在开始学习 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 解释器不支持 tail call optimization .然而,虽然尾调用优化是 part of the ECMAScript 2015 spec , 大多数 JavaScript 解释器 don't support it .
关于algorithm - 什么是尾递归?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33923/