马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 p62273470 于 2011-12-3 19:48 编辑
递归函数很牛逼，也很重要。用的适当的时候经常能高效的解决问题！递归函数的代码相对简洁，但其内部工作原理相对复杂，所以有时候递归函数很难理解！
概念：
递归调用：是一种特殊的嵌套调用，是函数本身调用自己！
下面举个例子来理解递归函数的工作原理：
给定一个值5896，需要依次产生字符'5，'8'，'9'，'6'。我们采用的策略是把这个值反复的除于10，打印其余数。例如，5896除10余6，可我们不能直接打印6，我们需要打印的是机器字符集中表示数字‘6’的值，ASCII中‘6’的值是54，‘0’的值是48，于是我们可以得出‘6’= ‘0’+ 6；
用余数加上‘0’的值，便得出我们需要的值。
代码如下：
#include <stdio.h>
void digui(int m);
void main()
{
digui(5896);
}
void digui(int m)
/*m表示要打印的整数*/
{
int q; //q保存每一次除10后的商
q = m / 10;
if (q != 0)digui(q);
putchar(m % 10 + '0');
}
理解递归函数关键在于理解函数中所声明的变量是怎么存储的！当递归函数每一次调用自身，产生的变量都创建于运行时的堆栈上！这些变量符合栈的先进后出原则，只有栈顶的变量才能被访问。以前调用的产生的变量仍保存在堆栈上，但它们被新的调用产生的变量所覆盖，因此不能被访问！
这个程序的递归函数digui(int m)有两个变量：参数m，和变量q；
1，刚开始堆栈内容为：
m : 5896 q：NULL
2，执行除法后，堆栈内容为：
m : 5896, q： 589
3，第一次递归调用后
m ：589 q ： NULL
5896 589
4，第二次执行除法后
m ：589 q ： 58
5896 589
5，第二次递归调用后
m ： 58 q： NULL
589 58
5896 589
6，第三次执行除法后
m ： 58 q： 5
589 58
5896 589
7，第三次递归调用后
m： 5 q： NULL
58 5
589 58
5896 589
8，第四次执行除法后
m： 5 q： 0
58 5
589 58
5896 589
现在q等于0了，递归函数便不在自身调用了，而是开始打印输出。然后函数返回，并开始销毁堆栈上的变量值。
1，现在q等于0了，递归函数便不在自身调用了，这次调用所使用的是自己的变量，它们现在位于堆栈的顶部。因为它的m值是5，所以打印出来的数字是5。
m： 5 q： 0 此时输出：5
58 5
589 58
5896 589
2，接着函数返回，它的变量从堆栈中销毁。接着递归函数的前一次调用继续执行。这次调用所使用的是自己的变量，它们现在位于堆栈的顶部。因为它的m值是58以打印出来的数字是8。
m ： 58 q： 5 此时输出:58
589 58
5896 589
3，接着函数继续返回，它的变量从堆栈中销毁。接着递归函数的前一次调用继续执行。这次调用所使用的是自己的变量，它们现在位于堆栈的顶部。因为它的m值是589以打印出来的数字是9。
m ：589 q ： 58 此时输出：589
5896 589
4，接着函数继续返回，它的变量从堆栈中销毁。接着递归函数的前一次调用继续执行。这次调用所使用的是自己的变量，它们现在位于堆栈的顶部。因为它的m值是5896以打印出来的
数字是6。
m : 5896, q： 589 此时输出：5896
5，最后函数完全返回，变量从堆栈中全部销毁。
递归函数有两个基本要素：
1，边界条件：确定递归到何时终止，也称为递归出口。
2，递归模式：大问题是如何分解为小问题的，也称为递归体！
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2011-12-3 19:46:34
置顶卡
千斤顶
显身卡
发表于 2011-12-3 20:31:14
楼主
其实我和你一样，也是随便写点...没想到你还这么较真...给你分数，以证明我不抠。