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

Question

我正在阅读尾递归和传统递归之间的区别，发现它提到 "Tail Recursion however is a form of recursion that doesn’t use any stack space, and thus is a way to use recursion safely."'

我很难理解。

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

传统递归

/* 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，它仍然必须 return120 到递归调用#3，然后到#2、#1 并返回到 main。所以，我的意思是说堆栈被使用了，每次你return到上一个调用，那个时间点的变量都可以看到，这意味着它在每一步都被保存。

除非尾递归像下面这样写，否则我无法理解它是如何节省堆栈的space。

/* 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 的线程并开始理解什么是尾递归，但是，这个问题更多地与它为什么节省堆栈 space 有关。我在讨论这个的地方找不到类似的问题。

Answer 1

诀窍在于，如果编译器注意到尾递归，它可以编译 goto。它将生成类似于以下代码的内容：

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

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

如您所见，堆栈 space 被重复用于每次迭代。

请注意，只有当递归调用是函数中的最后一个动作时才能进行此优化，即 尾递归（尝试对非尾递归手动执行案例，你会发现这是不可能的）。

Answer 2

当函数调用（递归）作为最终操作执行时，函数调用是尾递归的。 由于当前递归实例已在此时完成执行，因此无需维护其堆栈帧。

在这种情况下，在当前栈帧之上创建一个栈帧无异于浪费。
当编译器将递归识别为尾递归时，它不会为每个调用创建嵌套堆栈帧，而是使用当前堆栈帧。这实际上等同于 goto 语句。这使得该函数调用迭代而不是递归。

请注意，在传统递归中，每次递归调用都必须在编译器执行乘法运算之前完成：

fun(5)
5 * fun(4)
5 * (4 * fun(3))
5 * (4 * (3 * fun(2)))
5 * (4 * (3 * (2 * fun(1))))
5 * (4 * (3 * (2 * 1)))
120

在这种情况下需要嵌套堆栈框架。查看 wiki 了解更多信息。

在尾递归的情况下，每次调用 fun，变量 sofar 都会更新：

fun(5, 1)
fun(4, 5)
fun(3, 20)
fun(2, 60)
fun(1, 120)
120

不需要保存当前递归调用的栈帧。

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

How does tail recursion really help over traditional recursion?

c

c++

recursion

tail-recursion