c++ - 尾递归如何真正帮助传统递归？

Question

我在阅读尾递归和传统递归之间的区别时发现它提到“然而，尾递归是一种不使用任何堆栈空间的递归形式，因此是一种安全使用递归的方法。” '

我正在努力理解如何做。

比较使用传统递归和尾递归查找数字的阶乘

传统递归

/* 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;
}

正如您所见，每次迭代都会重复使用堆栈空间。

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