什么是尾递归？
在开始学习lisp的同时，我遇到了tail-recursive这个术语。 这究竟意味着什么？
考虑添加前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)会发生的事件序列。
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解释器不支持。
在传统的递归中 ，典型的模型是先执行递归调用，然后获取递归调用的返回值并计算结果。 以这种方式，直到您从每次递归调用返回后，才会得到计算结果。
在尾递归中 ，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。 这导致最后一条语句的形式是“（return（recursive-function params））”（我认为这是Lisp的语法）。 基本上，任何给定的递归步骤的返回值都与下一个递归调用的返回值相同 。
这样做的结果是，一旦准备好执行下一个递归步骤，就不再需要当前的堆栈帧。 这允许一些优化。 事实上，使用适当的编译器，你不应该有一个带有尾递归调用的堆栈溢出snicker。 只需重新使用当前的堆栈帧进行下一个递归步骤即可。 我很确定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;
}
相当于尾递归函数（s）
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);
}
（使用带较少参数的函数对尾递归函数进行“包装”是一种常见的功能方式。）
链接地址: http://www.djcxy.com/p/249.html