很重要的函数-------递归函数
本帖最后由 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');
}程序运行的结果是打印出：5896。我们来看看这个程序的运行原理；
理解递归函数关键在于理解函数中所声明的变量是怎么存储的！当递归函数每一次调用自身，产生的变量都创建于运行时的堆栈上！这些变量符合栈的先进后出原则，只有栈顶的变量才能被访问。以前调用的产生的变量仍保存在堆栈上，但它们被新的调用产生的变量所覆盖，因此不能被访问！
这个程序的递归函数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，递归模式：大问题是如何分解为小问题的，也称为递归体！
用的适当的时候经常能高效的解决问题
其实能用循环就用循环，递归只是写起来方便，效率比循环低很多。不过在C++里可以利用编译器的计算能力，将运行时期的开销转到编译时期。编译时期就不能写循环了，都是用递归做的。 仰望天上的光 发表于 2011-12-3 20:31 static/image/common/back.gif
其实能用循环就用循环，递归只是写起来方便，效率比循环低很多。不过在C++里可以利用编译器的计算能力，将 ...
好的，你所说的效率是指计算机语句运行的效率。我所说的效率是算法设计的效率，如算法中的减治法就要经常用到递归。 仰望天上的光 发表于 2011-12-3 20:31 static/image/common/back.gif
其实能用循环就用循环，递归只是写起来方便，效率比循环低很多。不过在C++里可以利用编译器的计算能力，将 ...
随便写点，都被挑毛病！你这版主也太扣了！ {:5_105:} 其实我和你一样，也是随便写点...没想到你还这么较真...给你分数，以证明我不抠。 p62273470 发表于 2011-12-3 21:21 static/image/common/back.gif
好的，你所说的效率是指计算机语句运行的效率。我所说的效率是算法设计的效率，如算法中的减治法就要经常 ...
咦。。。。这就对了嘛！版主威武，版主加油！ 有助于学习递归 不错的楼主
表示很郁闷，递归很少利用 练家志 发表于 2011-12-5 18:45 static/image/common/back.gif
表示很郁闷，递归很少利用
递归很少用？我不明白你要表达什么意思？ 不会用，怎么样将问题i转化为递归？非数值计算特难转化 练家志 发表于 2011-12-6 11:54 static/image/common/back.gif
不会用，怎么样将问题i转化为递归？非数值计算特难转化
这个问题好？我也常在想！怎么样将问题转化为递归处理？首先要先考虑什么样的问题能用递归处理，然后再考虑如何将问题转化为递归处理！
一般来讲，具有下面特点的问题可以用递归来处理：
（1）这样的问题通常可以分解成几个子问题，而且你必须先要求解它的这几个子问题，然后综合子问题的解才能得到原始问题的解。但这几个子问题的结构是和原始问题一样的，这几个子问题其实就相当于规模小点的原始问题。那怎么求解这几个子问题呢？又必须把这几个子问题分别分解成另外几个子问题。这样不断分解，当子问题的规模足够小时，就可以直接求出最小的子问题。这样，求出最小的子问题后 ，就可以逆推出原始问题的解了。
举个排序的例子（请允许我举个数值的例子，因为这个好举点）：
将序列A｛16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14｝排序。
使用递归调用有下面的思路：
1，将这个序列A分成两个序列a，b
2，先给序列a排序，再给序列b排序，完了之后将两个排好序列的a和b，有序的合并起来。
这样我们会面临的问题是如何给a和b排序，于是我们也用上面的方法。比如给a排序：
1，将序列a分成两个子序列a1，a2
2，先给序列a1排序，再给序列a1排序，完了之后将两个排好序列的a1和a1，有序的合并起来。
就这样不断减小排序规模，当规模等于2或者1的时候，就可以不用分成两个序列那么麻烦，直接就可以排序了。得出最小序列的排序之后，因为递归函数特点的关系，会不断逆推出原始数列A的排序。
至于如何把问题转换为递归？
先要把实际问题用编程语言描述出来先吧，就是用数据类型来表示实际问题的数据信息，用数据结构类型来表示实际问题的逻辑关系。数值问题容易是因为用编程语言比较容易描述，非数值问题难是因为用编程语言描述起来不太习惯。关键还是要理解问题的逻辑关系，然后用编程语言把问题表示出来。重要的还是多练习，看多了应该自然就理解。
我也是不太懂，要考试了，所以就发贴当作复习巩固的机会。 我不用了，毕业啦 说的不错哈哈！力挺啊！！！！ 哇 挺犀利的 学习了 递归虽好，但还是不要多用 好像很复杂的样子:sad 感谢楼主无私分享！！！！！！ 一般看书这个略过
页:
[1]