尾递归如何真正有助于传统的递归？

Question

我正在阅读尾递归和传统递归之间的区别,并发现它提到"Tail Recursion然而是一种不使用任何堆栈空间的递归形式,因此是一种安全使用递归的方法."

我很难理解如何.

使用Traditional和tail递归比较数字的发现阶乘

传统的递归

/* traditional recursion */
fun(5);


int fun(int n)
{
 if(n == 0)
  return 1;


 return n * fun(n-1);
}

这里,调用堆栈看起来像

5 * fact(4)
      |
   4 * fact(3)
          |
       3 * fact(2)
             |
         2 * fact(1)
               |
            1 * fact(0)
                  |
                  1

尾递归

/* tail recursion */
fun(5,1)


int fun(int n, int sofar)
{
 int ret = 0;


 if(n == 0)
  return sofar;


 ret = fun(n-1,sofar*n);


 return ret;
}

然而,即使在这里,变量'sofar'将在不同点保持 - 5,20,60,120,120.但是一旦从递归调用#4的基本情况调用return,它仍然必须返回120到递归调用#3,然后返回到#2,#1并返回到main.所以,我的意思是说使用堆栈并且每次返回上一次调用时,都可以看到该时间点的变量,这意味着它在每一步都被保存.

除非,尾递归写得如下,我无法理解它是如何节省堆栈空间的.

/* tail recursion */
fun(5,1)

int fun(int n, int sofar)
{
 int ret = 0;


 if(n == 0)
  return 'sofar' back to main function, stop recursing back; just a one-shot return


 ret = fun(n-1,sofar*n);


 return ret;
}

PS:我已经阅读了SO上的几个线程,并开始了解尾递归是什么,但是,这个问题与它为什么节省堆栈空间更相关.在讨论这个问题时,我找不到类似的问题.

Answer 1

诀窍是如果编译器注意到尾递归,它可以编译一个goto.它将生成类似以下代码的内容:

int fun_optimized(int n, int sofar)
{
start:
    if(n == 0)
       return sofar;

    sofar = sofar*n;
    n = n-1;
    goto start;
}

正如您所看到的,堆栈空间会在每次迭代时重用.

请注意,只有在递归调用是函数中的最后一个操作时才能进行此优化,即尾递归(尝试手动执行非尾部情况,您将看到这是不可能的).