经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C 语言 » 查看文章
我对递归的理解和总结
来源：cnblogs　　作者：yiifburj　　时间：2021/2/1 11:59:50　　对本文有异议

看了自己的动态记录，发现自己已经遗忘了曾经的自己，有一条动态，2013年的时候，我看了一篇关于尾递归的博文，那时候还只是一个初学者，胡乱评论了一下，作者希望我能写一篇博文发表一下自己的看法，当时没有写，然而现在却想写点什么总结一下，不保证说的没问题，只希望如果有像我当年一样的初学者看到，可以参考借鉴，或许能有些帮助，在此也感谢给我启发，教会我知识的陌生朋友们。

 

1. 递归就是一个函数直接或间接的自己调用自己，间接就是f0 -> f1 -> f0 ->f1这种，但也就是一个名词而已，并不神奇，它只是一个普普通通的函数调用，但由于自己调用自己这个特性，有一种自动化的力量，给它一个规则，它可以自动的持续运行下去，直到触发停止条件。一个递归函数就像是一个简单的计算机。

2. 所有的递归都可以用循环来替代，所有的循环也都可以用递归来替代，两者是等价的。

3. 递归是人脑的直接思维方式，循环是当前多数(我所知道的所有的)cpu的直接思维方式。

4. 对于cpu来讲，函数调用只是寄存器，内存，跳转等操作，如果不涉及额外栈空间使用（极简单函数的特殊情况），函数调用和循环的差别可能仅仅是使用的寄存器不同。

5. 递归可以把复杂的问题变得简单，是一种处理问题的模型。比如汉诺塔，快速排序，二叉树遍历和查找，如果学会使用递归这种思维方式思考问题，很多问题会变得很简单，大事化小，小事化了，每一步都是很简单的操作。

6. 正确的思维会使问题很简单，错误的思维会让人发懵，使用递归的思考方式是忘记调用的是自己，自己调用的是任意一个函数，那个函数有没有实现，是否实现得正确不是我现在要关心的事，我只要保证，在那个函数正确实现的前提下，我现在写的这个函数是没问题的，当我写完当前函数的时候，被调用的函数也就写完了(副产物)，因为它们是同一个，这有点像数学归纳法。

7. 正确的实现一个递归函数，需要保证有退出的条件，除非你是在写一个死循环，同时随着递归层数变深，问题逐渐简单化，规模逐渐缩小，或者是向退出条件逼近(收敛)。

8. 递归对栈空间的占用分两种，尾递归开启相应的优化之后不会导致栈空间使用不停扩大，非尾递归对栈空间的调用要看递归的层数，递归层数是可预测的，一般二分的递归(理想的情况，极端的情况二叉树会变成链表，这时候已经不是二分法了，但二叉树是可以事先保证平衡的)层数大约为log2(n)，30层函数调用使用的栈空间很少(使用超级庞大的数组局部变量这样的特殊情况除外)，但是n是10亿级别，这个时候要关注的已经不是栈空间了，而是保存数据的内存空间或cpu等资源，比如用递归方法计算Fibonacci数列，现在的个人电脑默认栈空间(M级别)，不可能栈溢出的，忙不过来的是cpu，多分的情况栈空间一般都不会过深，原因是一边调用增加深度，一边返回减少深度，用完全平衡二叉树为例，画一个图看一下调用过程就一目了然。

 

下面就栈空间的使用，尾递归，递归循环的转换等问题详细分析。

除非是特殊的情况，编译器能优化成不使用栈空间，否则递归是需要栈空间的，这和任何一个函数调用都是一样的，对于解决实际问题的函数，一般没有不需要栈空间的，在函数调用的时候，需要保存cpu寄存器到栈空间（用于恢复函数的执行），局部变量也有可能会导致栈空间的使用，每一个函数执行的时候局部变量都会占用一次栈空间，每一次函数调用也会触发一次栈空间的使用，这就是每一次递归调用的栈空间代价，函数调用总是有调用就有返回的，最大代价就是最大递归层数，尾递归是一种特殊情况，考虑下面的函数。

  1. int f(int n)
  2. {
  3.     if(n <= 0)
  4.        return n;
  5.     // body;
  6.     return f(n-1);
  7. }
  1. return f(n-1);是函数f的最后一个语句。f(n-1)的返回值就是f(n)的返回值，也就是说对于当前函数f(n)已经没有必要保存现场了，它的栈空间不需要恢复了，f(n-1)返回到f(n)，f(n)再向上返回，那为什么要留个中介呢，为什么不直接向上返回呢，所以栈空间中保存的返回地址等不动，进入f(n)时保存的寄存器(callee-saved registers)不动，也就是f(n)的上层现场不动，他们直接继承给f(n-1)，f(n-1)不再
    保存它的返回地址(f(n)的最后)，也不再保存使用的寄存器(f(n)已经不需要恢复了)，f(n)的局部变量使用的栈空间直接被f(n-1)的给覆盖掉，同样的逻辑再向上递推，会发现，每一层函数调用引起的栈空间占用都相当于没有了，实际上上述代码就变成了
  1. int f(int n)
  2. {
  3.     while( n > 0 )
  4.     {
  5.         //body;
  6.         n--;
  7.     }
  8.     return n;
  9. }

这种递归叫做尾递归，即递归调用之后不需要再有额外的操作，并且递归之前没有其他递归调用，开启优化之后（gcc, O2默认开启）编译器可以将尾递归优化成循环。

再考虑下面的函数

  1. int f(int n)
  2. {
  3.     if(n <= 0)
  4.        return n;
  5.     // body;
  6.     return n + f(n-1);
  7. }

这种递归调用是无法 直接 变成循环的，这里用直接，是因为这种情况太简单了，编译器不会那么傻，gcc O1就会变成循环，为什么不能直接变成循环呢，因为f(n-1)之后还有其他操作（返回值+n），为了继续其他操作能够继续执行，调用f(n-1)之前需要保存现场，需要用到栈空间，每一层调用都会保存一次栈空间，这时候栈空间的占用是O(n)的，因为不是二分，三分，n的数量稍大一点就会导致栈溢出。当然这里实在是太简单了！换个复杂的，编译器就不会优化了（只是写本文的时候用的gcc，不排除以后编译器越来越智能的可能）。

  1. unsigned long fib(int n)
  2. {
  3.     if(n < 2)
  4.        return 1;
  5.     return fib(n-1) + fib(n-2);
  6. }

fib(3) 调用 fib(2)和fib(1)，假定编译器生成的指令是先调用fib(2)，那么就要在栈空间中保存现场，以便fib(2)返回的时候能够继续执行fib(1)和一个加法操作，fib(2)调用fib(1)和fib(0)，还是假定先调用左边的，调用fib(1)的时候需要保存现场，然后返回1, 恢复现场，保存现场，调用fib(0)，然后恢复现场，加法运算，然后再返回上层，即fib(2)返回，恢复现场，fib(2)下面的所有调用占用的栈空间都已释放了(递减栈栈顶寄存器数值增加)，然后保存现场，调用fib(1)，返回1, 恢复现场，加法运算，返回，整个fib(3)就是这样完成的，可见每次调用+左边的分支的时候，递归层数会增加一层，每次调用+右面的分支的时候，左面增加的层数都已经恢复，这是一个动态增减的过程，递归层数是有限的。这种Fibonacci数列算法慢的根源在于重复计算。不重复计算的方法如下：

  1. unsigned long fib2(int n,  unsigned long left, unsigned long right)
  2. {
  3.     if( n < 2 )
  4.         return right;
  5.     return fib2(n - 1, right, left+right);
  6. }

这里是一个尾递归，相当于循环, 当然如果不优化，栈空间占用是O(n)，n足够大是会溢出的。

可见，循环和尾递归是直接互相转换的，循环变量相当于函数中的参数，循环退出条件相当于函数退出的条件，循环变量的增减相当于参数传递时的增减计算，循环体相当于函数体，所以像scheme这样的编程语言没有循环但是并不影响表达能力。

Fibonacci数列循环的算法是从数列的左边开始，不符合直观定义，需要知道原理才能想到，直观的定义是从右到左，然而左边又没有准备好，所以需要借用栈。

考虑一个更明显的例子，单向非循环链表的正向遍历和逆向遍历，前者是尾递归(循环)，后者非尾递归(使用循环需要借助栈)，正向遍历不需要额外的栈空间，但是如何实现逆向遍历呢？首先要拿到最后一个节点，但是访问完最后一个节点了，到哪里去找上一个节点呢，单向链表并没有prev指针，很明显，需要在内存中保存，由于访问的顺序是后进先出，用的应该是栈这种模型，而函数调用本来就是栈的模型的，所以如果使用函数调用的方式是很自然的，很符合人的思维逻辑的，用递归的方式都不用考虑栈的问题，因为这是一种很自然的符合人的逻辑的思考模型，代码如下：

  1. struct list{
  2.     int c;
  3.     struct list *next;
  4. };
  6. #define print_list(list) (void)list
  7. void visit(const struct list *cur)
  8. {
  9.     if(cur == NULL)
  10.         return;
  11.     print_list(cur);
  12.     visit(cur->next);
  13. }
  14. void visit_reverse(const struct list *cur)
  15. {
  16.     if(cur == NULL)
  17.         return;
  18.     // 访问后面的，怎么访问的不用管，会有人保证它的逆序
  19.     visit_reverse(cur->next);
  20.     // 后面的全都访问完了，访问当前的
  21.     print_list(cur);
  22. }
  24. #define list_append(tail_p, cur) ((*tail_p)->next = cur, (*tail_p) = cur)
  25. struct list * _list_reverse(struct list *cur, struct list **tail_after_reverse)
  26. {
  27.     // 最后一个
  28.     if(cur->next == NULL)
  29.     {
  30.         // 记录末尾，方便list_append
  31.         *tail_after_reverse = cur;
  32.         return cur;
  33.     }
  34.     struct list *head = _list_reverse(cur->next, tail_after_reverse);
  35.     list_append(tail_after_reverse, cur);
  36.     return head;
  37. }
  38. // 逆序单向链表
  39. struct list * list_reverse(struct list *cur)
  40. {
  41.     struct list *tail_after_reverse;
  42.     if(cur == NULL)
  43.         return cur;
  44.     struct list *head = _list_reverse(cur, &tail_after_reverse);
  45.     list_append(&tail_after_reverse, NULL);
  46.     return head;
  47. }

 

尾递归和循环可以互相转换，这是很明显的，那么非尾递归如何和循环互相转换呢，理论上是一定可以完成的，因为对于cpu来讲递归就是用栈来实现的，下面以二叉树的先序，中序，后序的遍历方式来举例说明，不过能够实现不代表应该这样做，代码的可读性和见解性非常重要，并且转变成循环也未必就能感受到性能的变化。

  1. #include <assert.h>
  2. #include <stdio.h>
  3.  
  4.  
  5. struct tree{
  6.     int n;
  7.     struct tree *left;
  8.     struct tree *right;
  9. };
  11. static const void *stack[128];
  12. static char stack_flag[128];
  13. static int stack_i;
  14. #define visit(t) printf("%d\t", t->n)
  15. #define push(x) do{if(x) stack[stack_i++] = x;}while(0)
  16. #define pop() (stack_i == 0 ? NULL : stack[--stack_i])
  17. #define push2(x, flag) do{if(x) {stack[stack_i] = x; stack_flag[stack_i++] = flag;}}while(0)
  18. #define pop2(flag) (stack_i == 0 ? NULL : ((flag=stack_flag[--stack_i]), (stack_flag[stack_i] = 0), stack[stack_i]))
  19.  
  20. // 二叉树的先序遍历
  21. //
  22. // 递归版本
  23. void preorder(const struct tree *t){
  24.     if(t == NULL)
  25.         return;
  26.     visit(t);
  27.     preorder(t->left);
  28.     preorder(t->right);
  29. }
  31. // 循环版本
  32. // 如何变成循环呢，方法就是递归怎么来，我们就怎么来，
  33. // 1. 调用visit，但是调用之后要恢复两个函数调用，为了恢复现场，需要在栈空间中保存后续要做的事，我们这里显然不需要保存cpu寄存器等，只需要保存t->left和t->right就可以了，由于是先调用t->left，后调用t->right，所以入栈就要反过来。
  34. //push(t->right);
  35. //push(t->left);
  36. //能不能直接push(t)呢，答案是不能，除非标记t已经访问过了，否则就循环访问t了，但是标记t访问过了还是要把t->right和t->left入栈，不如就直接来，更直接。
  37. // 2. t访问完了，递归程序就恢复现场，返回到visit的下一个地址执行，恢复现场就对应我们的出栈，继续执行同样的preorder逻辑就相当于我们重复一次循环，
  38. // 3. 递归程序继续这个过程，直到函数栈上的最底层，也就是最后一个函数调用返回，对应我们的继续这个过程，直到栈里面没有数据了为止。
  39. // 代码如下
  40. void preorder_loop0(const struct tree *in)
  41. {
  42.     const struct tree *t = in;
  43.     if(t == NULL)
  44.         return;
  45.     do{
  46.         visit(t);
  47.         push(t->right);
  48.         push(t->left);
  49.     }while((t = pop()) != NULL);
  50. }
  51. //这个程序是最原始的贴近递归的版本，还可以继续优化，visit(t)之后pop出来的一定是t->left，那么下次一定是visit(t->left)，往下递推，每一次都是visit(t->left)，也就是说按照一直向左的方向遍历就可以了，需要入栈的只是右子树，但是右子树谁先谁后呢，从递归程序可以看出，所有的左子树成员都在右子树的前面遍历，也就是说最接近树根的大叉是优先级最低的，远离树根的在左子树上的右子树更优先，也就是说，入栈的顺序和访问的顺序相同，即
  52. //
  53.  
  54. void preorder_loop1(const struct tree *in)
  55. {
  56.     const struct tree *t = in;
  57.     if(t == NULL)
  58.         return;
  59.     do{
  60.         while(t)
  61.         {
  62.             visit(t);
  63.             push(t->right);
  64.             t = t->left;
  65.         }
  66.     }while((t = pop()) != NULL);
  67. }
  68. // 将上面两种版本对比，想象一下preorder_loop0的执行过程，也可以直接优化为preorder_loop1
  70. //中序遍历
  71. // 递归版本
  72. void inorder(const struct tree *t){
  73.     if(t == NULL)
  74.         return;
  75.     inorder(t->left);
  76.     visit(t);
  77.     inorder(t->right);
  78. }
  80. // 第一步还是按照和递归一一对应的方式来转换成循环，这个地方有点复杂，因为第一个函数不是visit，本身就是个递归的，这时候的处理方式不唯一，可以直接把递归版本函数中最上面的那个inorder展开，也可以按照通用的循环中的逻辑来处理那个inorder，前者直接就是优化之后的了。另外由于inorder和visit是两种操作，为了区分是哪一种操作，还需要在入栈的时候加标记等。
  81. void inorder_loop0(const struct tree *in)
  82. {
  83.     int is_visit = 0;
  84.     const struct tree *t = in;
  85.     if(t == NULL)
  86.         return;
  87.     do{
  88.         if(is_visit)
  89.             visit(t);
  90.         else
  91.         {
  92.             push2(t->right, 0);
  93.             push2(t, 1);
  94.             push2(t->left, 0);
  95.         }
  96.     }while((t = pop2(is_visit)) != NULL);
  97. }
  98. // 简化push(t->left); 同preorder的方法
  99. void inorder_loop1(const struct tree *in)
  100. {
  101.     int is_visit = 0;
  102.     const struct tree *t = in;
  103.     if(t == NULL)
  104.         return;
  105.     do{
  106.         if(is_visit)
  107.             visit(t);
  108.         else
  109.         {
  110.             while(t)
  111.             {
  112.                 push2(t->right, 0);
  113.                 push2(t, 1);
  114.                 t = t->left;
  115.             }
  116.         }
  117.     }while((t = pop2(is_visit)) != NULL);
  118. }
  119. // 继续优化，每次pop出来的一定是先visit的，然后接着就是它的right，那么两者可以合成一个整体，这样也不用标记是否是is_visit了
  120. void inorder_loop2(const struct tree *in)
  121. {
  122.     const struct tree *t = in;
  123.     if(t == NULL)
  124.         return;
  126.     while(t)
  127.     {
  128.         push(t);
  129.         t = t->left;
  130.     }
  131.     while((t = pop()) != NULL)
  132.     {
  133.         visit(t); // pop -> t
  134.         if(t->right) // pop -> t->right
  135.         {
  136.             t = t->right;
  137.             while(t)
  138.             {
  139.                 push(t);
  140.                 t = t->left;
  141.             }
  142.         }
  143.     }
  144. }
  146. // 后续遍历
  147. // 递归版本
  148. void postorder(const struct tree *t){
  149.     if(t == NULL)
  150.         return;
  151.     postorder(t->left);
  152.     postorder(t->right);
  153.     visit(t);
  154. }
  155. // 和中序遍历相同的方式，唯一一个区别就是 visit(t) 和postorder(t->right)的顺序换了一下，也就是入栈的顺序换了一下。代码如下：
  156. void postorder_loop0(const struct tree *in)
  157. {
  158.     int is_visit = 0;
  159.     const struct tree *t = in;
  160.     if(t == NULL)
  161.         return;
  162.     do{
  163.         if(is_visit)
  164.             visit(t);
  165.         else
  166.         {
  167.             push2(t, 1);
  168.             push2(t->right, 0);
  169.             push2(t->left, 0);
  170.         }
  171.     }while((t = pop2(is_visit)) != NULL);
  172. }
  174. // 前面已经用过这种思路，去掉push t->left(附带的pop也一起去掉了)
  175. void postorder_loop1(const struct tree *in)
  176. {
  177.     int is_visit = 0;
  178.     const struct tree *t = in;
  179.     if(t == NULL)
  180.         return;
  181.     do{
  182.         if(is_visit)
  183.             visit(t);
  184.         else
  185.         {
  186.             while(t)
  187.             {
  188.                 push2(t, 1);
  189.                 push2(t->right, 0);
  190.                 t = t->left;
  191.             }
  192.         }
  193.     }while((t = pop2(is_visit)) != NULL);
  194. }
  196. // t->right 先出栈，处理完整棵树才能继续处理t(即visit(t))，所以t和t->right不能当成一个整体来优化
  197. // 但仍然可以继续优化，t->right的处理过程是先push 它自己，也就是说visit(t)的时候上一次pop一定是
  198. // t->right，并且pop -> t->right 然后pop -> t 的时候一定是访问t的时候，这是后序遍历的定义的必然
  199. // 即 t->right == NULL 或last_pop/visit == t->right就是visit(t)的时刻，这样可以去掉is_visit的标记
  200. // 使用更简单的push 和 pop
  201. void postorder_loop2(const struct tree *in)
  202. {
  203.     const struct tree *t = in, *last_visit = NULL;
  204.     if(t == NULL)
  205.         return;
  207.     while(t)
  208.     {
  209.         push(t);
  210.         push(t->right);
  211.         t = t->left;
  212.     }
  213.     while((t = pop()) != NULL)
  214.     {
  215.         if(t->right == NULL || last_visit == t->right)
  216.         {
  217.             visit(t);
  218.             last_visit = t;
  219.         }
  220.         else
  221.         {
  222.             while(t)
  223.             {
  224.                 push(t);
  225.                 push(t->right);
  226.                 t = t->left;
  227.             }
  228.         }
  229.     }
  230. }
  232. int main(int argc, char *argv[])
  233. {
  234.     /*
  235.      *
  236.      *                        4
  237.      *                     /         *                   2        6
  238.      *                 /  \      /        *                1    3    5      8
  239.      *                                /      *                               7   9
  240.      *
  241.      *
  242.      */
  243.     struct tree t[9] = {
  244.         {1, NULL,NULL},
  245.         {2, &t[0],&t[2]},
  246.         {3, NULL,NULL},
  247.         {4, &t[1],&t[5]},
  248.         {5, NULL,NULL},
  249.         {6, &t[4],&t[7]},
  250.         {7, NULL,NULL},
  251.         {8, &t[6],&t[8]},
  252.         {9, NULL,NULL},
  253.     };
  254.     preorder(&t[3]);
  255.     puts("");
  256.     assert(stack_i == 0);
  257.     preorder_loop0(&t[3]);
  258.     assert(stack_i == 0);
  259.     puts("");
  260.     preorder_loop1(&t[3]);
  261.     assert(stack_i == 0);
  262.     puts("");
  263.     inorder(&t[3]);
  264.     assert(stack_i == 0);
  265.     puts("");
  266.     inorder_loop0(&t[3]);
  267.     assert(stack_i == 0);
  268.     puts("");
  269.     inorder_loop1(&t[3]);
  270.     assert(stack_i == 0);
  271.     puts("");
  272.     inorder_loop2(&t[3]);
  273.     puts("");
  274.     postorder(&t[3]);
  275.     puts("");
  276.     assert(stack_i == 0);
  277.     postorder_loop0(&t[3]);
  278.     assert(stack_i == 0);
  279.     puts("");
  280.     postorder_loop1(&t[3]);
  281.     assert(stack_i == 0);
  282.     puts("");
  283.     postorder_loop2(&t[3]);
  284.     assert(stack_i == 0);
  285.     return 0;
  286. }

尾递归和非尾递归是否能转换呢，对于Fibonacci数列这样的特殊情况当然可以，但有些问题就是递归模型，比如快速排序，所以是无法直接转换的，如果非要转换的话，也是可以的，借助额外实现的栈，因为循环和尾递归是等价的，循环加额外的栈能实现的，尾递归加额外的栈也能实现，但是这样做是否有意义呢，人工精心优化的循环/尾递归程序和非尾递归相比，有时候也许能获得少量性能提升，但是代码的可读性却很差，而非尾递归程序却是非常直观。

补充一点，看编译器是否进行了尾递归优化，可以通过gdb或objdump看汇编，看尾递归发生的时候后面是否有其他操作，或者是否还有递归的调用，gcc O2一定会优化的， 如果通过试验测试，建议数字要足够大，因为优化之后的程序可能占用栈空间很小，而进程的栈空间可能又很大，所以没有进行尾递归优化依然可能不会栈溢出。

 

总之，递归是一种非常好的模型，栈空间一般可预测，尾递归因为利用函数实现，局部变量隔离，也会增加安全性，但是记得开优化，尽量不用栈和循环替代递归，增加代码可读性。

原文链接：http://www.cnblogs.com/yiifburj/p/14350553.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C 语言热门文章

  • 图形学入门(1)——直线生成算法（DDA和Bresenham）
  • 用C语言制作一个最简单的飞机游戏！
  • MODBUS 超时时间计算
  • zabbix wait for 15s seconds 出现原因及调优建议
  • C/C++知识分享：assert()函数
  • 图形学入门(2)——圆弧生成算法（中点画圆法）
  • C 共享内存封装
  • C语言中break与continue的用法和区别详解
  • GStreamer基础教程09 - Appsrc及Appsink
  • 三元组矩阵行列式的计算（用递归）

    • C 语言推荐文章

  • C语言指针易混淆知识点总结
  • 进程间通信
  • 数组降维、函数栈帧、地址空间、可变参数原理剖析
  • 【Learning eBPF-3】一个 eBPF 程序的深入剖析
  • [apue] 进程控制那些事儿
  • 解密C语言选择结构：掌握条件语句与分支逻辑的利器
  • 精通C语言：打造高效便捷的通讯录管理系统
  • c语言实现内存池
  • [数据结构] 数组与特殊矩阵
  • 探索C语言结构体：编程中的利器与艺术

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号