在开始学习 lisp 时,我遇到了tail-recursive一词。究竟是什么意思?
考虑一个简单的函数,它将前 N 个自然数相加。(例如sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15)。
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)
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)
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