什么是尾递归？

Question

什么是尾递归？

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

Answer 1

考虑一个添加前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(4, 5)tailrecsum(3, 9)tailrecsum(2, 12)tailrecsum(1, 14)tailrecsum(0, 15)15在尾递归的情况下，每次递归调用的评估running_total都会更新。注意：原始答案使用了Python中的示例。这些已经改为JavaScript，因为现代JavaScript解释器支持尾调用优化，但Python解释器不支持。

Answer 2

重要的一点是尾递归基本上等于循环。这不仅仅是编译器优化的问题，而是表达性的基本事实。这有两种方式：你可以采取任何形式的循环while(E)&nbsp;{&nbsp;S&nbsp;};&nbsp;return&nbsp;Qwhere&nbsp;E和Q是表达式，S是一系列语句，并将其转换为尾递归函数f()&nbsp;=&nbsp;if&nbsp;E&nbsp;then&nbsp;{&nbsp;S;&nbsp;return&nbsp;f()&nbsp;}&nbsp;else&nbsp;{&nbsp;return&nbsp;Q&nbsp;}当然，E，S，和Q必须定义来计算对一些变量的一些有趣的价值。例如，循环函数sum(n)&nbsp;{ &nbsp;&nbsp;int&nbsp;i&nbsp;=&nbsp;1,&nbsp;k&nbsp;=&nbsp;0; &nbsp;&nbsp;while(&nbsp;i&nbsp;<=&nbsp;n&nbsp;)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;k&nbsp;+=&nbsp;i; &nbsp;&nbsp;&nbsp;&nbsp;++i; &nbsp;&nbsp;} &nbsp;&nbsp;return&nbsp;k;}相当于尾递归函数sum_aux(n,i,k)&nbsp;{ &nbsp;&nbsp;if(&nbsp;i&nbsp;<=&nbsp;n&nbsp;)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;sum_aux(n,i+1,k+i); &nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;k; &nbsp;&nbsp;}}sum(n)&nbsp;{ &nbsp;&nbsp;return&nbsp;sum_aux(n,1,0);}（这种带有参数较少的函数的尾递归函数的“包装”是一种常见的功能习惯。）