递归实验-C语言递归调用的极限

sagasw

C语言递归调用不是无限的，当递归到一定时候，会出现stack over flow的问题。http://en.wikipedia.org/wiki/Stack_buffer_overflow

但是，这个度是多少呢？

我构造了一个极为简单的C语言递归程序，大家可以参考这里https://gist.github.com/749543

另外要说明的是，由于只是为了开心写着玩，所以没有测试其它平台，也没有横向纵向对比，如Linux，Mac PPC。这些结果都是程序在我机器上运行得到，仅做参考。

#include "stdafx.h"
int count = 0;
void f()
{
  int a = 1; int b = 1; int c = 1; int d = 1;
  a = b + 3;
  c = count + 4;
  d = count + 5*c;
  count++;
  printf("count: %d\n", count);
  f();
}

int _tmain(int argc, _TCHAR* argv[])
     {
        f(); return 0;
      }

我使用的是VC2010SP1的C语言模式编译，console程序，无优化。

运行结果如下：

默认情况下，count最后结果为42860，然后程序就结束了。通过查询MSDN可以知道

http://msdn.microsoft.com/en-us/ ... 6%28v=vs.80%29.aspx

我们可以通过修改project的link选项中的stack commit size和stack reserve size来改变程序的stack大小。

如果这两个size都设置为1、64、640、2048这几个值，结果都是10092.

如果size设置为1024000，那么结果是42860，与默认情况相同。可以看出这个size是以BYTE为单位。

如果size设置为1048000，结果为43372.

size设置为1072000以及2048000，结果都是86551.

size设置为2110000以及3072000，结果都是130242.

一般来说，我们基本上不需要考虑修改这个大小，因为很少会有将近四万的递归层次，默认值已经足够用了。但是如果万一不够用或者有这种递归需求，那么就需要修改这两个值，另外当我们新建一个线程的时候，也可以编程修改线程stack的大小。

http://cs.nyu.edu/exact/core/doc/stackOverflow.txt 这里解释了一下不同平台上stackoverflow的问题，有一些数据可以参考。

http://stackoverflow.com/questio ... ble-stack-size-in-c 在这里有人提供了一个有趣的递归C代码片段来判断栈大小。

在这里多废话几句，关于Lua的proper tail call http://www.lua.org/pil/6.3.html 。当我们使用Lua for windows构造一个简单的递归程序运行，依然是会得到stack over flow的结果。但是当我们使用proper tail call这种方式调用，（由于抛弃了前面程序的栈）调用可以无限循环下去，所以Lua这个特性常常用来构造state machine。关于使用proper tail call来实现斐波拉契，可以参考这里http://lua-users.org/wiki/ProperTailRecursion

http://sunxiunan.com/?p=1784

OwnWaterloo

某些C编译器（ gcc, vc的较高版本） 也可以优化一部分tail call。
只是C语言没有要求， 不像lua那样有保障。

rubylc_unix

我知道递归不是无限的，不过也不需要考虑这种情况{:3_189:}

OwnWaterloo

回复 4# rubylc_unix

1. 
   
2. #include <stdio.h>
   
3. 
   
4. void infinite(unsigend i, unsigned c)
   
5. {
   
6.       if (++i==0)
   
7.             printf("%u\n", c++);
   
8.       infinite(i, c);
   
9. }
   
10. 
    
11. int main(void)
    
12. {
    
13.       infinite(0, 0);
    
14.       return 0;
    
15. }
    

复制代码

编译器够好的话：
./a.out >nul

可以一直跑下去……

rubylc_unix

回复 5# OwnWaterloo


    谢谢提供实例，但是分配的栈不会溢出吗？

OwnWaterloo

回复 5# OwnWaterloo

再改有趣一点……

1. 
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. 
   
5. void infinite(unsigned i, unsigned c, clock_t t)
   
6. {
   
7.       if (++i==0)
   
8.       {
   
9.             clock_t t2 = clock();
   
10.             printf("wrap %u tims, use %f sec\n"
    
11.                   ,++c, (double)(t2-t)/CLOCKS_PER_SEC);
    
12.             t = t2;
    
13.       }
    
14.       infinite(i, c, t);
    
15. }
    
16. 
    
17. int main(void)
    
18. {
    
19.       infinite(0, 0, clock() );
    
20.       return 0;
    
21. }
    

复制代码

veking

有特殊需求的时候还是非常有用的。

OwnWaterloo

回复 6# rubylc_unix

假设：
f()
{

      ...
      g();

}

f函数以调用g作为最后一个语句。
再假设， 某个调用者（假设叫c）调用了f。


从语义上， 调用链应该是 c->f->g， 且逆向返回。
但考虑g返回到f后， 再没有多余的事可做； 所以可认为是g直接返回到c。
那么， 在调用g时， f的frame就不需要保持（因为返回时不需要）， 继而……  f的frame就可以被g复用。

f中的g的调用， 称为尾调用。
如果尾调用是对自身的递归调用， 就称了尾递归。 优化工作比一般性的尾调用更容易。
每次递归调用时， 调用者的栈被复用， 原地作为被调用者的栈； 栈的总体使用不会增长。

具体可看汇编代码。  不过， 也就好玩而已， 切不可依赖。
实际代码还是老老实实的转化为迭代比较靠谱……

jhui66

顶楼主