什么是尾递归？

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

考虑一个将前 N 个自然数相加的简单函数。 （例如。sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).

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

function recsum(x) {
    if (x === 0) {
        return 0;
    } 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 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
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(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾递归情况下，每次对递归调用求值时，running_total已更新。

注意：原始答案使用了 Python 中的示例。这些已更改为 JavaScript，因为 Python 解释器不支持尾调用优化 https://stackoverflow.com/questions/310974/what-is-tail-call-optimization。然而，虽然尾调用优化是ECMAScript 2015 规范的一部分 https://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls, 大多数 JavaScript 解释器不支持 https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation).