协慌网

在开始学习 lisp 时，我遇到了尾递归这个术语。这究竟是什么意思？

考虑一个添加前 N 个整数的简单函数。 （例如， sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ）。

这是一个使用递归的简单 JavaScript 实现：

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

如果你调用了recsum(5) ，这就是 JavaScript 解释器会评估的内容：

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

请注意每个递归调用必须在 JavaScript 解释器开始实际执行计算总和之前完成。

这是同一函数的尾递归版本：

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

以下是调用tailrecsum(5)会发生的事件序列tailrecsum(5, 0)由于默认的第二个参数，它实际上是tailrecsum(5, 0) ））。

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归的情况下，每次递归调用的running_total都会更新running_total 。

注意：原始答案使用了 Python 中的示例。这些已经改为 JavaScript，因为现代 JavaScript 解释器支持尾调用优化，但 Python 解释器不支持。

在传统的递归中 ，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。以这种方式，在每次递归调用返回之前，您不会得到计算结果。

在尾递归中 ，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。这导致最后一个语句采用(return (recursive-function params)) 。 基本上，任何给定递归步骤的返回值与下一个递归调用的返回值相同 。

这样做的结果是，一旦准备好执行下一个递归步骤，就不再需要当前的堆栈帧了。这允许一些优化。事实上，使用适当编写的编译器，您应该永远不会有带尾递归调用的堆栈溢出窃听器 。只需重复使用当前堆栈帧进行下一个递归步骤。我很确定 Lisp 会这样做。

重要的一点是尾递归基本上等于循环。这不仅仅是编译器优化的问题，而是表达性的基本事实。这有两种方式：你可以采取任何形式的循环

while(E) { S }; return Q

其中E和Q是表达式， S是一系列语句，并将其转换为尾递归函数

f() = if E then { S; return f() } else { return Q }

当然，必须定义E ， S和Q来计算某些变量的一些有趣值。例如，循环函数

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

相当于尾递归函数

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

（这种带有参数较少的函数的尾递归函数的 “包装” 是一种常见的功能习惯。）