什么是尾递归？

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) { S }; return Q

where 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;}

相当于尾递归函数

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);}

（这种带有参数较少的函数的尾递归函数的“包装”是一种常见的功能习惯。）