尾递归真的会被优化吗？

linyunxian

一直听说尾递归的效率高是因为它会被编译器优化，不会有产生调用栈的开销。
可从调试来看，却没发现我普通的递归有什么差别。
下面是尾递归的测试实例。

1. 
   
2. long long fact_tr_aux(long long n, long long *result)
   
3. {
   
4.         printf("%x\n", &n); /* print &n in stack */
   
5. 
   
6.         if (n==0 || n==1)
   
7.                 return *result;
   
8. 
   
9.         *result *= n;
   
10. 
    
11.         return fact_tr_aux(n-1, result);
    
12. }
    
13. 
    
14. long long fact_tr(long long n)
    
15. {
    
16.         long long result = 1;
    
17. 
    
18.         return fact_tr_aux(n, &result);
    
19. }
    
20. 
    
21. int main(int argc, char *argv[])
    
22. {
    
23.         printf("%lld\n", fact_tr(atoi(argv[1])));
    
24. 
    
25.         return 0;
    
26. }
    

复制代码

无论从汇编还是gdb看调用栈，都发现一样的在栈上分配递归了。
这是为什么？

谢谢各位的回复。
总结一下：gcc也可能会对尾递归优化，前提是递归栈里没有变量需要保存。
注释掉这行似乎就可以：        printf("%x\n", &n); /* print &n in stack */
gcc不能判断&n是否属于上个栈帧上，所以没有优化。

linyunxian

@humjb_1983 兄台解释一下？

A.com

编译器不会优化的，递归的效率主要取决于边界条件是否最优。

humjb_1983

linyunxian 发表于 2014-01-23 13:27
一直听说尾递归的效率高是因为它会被编译器优化，不会有产生调用栈的开销。
可从调试来看，却没发现我普通 ...

据了解，编译器(至少是gcc)是不会去递归的，没有这个功能，当然肯定还会压栈，并带有栈溢出的风险，不知兄台是从哪儿看到编译器会做这样的优化的呢？呵呵

bruceteen

C/C++ 没有规定过 必须优化尾递归。事实上，也没有哪个编译器去优化尾递归。当然，如果有编译器去优化尾递归，也是符合标准的。

估计你说的是Java等，Java等才有“尾递归”的概念。

尾递归 很容易改写成 循环，所以C/C++是不会加入“尾递归”这个概念的，优化让编码者自己来。

humjb_1983

linyunxian 发表于 2014-01-23 13:27
一直听说尾递归的效率高是因为它会被编译器优化，不会有产生调用栈的开销。
可从调试来看，却没发现我普通 ...

咨询了一下专家，确实对于“尾递归”的情况，也就是说函数体中用到的变量不需要栈保存，gcc -O2是可以进行优化的，会将其展开成循环，但如果递归函数中有分支就不行，比如路径遍历的实现。有分支就要保存条件变量，就需要压栈，这种情况就展不开。实际编码中绝大多数都是这种情况。

linyunxian

回复 6# humjb_1983


    嗯！刚测试了一下！gcc编译c代码如果递归代码里的变量不需要在栈里维护，就有可能被优化掉。不产生新的栈桢。

shan_ghost

http://stackoverflow.com/questio ... ursion-optimization

linyunxian

回复 8# shan_ghost


    gcc 的优化选项 ~-O1 -foptimize-sibling-calls~  或 ~-O2~ 都会使能尾递归的优化。
不过这种优化是有前提的，就是递归函数本身不依赖函数栈这种结构。

OwnWaterloo

1. 
   
2. printf("%x\n", &n); /* print &n in stack */
   

复制代码

这让编译器情何以堪。。。