尾递归真的会被优化吗？

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 兄台解释一下？

linyunxian

回复 6# humjb_1983


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

linyunxian

回复 8# shan_ghost


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

linyunxian

回复 10# OwnWaterloo


    是的，这条语句阻止了gcc的优化。但逻辑上来说，似乎它仍可以做到。