什么是尾递归？

Question

在开始学习Lisp时，我遇到了术语尾递归。它确切指的是什么？

- Ben Lever

---

也许有点晚，但这是一篇很好的关于尾递归的文章：http://www.programmerinterview.com/index.php/recursion/tail-recursion/ - Sam003

识别尾递归函数的一个巨大优点是，可以将其转换为迭代形式，从而减轻算法的方法栈开销。建议查看下@Kyle Cronin以及下面其他人的回答。 - KGhatak

有人能告诉我，归并排序和快速排序是否使用尾递归（TRO）？ - majurageerthan

@majurageerthan - 这取决于特定的算法实现（包括其他任何算法）。 - Bob Jarvis - Слава Україні

https://www.youtube.com/watch?v=-PX0BV9hGZY =) - Abhijit

Answer 1

考虑一个简单的函数，它将前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解释器不支持它。

- lorin

---

使用尾递归，最终答案仅由方法的最后一次调用计算。如果不使用尾递归，则需要所有方法的结果才能计算答案。 - chrisapotek

这里有一个附录，展示了一些Lua的例子：http://www.lua.org/pil/6.3.html也许阅读一下会很有用！ :) - yesudeep

有人能否回答chrisapotek的问题？我不明白在一种不优化尾调用的语言中如何实现“尾递归”。 - Kevin Meredith

“尾递归”是指函数中最后一个语句是对同一函数的递归调用。你说的没错，在那些不能优化递归的语言中这样做毫无意义。尽管如此，这个答案几乎正确地阐述了这个概念。如果省略掉“else:”，它会更明确地表示为尾调用，不会改变行为，但是会将尾调用作为独立语句放置。我会将其作为编辑提交。 - ToolmakerSteve

关于答案末尾的注释：只有苹果的JavaScriptCore实现了尾调用优化（TCO），V8（在Chrome、Chromium、Node.js等中使用）、SpiderMonkey（Firefox等）和Chakra（Edge，目前为止）不支持也没有计划支持，即使它在规范中。因此，在桌面上，只有Safari支持TCO。（在iOS上，Chrome、Firefox和其他浏览器支持，因为它们被迫使用JavaScriptCore而不是自己的引擎，因为非苹果应用程序无法分配可执行内存。V8正在添加一个仅解释模式，他们可能会转向这个模式，但是......） - T.J. Crowder

Answer 2

在传统递归中，典型的模式是你首先执行递归调用，然后取递归调用的返回值计算结果。以这种方式，只有在从每个递归调用返回后才能得到计算结果。

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

其结果是，一旦您准备好执行下一个递归步骤，您就不再需要当前的堆栈帧。这样可以进行一些优化。实际上，通过适当编写编译器，尾递归调用应该永远不会出现堆栈溢出问题（窃笑）。只需重复使用当前堆栈帧即可进行下一个递归步骤。我很确定Lisp会这样做。

- user316

---

我很确定Lisp能够做到这一点 -- Scheme可以，但Common Lisp并不总是如此。 - Aaron

@Daniel “基本上，任何给定递归步骤的返回值都与下一个递归调用的返回值相同。”-我不能理解这个论点对Lorin Hochstein发布的代码片段成立。您能否详细说明一下？ - Geek

@Geek 这是一个非常晚的回复，但这确实是Lorin Hochstein例子中的真理。每一步的计算都在递归调用之前完成，而不是之后。因此，每一步只需直接从上一步返回值。最后的递归调用完成计算，然后将最终结果不经修改地返回到调用栈底部。 - reirab

Scala确实支持尾递归，但需要使用@tailrec注解来强制执行。 - SilentDirge

以这种方式，只有在从每个递归调用返回后，您才能获得计算结果。也许我误解了这一点，但对于惰性语言来说并不特别正确，其中传统递归是唯一的方法，可以在不调用所有递归的情况下实际获得结果（例如，使用&&折叠无限布尔列表）。 - hasufell

Answer 3

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

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

相当于尾递归函数

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

(这种将尾递归函数“包装”成参数更少的函数的方法是一种常见的函数式习惯用法。)

- Chris Conway

---

在@LorinHochstein的回答中，根据他的解释，我理解尾递归是指递归部分跟随“Return”，但在你的例子中，尾递归并不是这样。你确定你的例子被正确地认为是尾递归吗？ - CodyBugstein

@Imray 尾递归部分是 sum_aux 内的 "return sum_aux" 语句。 - Chris Conway

@lmray：Chris的代码基本上是等效的。if/then的顺序和限制测试的样式...如果x == 0与if(i<=n)...不是要纠结的事情。关键是每次迭代都将其结果传递给下一个。 - Taylor

else { return k; } can be changed to return k; - c0der

@cOder，你说得没错，但人们来到stackoverflow也是为了学习，所以也许使用if和else会使它更易于理解，特别是对于初学者。 - Enrique René

但是为什么这样的过程被称为尾递归而不是头递归呢？ - Charlie Parker

Answer 4

这段摘自《Lua编程》一书的内容展示了如何实现正确的尾递归（在Lua中，但应该也适用于Lisp），以及为什么这样做更好。

A tail call [tail recursion] is a kind of goto dressed as a call. A tail call happens when a function calls another as its last action, so it has nothing else to do. For instance, in the following code, the call to g is a tail call:

function f (x)
  return g(x)
end

After f calls g, it has nothing else to do. In such situations, the program does not need to return to the calling function when the called function ends. Therefore, after the tail call, the program does not need to keep any information about the calling function in the stack. ...

Because a proper tail call uses no stack space, there is no limit on the number of "nested" tail calls that a program can make. For instance, we can call the following function with any number as argument; it will never overflow the stack:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... As I said earlier, a tail call is a kind of goto. As such, a quite useful application of proper tail calls in Lua is for programming state machines. Such applications can represent each state by a function; to change state is to go to (or to call) a specific function. As an example, let us consider a simple maze game. The maze has several rooms, each with up to four doors: north, south, east, and west. At each step, the user enters a movement direction. If there is a door in that direction, the user goes to the corresponding room; otherwise, the program prints a warning. The goal is to go from an initial room to a final room.

This game is a typical state machine, where the current room is the state. We can implement such maze with one function for each room. We use tail calls to move from one room to another. A small maze with four rooms could look like this:

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）。如果输入一个非常大的数，可能会导致堆栈溢出。

- Hoffmann

---

这个答案很棒，因为它解释了尾调用对栈大小的影响。 - Andrew Swan

@AndrewSwan，确实如此，尽管我认为原始提问者和偶然进入这个问题的读者可能更适合接受的答案（因为他可能不知道堆栈实际上是什么）。顺便说一下，我使用Jira，是个大粉丝。 - Hoffmann

我的最爱答案也是因为包含了堆栈大小的含义。 - njk2015

Answer 5

使用常规递归，每次递归调用都会将另一个条目推入调用堆栈中。当递归完成时，应用程序需要将每个条目弹出直到回到初始状态。 使用尾递归，根据语言，编译器可能能够将堆栈折叠为一个条目，因此可以节省堆栈空间...大型递归查询实际上可能会导致堆栈溢出。 基本上，尾递归能够优化为迭代。

- Jonathan Holland

---

一大型递归查询实际上可能会导致堆栈溢出，应该在第一段而不是第二个（尾递归）中提到。尾递归的最大优点是它可以被优化（例如Scheme），使得在堆栈中不会“积累”调用，因此大多数情况下避免了堆栈溢出！ - Olivier Dulac

Answer 6

术语文件对尾递归的定义如下：

尾递归 /n./

如果你还没有厌烦它，可以参考尾递归。

- Pat

---

有趣的是，行话文件条目实际上是尾递归的有效示例。一旦你满足了对尾递归厌倦的条件，你就不必遍历回到之前访问过尾递归定义的堆栈，以完成对定义的理解。你可以直接退出定义，继续你的生活。 - harperska

Answer 7

不用言语来解释它，这里提供一个示例。这是阶乘函数的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))))

在第一个版本中，您会注意到将递归调用传递到乘法表达式中，因此在进行递归调用时必须在堆栈上保存状态。在尾递归版本中，没有其他S表达式等待递归调用的值，由于没有进一步的工作要做，因此状态不必在堆栈上保存。通常，Scheme的尾递归函数使用恒定的堆栈空间。

- Kyle

---

提到尾递归最重要的一点就是它们可以转换为迭代形式，从而将其转化为O(1)内存复杂度形式。+1 - KGhatak

@KGhatak 不完全是这样；答案正确地谈到了“常量栈空间”，而不是内存总体。并非吹毛求疵，只是为了确保没有误解。例如，尾递归的list-tail-mutating list-reverse过程将在常量栈空间中运行，但会在堆上创建和增长数据结构。树遍历可以使用模拟栈，在额外的参数中实现等等。 - Will Ness

Answer 8

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

通常，在递归中，您需要一个基本情况(base-case)，它可以停止递归调用并开始弹出调用栈。使用一个经典的例子来说明，虽然更C风格而不是Lisp，阶乘函数说明了尾递归。在检查基本情况条件之后，递归调用发生。

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

对阶乘的最初调用应为factorial(n)，其中fac=1（默认值），n是要计算阶乘的数字。

- Peter Meyer

---

我发现你的解释最容易理解，但如果按照这个来说，那么尾递归只对具有一个语句基本情况的函数有用。考虑这样的方法https://postimg.cc/5Yg3Cdjn。注意：外部的“else”是您可能称之为“基本情况”的步骤，但跨越多行。我是否误解了你还是我的假设正确？尾递归只适用于一行代码吗？ - I Want Answers

@IWantAnswers - 不，函数的主体可以任意大。尾调用所需要的仅仅是该分支作为最后一件事情调用函数并返回调用函数的结果。factorial示例只是经典的简单示例，仅此而已。 - T.J. Crowder

Peter Meyer，就你的例子而言，运行时真的需要维护调用堆栈吗？@FlySwat - Supun Wijerathne

Answer 9

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

我写了一篇关于这个主题的博客文章，其中有图形示例展示堆栈帧的外观。

- Chris Smith

Answer 10

对于我来说理解尾递归最好的方法就是指特殊情况下的递归，其中最后一个调用(或尾递归)是函数本身。

比较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)，这意味着最后一次调用是对方法本身的调用，并且没有其他操作。

这一点很重要，因为如上所述的尾递归并不会使内存增长。当底层虚拟机看到函数在尾部位置（即函数中要评估的最后一个表达式）调用自身时，它会消除当前的堆栈帧，这就是尾调用优化(Tail Call Optimization, TCO)。

编辑

请注意，上面的示例是用 Python 编写的，而 Python 的运行时不支持 TCO。这只是一个例子，用于说明这一点。TCO 在 Scheme、Haskell 等语言中受到支持。

- Abhiroop Sarkar