algorithm - 什么是尾递归？

Question

在开始学习 lisp 时，我遇到了tail-recursive一词。究竟是什么意思？

score 1948 · Accepted Answer

考虑一个简单的函数，它将前 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 解释器不支持尾调用优化。然而，虽然尾调用优化是ECMAScript 2015 规范的一部分，但大多数 JavaScript 解释器并不支持它。

score 791 · Accepted Answer

在传统的递归中，典型的模型是先执行递归调用，然后获取递归调用的返回值并计算结果。以这种方式，在您从每个递归调用返回之前，您不会得到计算结果。

在尾递归中，您首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句采用(return (recursive-function params)). 基本上，任何给定递归步骤的返回值与下一个递归调用的返回值相同。

这样做的结果是，一旦您准备好执行下一个递归步骤，您就不再需要当前的堆栈帧。这允许进行一些优化。事实上，使用适当编写的编译器，您永远不应该有一个带有尾递归调用的堆栈溢出窃笑。只需将当前堆栈帧重用于下一个递归步骤。我很确定 Lisp 可以做到这一点。

score 224 · Accepted Answer

重要的一点是尾递归本质上等同于循环。这不仅仅是编译器优化的问题，而是关于表现力的基本事实。这是双向的：您可以采用任何形式的循环

while(E) { S }; return Q

where EandQ是表达式 andS是语句序列，并将其变成尾递归函数

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

（这种尾递归函数与参数较少的函数的“包装”是一种常见的函数式习惯用法。）

score 163 · Accepted Answer

这段摘自《Lua 编程》一书的摘录展示了如何进行适当的尾递归（在 Lua 中，但也应适用于 Lisp）以及为什么它更好。

尾调用[tail recursion] 是一种伪装成调用的 goto。当一个函数调用另一个函数作为其最后一个操作时，就会发生尾调用，因此它没有其他事情可做。例如，在下面的代码中，调用g是尾调用：
function f (x)
  return g(x)
end
f调用后g，它没有其他事情可做。在这种情况下，程序不需要在被调用函数结束时返回调用函数。因此，在尾调用之后，程序不需要在堆栈中保留任何有关调用函数的信息。...

因为正确的尾调用不使用堆栈空间，所以程序可以进行的“嵌套”尾调用的数量没有限制。例如，我们可以使用任意数字作为参数调用以下函数；它永远不会溢出堆栈：
function foo (n)
  if n > 0 then return foo(n - 1) end
end
... 正如我之前所说，尾调用是一种 goto。因此，在 Lua 中正确尾调用的一个非常有用的应用是编程状态机。这样的应用程序可以用一个函数来表示每个状态；改变状态是去（或调用）一个特定的功能。例如，让我们考虑一个简单的迷宫游戏。迷宫有几个房间，每个房间最多有四个门：北，南，东，西。在每一步，用户输入一个移动方向。如果那个方向有门，用户就去对应的房间；否则，程序会打印警告。目标是从初始房间进入最终房间。

这个游戏是一个典型的状态机，当前房间就是状态。我们可以为每个房间使用一个功能来实现这样的迷宫。我们使用尾调用从一个房间移动到另一个房间。一个有四个房间的小迷宫可能是这样的：
function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

所以你看，当你进行递归调用时：

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

这不是尾递归，因为在进行递归调用之后，您在该函数中仍有事情要做（加 1）。如果您输入一个非常高的数字，它可能会导致堆栈溢出。

score 85 · Accepted Answer

使用常规递归，每个递归调用将另一个条目推入调用堆栈。递归完成后，应用程序必须将每个条目一直弹出。

使用尾递归，根据语言，编译器可能能够将堆栈折叠为一个条目，因此您可以节省堆栈空间......大型递归查询实际上会导致堆栈溢出。

基本上尾递归能够被优化成迭代。

score 78 · Accepted Answer

行话文件对尾递归的定义有这样的说法：

尾递归/n./

如果您还没有厌倦它，请参阅尾递归。

score 73 · Accepted Answer

与其用文字来解释，不如举个例子。这是阶乘函数的 Scheme 版本：

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

这是尾递归的阶乘版本：

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

您会注意到在第一个版本中，对 fact 的递归调用被馈送到乘法表达式中，因此在进行递归调用时必须将状态保存在堆栈中。在尾递归版本中，没有其他 S 表达式等待递归调用的值，并且由于没有进一步的工作要做，因此不必将状态保存在堆栈中。作为一项规则，Scheme 尾递归函数使用常量堆栈空间。

score 53 · Accepted Answer

尾递归是指递归调用在递归算法中最后一条逻辑指令中的最后一个。

通常在递归中，您有一个基本情况，即停止递归调用并开始弹出调用堆栈。举一个经典的例子，尽管比 Lisp 更 C-ish，阶乘函数说明了尾递归。递归调用发生在检查基本情况条件之后。

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

对阶乘的初始调用将是factorial(n)where fac=1（默认值），n 是要计算阶乘的数字。

score 29 · Accepted Answer

这意味着不需要将指令指针压入堆栈，您可以简单地跳转到递归函数的顶部并继续执行。这允许函数无限地递归而不会溢出堆栈。

我写了一篇关于该主题的博客文章，其中包含堆栈框架外观的图形示例。

score 22 · Accepted Answer

这是一个比较两个函数的快速代码片段。第一个是传统的递归，用于找到给定数字的阶乘。第二个使用尾递归。

非常简单直观的理解。

判断递归函数是否为尾递归的一种简单方法是它是否在基本情况下返回具体值。这意味着它不会返回 1 或 true 或类似的东西。它很可能会返回方法参数之一的一些变体。

另一种方法是判断递归调用是否没有任何加法、算术、修改等......这意味着它只是一个纯粹的递归调用。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

score 21 · Accepted Answer

我理解的最好方法tail call recursion是递归的一个特殊情况，其中最后一次调用（或尾部调用）是函数本身。

比较 Python 中提供的示例：

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^递归

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾递归

正如您在通用递归版本中看到的那样，代码块中的最终调用是x + recsum(x - 1). 所以调用该recsum方法之后，还有另一个操作是x + ...

但是，在尾递归版本中，代码块中的最终调用（或尾调用）tailrecsum(x - 1, running_total + x)意味着最后一次调用是对方法本身进行的，之后没有任何操作。

这一点很重要，因为这里看到的尾递归不会使内存增长，因为当底层 VM 看到一个函数在尾位置（函数中要计算的最后一个表达式）调用自身时，它会消除当前堆栈帧，这称为尾调用优化 (TCO)。

编辑

注意。请记住，上面的示例是用 Python 编写的，其运行时不支持 TCO。这只是解释这一点的一个例子。Scheme、Haskell 等语言支持 TCO

score 13 · Accepted Answer

在 Java 中，这是斐波那契函数的一个可能的尾递归实现：

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

将此与标准递归实现进行对比：

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

score 12 · Accepted Answer

我不是 Lisp 程序员，但我认为这会有所帮助。

基本上它是一种编程风格，递归调用是你做的最后一件事。

score 12 · Accepted Answer

递归函数是一个自己调用的函数

它允许程序员使用最少的代码编写高效的程序。

不利的一面是，如果编写不当，它们可能会导致无限循环和其他意外结果。

我将解释简单递归函数和尾递归函数

为了写一个简单的递归函数

要考虑的第一点是什么时候应该决定退出 if 循环
第二个是如果我们是自己的函数要做什么流程

从给定的例子：

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

从上面的例子

if(n <=1)
     return 1;

是何时退出循环的决定因素

else 
     return n * fact(n-1);

是否要进行实际处理

让我一一分解任务以便于理解。

让我们看看如果我运行内部会发生什么fact(4)

代入 n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If循环失败，所以它进入else循环，所以它返回4 * fact(3)

在堆栈内存中，我们有4 * fact(3)

代入 n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If循环失败，所以它进入else循环

所以它返回3 * fact(2)

记住我们调用了```4 * fact(3)`

输出为fact(3) = 3 * fact(2)

到目前为止，堆栈有4 * fact(3) = 4 * 3 * fact(2)

在堆栈内存中，我们有4 * 3 * fact(2)

代入 n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If循环失败，所以它进入else循环

所以它返回2 * fact(1)

记得我们打电话4 * 3 * fact(2)

输出为fact(2) = 2 * fact(1)

到目前为止，堆栈有4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

在堆栈内存中，我们有4 * 3 * 2 * fact(1)

代入 n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If循环是真的

所以它返回1

记得我们打电话4 * 3 * 2 * fact(1)

输出为fact(1) = 1

到目前为止，堆栈有4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

最后，fact(4) = 4 * 3 * 2 * 1 = 24

尾递归将是

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

代入 n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If循环失败，所以它进入else循环，所以它返回fact(3, 4)

在堆栈内存中，我们有fact(3, 4)

代入 n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If循环失败，所以它进入else循环

所以它返回fact(2, 12)

在堆栈内存中，我们有fact(2, 12)

代入 n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If循环失败，所以它进入else循环

所以它返回fact(1, 24)

在堆栈内存中，我们有fact(1, 24)

代入 n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If循环是真的

所以它返回running_total

输出为running_total = 24

最后，fact(4,1) = 24的结果

score 10 · Accepted Answer

这是一个使用尾递归进行阶乘的 Common Lisp 示例。由于无堆栈的性质，人们可以执行非常大的阶乘计算......

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

然后为了好玩你可以试试(format nil "~R" (! 25))

score 10 · Accepted Answer

尾递归函数是一个递归函数，它在返回之前执行的最后一个操作是进行递归函数调用。即立即返回递归函数调用的返回值。例如，您的代码如下所示：

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

实现尾调用优化或尾调用消除的编译器和解释器可以优化递归代码以防止堆栈溢出。如果您的编译器或解释器没有实现尾调用优化（例如 CPython 解释器），那么以这种方式编写代码没有额外的好处。

例如，这是 Python 中的标准递归阶乘函数：

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

这是阶乘函数的尾调用递归版本：

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

（请注意，即使这是 Python 代码，CPython 解释器也不会进行尾调用优化，因此像这样安排代码不会带来运行时优势。）

您可能必须使代码更难读才能使用尾调用优化，如阶乘示例中所示。（例如，基本情况现在有点不直观，accumulator参数被有效地用作一种全局变量。）

但是尾调用优化的好处是它可以防止堆栈溢出错误。（我会注意到，您可以通过使用迭代算法而不是递归算法来获得同样的好处。）

当调用堆栈有太多的框架对象被压入时，会导致堆栈溢出。一个框架对象在函数被调用时被压入调用栈，并在函数返回时从调用栈中弹出。框架对象包含诸如局部变量和函数返回时要返回的代码行等信息。

如果您的递归函数在没有返回的情况下进行了太多递归调用，则调用堆栈可能会超出其帧对象限制。（数量因平台而异；在 Python 中默认为 1000 个框架对象。）这会导致堆栈溢出错误。（嘿，这就是这个网站的名字的由来！）

然而，如果你的递归函数做的最后一件事是进行递归调用并返回它的返回值，那么它没有理由需要保持当前帧对象需要留在调用堆栈上。毕竟，如果递归函数调用之后没有代码，就没有理由挂在当前帧对象的局部变量上。因此我们可以立即摆脱当前的帧对象，而不是将其保留在调用堆栈中。这样做的最终结果是您的调用堆栈的大小不会增长，因此不会堆栈溢出。

编译器或解释器必须将尾调用优化作为一项功能，以便能够识别何时可以应用尾调用优化。即便如此，您可能已经重新排列递归函数中的代码以利用尾调用优化，而这种潜在的可读性降低是否值得优化取决于您。

score 9 · Accepted Answer

简而言之，尾递归将递归调用作为函数中的最后一条语句，因此它不必等待递归调用。

所以这是一个尾递归，即 N(x - 1, p * x) 是函数中的最后一条语句，编译器很聪明地发现它可以优化为 for 循环（阶乘）。第二个参数 p 携带中间产品值。

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

这是编写上述阶乘函数的非尾递归方式（尽管一些 C++ 编译器可能无论如何都能够对其进行优化）。

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

但这不是：

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

我确实写了一篇题为“了解尾递归 - Visual Studio C++ - 汇编视图”的长文

score 8 · Accepted Answer

tailrecsum这是前面提到的函数的 Perl 5 版本。

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

score 8 · Accepted Answer

这是关于尾递归的计算机程序结构和解释的摘录。

在对比迭代和递归时，我们必须注意不要将递归过程的概念与递归过程的概念混淆。当我们将过程描述为递归时，我们指的是过程定义（直接或间接）引用过程本身的句法事实。但是，当我们将过程描述为遵循某种模式时，例如线性递归，我们是在谈论过程如何演变，而不是在讨论如何编写过程的语法。我们将诸如 fact-iter 之类的递归过程称为生成迭代过程似乎令人不安。然而，这个过程确实是迭代的：它的状态完全由它的三个状态变量捕获，解释器只需要跟踪三个变量就可以执行这个过程。

进程和过程之间的区别可能令人困惑的一个原因是，大多数通用语言（包括 Ada、Pascal 和 C）的实现都是这样设计的，即任何递归过程的解释都会消耗大量内存，该内存量会随着过程调用的数量，即使所描述的过程原则上是迭代的。因此，这些语言只能通过使用诸如 do、repeat、until、for 和 while 等特殊用途的“循环结构”来描述迭代过程。Scheme 的实现没有这个缺陷。即使迭代过程由递归过程描述，它将在恒定空间中执行迭代过程。具有此属性的实现称为尾递归。使用尾递归实现，可以使用普通的过程调用机制来表示迭代，因此特殊的迭代构造仅用作语法糖。

score 8 · Accepted Answer

尾递归就是你现在的生活。您不断地循环使用相同的堆栈帧，因为没有理由或方法返回到“前一个”帧。过去已经过去了，所以它可以被丢弃。你得到一帧，永远移动到未来，直到你的过程不可避免地死亡。

_{当您考虑到某些进程可能会使用额外的帧但如果堆栈没有无限增长时仍被认为是尾递归时，这个类比就失效了。}

score 8 · Accepted Answer

尾递归是一个递归函数，其中函数在函数的末尾（“尾”）调用自身，在递归调用返回后不进行任何计算。许多编译器优化以将递归调用更改为尾递归或迭代调用。

考虑计算一个数的阶乘问题。

一个简单的方法是：

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

假设您调用阶乘（4）。递归树将是：

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1

上述情况下的最大递归深度为 O(n)。

但是，请考虑以下示例：

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

factTail(4) 的递归树将是：

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

在这里，最大递归深度也是 O(n)，但没有一个调用将任何额外的变量添加到堆栈中。因此编译器可以取消堆栈。

score 7 · Accepted Answer

与普通递归相比，尾递归相当快。它很快，因为祖先调用的输出不会被写入堆栈以保持跟踪。但在正常递归中，所有祖先调用输出写入堆栈以保持跟踪。

score 6 · Accepted Answer

要了解尾调用递归和非尾调用递归之间的一些核心区别，我们可以探索这些技术的 .NET 实现。

这是一篇文章，其中包含 C#、F# 和 C++\CLI 中的一些示例：C#、F# 和 C++\CLI中的尾递归冒险。

C# 不针对尾调用递归进行优化，而 F# 可以。

原理的差异涉及循环与 Lambda 演算。C# 在设计时考虑了循环，而 F# 是根据 Lambda 演算原理构建的。有关 Lambda 演算原理的非常好的（免费）书籍，请参阅Abelson、Sussman 和 Sussman 的计算机程序的结构和解释。

关于 F# 中的尾调用，一篇非常好的介绍性文章，请参阅F# 中的尾调用详细介绍。最后，这里有一篇文章介绍了非尾递归和尾调用递归（在 F# 中）之间的区别：Tail-recursion vs. non-tail recursion in F sharp。

如果您想了解 C# 和 F# 之间尾调用递归的一些设计差异，请参阅在 C# 和 F# 中生成尾调用操作码。

如果您想知道哪些条件会阻止 C# 编译器执行尾调用优化，请参阅这篇文章：JIT CLR 尾调用条件。

score 5 · Accepted Answer

递归意味着一个函数调用自己。例如：

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion 表示结束函数的递归：

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

看，未结束的函数（程序，在方案行话中）所做的最后一件事就是调用自己。另一个（更有用的）示例是：

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

在辅助过程中，如果 left 不是 nil，它所做的最后一件事是调用自身（在 cons 和 cdr 之后）。这基本上是您映射列表的方式。

尾递归具有很大的优势，解释器（或编译器，取决于语言和供应商）可以对其进行优化，并将其转换为等效于 while 循环的东西。事实上，在 Scheme 传统中，大多数“for”和“while”循环都是以尾递归方式完成的（据我所知，没有 for 和 while）。

score 4 · Accepted Answer

递归有两种基本类型：头递归和尾递归。

在head recursion中，函数进行递归调用，然后执行更多计算，例如，可能使用递归调用的结果。

在尾递归函数中，所有计算首先发生，递归调用是最后发生的事情。

取自这篇超级棒的帖子。请考虑阅读它。

score 4 · Accepted Answer

如果每个递归案例仅包含对函数本身的调用，则函数是尾递归的，可能带有不同的参数。或者，尾递归是没有待处理工作的递归。请注意，这是一个独立于编程语言的概念。

考虑定义为的函数：

g(a, b, n) = a * b^n

一个可能的尾递归公式是：

g(a, b, n) | n is zero = a
           | n is odd  = g(a*b, b,   n-1)
           | otherwise = g(a,   b*b, n/2)

如果您检查g(...)其中涉及递归案例的每个 RHS，您会发现 RHS 的整个主体都是对的调用g(...)，并且仅此而已。这个定义是尾递归的。

为了比较，非尾递归公式可能是：

g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
        | n is odd  = f(b, n-1) * b
        | otherwise = f(b, n/2) ^ 2

每个递归案例f(...)都有一些待处理的工作需要在递归调用之后进行。

请注意，当我们从g'到时g，我们基本使用了乘法的结合性（和交换性）。这不是偶然的，大多数需要将递归转换为尾递归的情况都会使用这些属性：如果我们想急切地做一些工作而不是让它等待，我们必须使用关联性之类的东西来证明答案将是相同的。

尾递归调用可以通过向后跳转来实现，而不是使用堆栈进行正常的递归调用。请注意，检测尾调用或发出向后跳转通常很简单。但是，通常很难重新排列参数以使向后跳转成为可能。由于这种优化不是免费的，语言实现可以选择不实现这种优化，或者通过使用“tailcall”指令标记递归调用和/或选择更高的优化设置来选择加入。

但是，某些语言（例如 Scheme）确实需要所有实现来优化尾递归函数，甚至可能所有调用都在尾位置。

在大多数命令式语言中，向后跳转通常被抽象为（while）循环，而尾递归在优化为向后跳转时，与循环同构。

score 3 · Accepted Answer

这个问题有很多很好的答案......但我不禁提出了另一种关于如何定义“尾递归”或至少“正确的尾递归”的看法。即：是否应该将其视为程序中特定表达式的属性？还是应该将其视为编程语言实现的属性？

关于后一种观点的更多信息，Will Clinger 的经典论文“Proper Tail Recursion and Space Efficiency”（PLDI 1998）将“正确的尾递归”定义为编程语言实现的属性。该定义被构造为允许忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链表表示）。

为了做到这一点，它使用渐近分析：不是人们通常看到的程序执行时间，而是程序空间使用情况。这样，堆分配的链表与运行时调用堆栈的空间使用最终是渐近等效的；所以人们会忽略编程语言的实现细节（这个细节在实践中肯定很重要，但是当人们试图确定给定的实现是否满足“属性尾递归”的要求时，它可能会变得很混乱)

这篇论文值得仔细研究，原因有很多：

它给出了程序尾部表达式和尾部调用的归纳定义。（这样的定义，以及为什么这样的调用很重要，似乎是这里给出的大多数其他答案的主题。）

以下是这些定义，只是为了提供文本的味道：
定义1用Core Scheme 编写的程序的尾部表达式归纳定义如下。
1. lambda 表达式的主体是尾表达式
2. 如果(if E0 E1 E2)是尾表达式，则E1和E2都是尾表达式。
3. 没有其他东西是尾巴表达。
定义 2尾调用是一个尾表达式，它是一个过程调用。

（尾递归调用，或者正如论文所说，“自尾调用”是尾调用的一种特殊情况，其中过程本身被调用。）

它为评估核心方案的六种不同“机器”提供了正式定义，其中每台机器具有相同的可观察行为，除了每个机器所在的渐近空间复杂度类。

例如，在给出了分别具有 1. 基于堆栈的内存管理、2. 垃圾收集但没有尾调用、3. 垃圾收集和尾调用的机器的定义之后，本文继续介绍了更高级的存储管理策略，例如4. “evlis tail recursion”，不需要在尾部调用中对最后一个子表达式参数的求值过程中保留环境， 5. 将闭包的环境简化为该闭包的自由变量，以及6. Appel 和 Shao定义的所谓“空间安全”语义。
为了证明这些机器实际上属于六个不同的空间复杂度类别，该论文针对每一对被比较的机器，提供了具体的程序示例，这些程序将在一台机器上暴露渐近空间爆炸而不是另一台机器。

（现在阅读我的答案，我不确定我是否能够真正抓住Clinger 论文的关键点。但是，唉，我现在不能花更多的时间来开发这个答案。）

score 3 · Accepted Answer

很多人已经在这里解释了递归。我想引用 Riccardo Terrell 所著的“.NET 中的并发，并发和并行编程的现代模式”一书中关于递归带来的一些优势的一些想法：

“函数递归是在 FP 中迭代的自然方式，因为它避免了状态的突变。在每次迭代期间，将一个新值传递给循环构造函数，而不是进行更新（变异）。此外，可以组合递归函数，使您的程序更加模块化，并引入利用并行化的机会。”

以下是同一本书中关于尾递归的一些有趣的注释：

尾调用递归是一种将常规递归函数转换为可以处理大量输入而没有任何风险和副作用的优化版本的技术。

注意尾调用作为优化的主要原因是改善数据局部性、内存使用和缓存使用。通过尾调用，被调用者使用与调用者相同的堆栈空间。这减少了内存压力。它略微改进了缓存，因为相同的内存被后续调用者重用并且可以保留在缓存中，而不是驱逐旧的缓存行来为新的缓存行腾出空间。

score 1 · Accepted Answer

它是一种特殊形式的递归，其中函数的最后一个操作是递归调用。通过在当前堆栈帧中执行调用并返回其结果而不是创建新的堆栈帧，可以优化递归。

当递归调用是函数执行的最后一件事时，递归函数是尾递归的。例如，以下 C++ 函数 print() 是尾递归的。

尾递归函数的一个例子

    void print(int n) 
{ 
if (n < 0)  return; 
cout << " " << n; 
print(n-1);} 



// The last executed statement is recursive call

尾递归函数被认为比非尾递归函数更好，因为尾递归可以由编译器优化。编译器用来优化尾递归函数的想法很简单，因为递归调用是最后一条语句，当前函数中没有什么可做的，所以保存当前函数的堆栈帧是没有用的。

score 0 · Accepted Answer

0

递归就是递归，或多或少。尾递归或多或少是尾递归。

于 2022-03-03T09:15:52.823 回答

algorithm - 什么是尾递归？

30 回答 30

编辑

Related

Reference