C语言必学经典算法之一—递归算法

1.函数调用

通常，当一个函数运行期间调用另一个函数时，在运行被调函数之前，系统需要完成3件事：

（1）将所有的实参，返回地址（个人理解是调用被调函数时的下一个语句的地址）等信息传递给被调函数保存。

（2）为被调函数的局部变量分配存储空间。

（3）将控制转移到被调函数入口。

从被调函数返回调用函数之前，系统完成3件事：

（1）保存被调函数的计算结果。

（2）释放被调函数的数据区。

（3）依照被调函数保存的返回地址，将控制转移到调用函数。

2.递归

一个函数自己直接或间接调用自己。

思想就是：将问题规模不断缩小，化繁为简，求n！转化成（n-1）!,再转换成(n-2)！…….最后转换成(1)!.

有如汉诺塔问题，如果初始有10个砝码，要从A移动到C，这个看起来比较复杂。只要把前9个移动到B，然后移

动第10个到Ｃ。那这9个怎么移动呢，也用这种方式。。。这就是递归实现汉诺塔。

现在我们来看一个简单的递归算法：C语言实现汉诺塔

递归算法的精髓是一层入一层，直至遇到满足的结束语句，所以一般和递归在一起的是一些判断语句。递归函数得要有终止语句。

遇到递归问题需要根据规律解决。

（1）找到所谓的终止条件，即让递归停止的条件

（2）找到递推的关系式

（3）递归的方向要搞清楚，一般是向最终的终止条件不断递归

（4）递归 分为回推和递推两个阶段，当递推到终止条件时，程序会反向推回（回推）！！！！

一般会出现递归不像递归的情况，这个要小心

例题：

猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就又多吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第10天在想吃的时候就剩一个桃子了,问第一天共摘下来多少个桃子？并反向打印每天所剩桃子数。

/**************************************

*author: Yang Xu

*goals: compute a question of monkey eatting pitches by recursion

***************************************/

#include<stdio.h>

#include<process.h>

int main()

{

/*打印最初的桃子数量*/

printf(“%d\n”, f(1));

system(“pause”);

return 0;

}

/*第day天剩下的桃子数*/

int f(int day)

{

int n;

if(day==10)

n=1;

else

{

/*第day天（左）和第day+1天（右）所剩桃子的关系式*/

n=(f(day+1)+1)*2;

/*由于递归规律，直接倒序打印*/

printf(“第%d天所剩桃子%d个\n”, day, n);

}

return n;

}

3. 善用递归:

使用递归有利有弊，有点自然是为某些问题提供了简单的解决办法，同时，代码看起来也很简洁；而缺点也不容忽视，很多递归会很快耗尽计算机的内部资源。分分钟电脑死机。

正因为如此，很多递归我们都可以使用非递归来代替，比如下面我们求两个整数的最大公约数:

4.结束语

现在的程序设计追求的就是可读性好，递归的算法看起来简洁。随着计算机性能的不断提高，程序在更多的场合是优先考虑可读性，因此，如果可以，鼓励使用递归优先实现程序思想。

每天进步一点点，每天消化一点点。如果你有更高的想法，欢迎一起交流。如果觉得文章写得还不错，点个赞呗。