很重要的函数-------递归函数

p62273470

递归函数很牛逼，也很重要。用的适当的时候经常能高效的解决问题！递归函数的代码相对简洁，但其内部工作原理相对复杂，所以有时候递归函数很难理解！

概念：
递归调用：是一种特殊的嵌套调用，是函数本身调用自己！


下面举个例子来理解递归函数的工作原理：
给定一个值5896，需要依次产生字符'5，'8'，'9'，'6'。我们采用的策略是把这个值反复的除于10，打印其余数。例如，5896除10余6，可我们不能直接打印6，我们需要打印的是机器字符集中表示数字‘6’的值，ASCII中‘6’的值是54，‘0’的值是48，于是我们可以得出‘6’= ‘0’+ 6；
用余数加上‘0’的值，便得出我们需要的值。

代码如下：

1. 
   
2. #include <stdio.h>
   
3. void digui(int m);
   
4. 
   
5. void main()
   
6. {
   
7. digui(5896);
   
8. }
   
9. 
   
10. 
    
11. void digui(int m)
    
12. /*m表示要打印的整数*/
    
13. {
    
14. int q;       //q保存每一次除10后的商
    
15. q = m / 10;
    
16. if (q != 0)digui(q);
    
17. putchar(m % 10 + '0');
    
18. 
    
19. }

复制代码

程序运行的结果是打印出：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++里可以利用编译器的计算能力，将运行时期的开销转到编译时期。编译时期就不能写循环了，都是用递归做的。

p62273470

仰望天上的光 发表于 2011-12-3 20:31

                               
登录/注册后可看大图

其实能用循环就用循环，递归只是写起来方便，效率比循环低很多。不过在C++里可以利用编译器的计算能力，将 ...

好的，你所说的效率是指计算机语句运行的效率。我所说的效率是算法设计的效率，如算法中的减治法就要经常用到递归。

p62273470

仰望天上的光 发表于 2011-12-3 20:31

                               
登录/注册后可看大图

其实能用循环就用循环，递归只是写起来方便，效率比循环低很多。不过在C++里可以利用编译器的计算能力，将 ...

随便写点，都被挑毛病！你这版主也太扣了！

仰望天上的光

其实我和你一样，也是随便写点...没想到你还这么较真...给你分数，以证明我不抠。

p62273470

p62273470 发表于 2011-12-3 21:21

                               
登录/注册后可看大图

好的，你所说的效率是指计算机语句运行的效率。我所说的效率是算法设计的效率，如算法中的减治法就要经常 ...

咦。。。。这就对了嘛！版主威武，版主加油！

ooogu

有助于学习递归 不错的楼主

练家志

表示很郁闷，递归很少利用

p62273470

练家志 发表于 2011-12-5 18:45

                               
登录/注册后可看大图

表示很郁闷，递归很少利用

递归很少用？我不明白你要表达什么意思？

练家志

不会用，怎么样将问题i转化为递归？非数值计算特难转化

p62273470

练家志 发表于 2011-12-6 11:54

                               
登录/注册后可看大图

不会用，怎么样将问题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的排序。

至于如何把问题转换为递归？
先要把实际问题用编程语言描述出来先吧，就是用数据类型来表示实际问题的数据信息，用数据结构类型来表示实际问题的逻辑关系。数值问题容易是因为用编程语言比较容易描述，非数值问题难是因为用编程语言描述起来不太习惯。关键还是要理解问题的逻辑关系，然后用编程语言把问题表示出来。重要的还是多练习，看多了应该自然就理解。

我也是不太懂，要考试了，所以就发贴当作复习巩固的机会。

练家志

我不用了，毕业啦

毛毛

说的不错哈哈！力挺啊！！！！

ever.g

哇 挺犀利的 学习了

wangerwanger

递归虽好，但还是不要多用

cable5881

好像很复杂的样子:sad

jsqking99

感谢楼主无私分享！！！！！！

xykj2011

一般看书这个略过