递归下降分析程序的设计与实现_算法讲解|如何直观理解递归算法

什么是递归   

递归是程序设计语言中的一种广泛应用的算法&＃xff0c;能大大减少多次重复计算的代码量。

递归就是某个函数或者操作在运行中调用自己的现象&＃xff0c;类似于一个连环套娃的过程。

///

//

递归的实现

当然&＃xff0c;由于计算机的计算能力有限&＃xff0c;并且最终需要通过深层的结果求得浅层的结果&＃xff0c;我们不可能让递归程序无限进行下去。

举个例子&＃xff0c;我们熟悉的养兔子问题(斐波那契数列)中的项就可以用递归求解。

我们只需要知道

就可以了。

程序会先运行到求f(n)的环节&＃xff0c;又因为此时f(n-1),f(n-2)仍未求出&＃xff0c;程序会递归到下一层求解&＃xff0c;之后求f(n-1)时又因为f(n-2),f(n-3)未知&＃xff0c;又会进入下一层递归...直到0和1时&＃xff0c;不能继续往下递归&＃xff0c;返回上层。用f(0)和f(1)求出f(2)进而返回上层求出f(3)&＃xff0c;以此类推&＃xff0c;直到求出f(n)。

我们将上述求解过程分成许多小过程&＃xff0c;每个小过程的小结果称为状态。

在递归过程中&＃xff0c;我们求某一状态前需要之前的状态作为支撑来求解&＃xff0c;该过程称为状态转移。

///

//

代码实现

我们来看看是如何用代码实现递归这一算法的吧&＃xff0c;我们编写一个程序&＃xff0c;输入小于等于30的非负整数i&＃xff0c;输出f(i)&＃xff0c;以下给出代码的C语言版本。

#includeint Fibonacci(int n) { if (n &＃61;&＃61; 0 || n &＃61;&＃61; 1)return n; //f(0)&＃61;&＃61;0,f(1)&＃61;&＃61;1,直接返回上层 return Fibonacci(n - 1) &＃43; Fibonacci(n - 2); /*递归到下一层&＃xff0c; 求出f(n-1),f(n-2)后再返回该层求f(n)*/}int main(void) { int i,fi;//i为输入的数列的序数&＃xff0c;fi为输出的f(i)  scanf("%d",&i);//输入 fi&＃61;Fibonacci(i);//调用递归函数进行求解  printf("%d\n",fi);//输出 return 0;}

递归过程形成了一个n层的二叉树(每个节点最多有两个子节点)&＃xff0c;整棵树最多有2的n次方个节点&＃xff0c;故该算法的时间复杂度为

///

//

下面留下几道例题&＃xff0c;感兴趣的小伙伴们可以挑战一下哦&＃xff01;

昆虫繁殖

问题描述

 科学家在热带森林中发现了一种特殊的昆虫, 这种昆虫的繁殖能力很强. 每对成虫过x个月产y对卵, 每对卵要过两个月长成成虫. 假设每个成虫不死, 第一个月只有一对成虫, 且卵长成成虫后的第一个月不产卵 (过 x 个月产卵), 问过 z 个月以后, 共有成虫多少对? 

输入

包含三个整数&＃xff0c;用空格隔开&＃xff0c;分别表示x、y、z。

题目范围 x ≥ 1, y ≥ 1, z ≥ x

输出

z个月后成虫的对数

样例输入:

1 2 8

样例输出:

37

超级楼梯

问题描述

有一楼梯共M级&＃xff0c;刚开始时你在第一级&＃xff0c;若每次只能跨上一级或二级&＃xff0c;要走上第M级&＃xff0c;共有多少种走法&＃xff1f;

输入

输入数据首先包含一个整数N&＃xff0c;表示测试实例的个数&＃xff0c;然后是N行数据&＃xff0c;每行包含一个整数M(1<&＃61;M<&＃61;40),表示楼梯的级数。

输出

对于每个测试实例&＃xff0c;请输出不同走法的数量

样例输入

2
2
3

样例输出

1
2

解析我们会在下期推送放出&＃xff0c;如果想获取更多资料欢迎加入周行算协招新群↓↓↓

end.

文字&＃xff0c;代码&＃xff0c;&＃xff1a;李怡凡

配图&＃xff1a;unsplash&＃xff0c;penjee&＃xff0c;网络