什么是尾recursion？

在开始学习lisp的同时，我遇到了尾recursion的术语。 这到底意味着什么？

Answer 1

考虑一个简单的函数，添加前N个整数。 （例如， sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ）。

这是一个简单的Javascript实现，使用recursion：

 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解释器开始实际完成计算总和之前，每个recursion调用都必须完成。

这是一个相同函数的尾recursion版本：

 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 

在尾recursion的情况下，对recursion调用的每次评估都会更新running_total 。

注意：原始的答案使用Python的例子。 这些已被更改为Javascript，因为现代的Javascript解释器支持尾部调用优化，但Python解释器不支持。

Answer 2

在传统的recursion中 ，典型的模型是先执行recursion调用，然后再recursion调用的返回值并计算结果。 以这种方式，直到你从每次recursion调用返回，你都不会得到你的计算结果。

在尾recursion中 ，首先执行计算，然后执行recursion调用，将当前步骤的结果传递给下一个recursion步骤。 这导致最后一个语句的forms是“（return（recursive-function params））”（我认为这是Lisp的语法）。 基本上，任何给定的recursion步骤的返回值都与下一个recursion调用的返回值相同 。

这样做的结果是，一旦准备好执行下一个recursion步骤，就不再需要当前的堆栈框架了。 这允许一些优化。 实际上，使用适当的编译器编译器，你不应该有一个带有尾recursion调用的堆栈溢出snicker 。 只需重新使用当前的堆栈帧进行下一个recursion步骤即可。 我很确定Lisp这样做。

Answer 3

重要的一点是尾recursion本质上等同于循环。 这不仅仅是编译器优化的问题，而是expression性的基本事实。 这两种方式：你可以采取任何forms的循环

 while(E) { S }; return Q 

其中E和Q是expression式， S是一系列语句，并将其转换为尾recursion函数

 f() = if E then { S; return f() } else { return Q } 

当然，必须定义E ， S和Q来计算一些有趣的variables值。 例如，循环function

 sum(n) { int i = 1, k = 0; while( i <= n ) { k += i; ++i; } return k; } 

相当于尾recursion函数（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); } 

（使用带较less参数的函数对尾recursion函数进行“包装”是一个常见的function方法。）

Answer 4

Lua编程这本书的摘录显示了如何进行适当的尾recursion （在Lua中，但也应该适用于Lisp），以及为什么它更好。

一个尾巴呼叫 [尾recursion]是一种打扮成一个呼叫。 当一个函数调用另一个函数作为其最后一个动作时，就会发生尾部调用，所以没有别的办法了。 例如，在下面的代码中，对g的调用是一个尾部调用：

 function f (x) return g(x) end 

f调用g ，就没有别的事可做了。 在这种情况下，当被调用函数结束时，程序不需要返callback用函数。 因此，在尾部调用之后，程序不需要保存关于堆栈中的调用function的任何信息。 …

由于正确的尾部调用不使用堆栈空间，程序可以进行的“嵌套”尾部调用的数量没有限制。 例如，我们可以用任何数字作为参数来调用下面的函数。 它永远不会溢出堆栈：

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

正如我刚才所说，尾巴呼叫是一种转机。 因此，Lua中适当的尾部调用非常有用的应用是编程状态机。 这些应用程序可以通过函数来​​表示每个状态; 改变状态是去（或去调用）一个特定的function。 作为一个例子，让我们考虑一个简单的迷宫游戏。 迷宫有几个房间，每个房间最多有四个门：北，南，东，西。 在每一步，用户input一个移动方向。 如果在那个方向有门，用户就去相应的房间; 否则，程序会打印一个警告。 目标是从最初的房间到最后的房间。

这个游戏是一个典型的状态机，当前的房间是状态。 我们可以为每个房间实现一个function的迷宫。 我们使用尾巴呼叫从一个房间移动到另一个房间。 一个有四个房间的小迷宫可能是这样的：

 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 

所以你看，当你做一个recursion调用，如：

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

这不是尾recursion，因为在recursion调用之后，您仍然需要在该函数中执行（添加1）。 如果input的数字太大，可能会导致堆栈溢出。

Answer 5

而不是用文字来解释，这里是一个例子。 这是阶乘函数的Scheme版本：

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

这是一个尾recursion的阶乘版本：

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

你会注意到在第一个版本中recursion调用的事实被送入乘法expression式，因此当进行recursion调用时，状态必须保存在堆栈中。 在尾recursion版本中，没有其他Sexpression式正在等待recursion调用的值，因为没有其他的工作要做，所以状态不必保存在堆栈中。 通常，Scheme尾recursion函数使用常量堆栈空间。

Answer 6

行话文件有这个关于尾recursion的定义：

尾recursion/n //

如果你还没有厌倦，请看尾recursion。

Answer 7

使用定期recursion，每个recursion调用将另一个条目推入调用堆栈。 当recursion完成时，应用程序必须将每个条目都popup来。

通过尾recursion，编译器可以将堆栈压缩到一个入口，这样可以节省堆栈空间…一个大的recursion查询实际上可能导致堆栈溢出。

基本上尾部recursion可以被优化成迭代。

Answer 8

这意味着不需要将指令指针压入堆栈，只需跳到recursion函数的顶部并继续执行即可。 这允许函数无限期递增而不溢出堆栈。

我写了一篇关于这个主题的博客文章，里面有堆栈框架的graphics例子。

Answer 9

尾recursion是指在recursionalgorithm的最后一个逻辑指令中recursion调用是最后一个。

通常在recursion中，你有一个基本的情况是停止recursion调用，并开始popup调用栈。 要使用一个经典的例子，尽pipe比Lisp更多的C语言，阶乘函数说明了尾recursion。 在检查基本情况之后发生recursion调用。

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

请注意，阶乘的初始调用必须是阶乘（n，1），其中n是要计算阶乘的数字。

Answer 10

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

非常简单直观的理解。

简单的方法来判断一个recursion函数是否是recursion的，就是如果它在基本情况下返回一个具体的值。 这意味着它不会返回1或者真的或者类似的东西。 它将更可能返回一个方法参数的一个变体。

另一种方法是告诉是recursion调用是否没有任何增加，算术，修改等…意味着它只不过是一个纯粹的recursion调用。

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

Answer 11

在Java中，这里有一个可能的斐波那契函数的尾recursion实现：

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

将其与标准recursion实现进行对比：

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

Answer 12

下面是使用尾recursion进行阶乘的Common Lisp示例。 由于无堆栈性质，可以执行疯狂的大因数计算。

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

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

Answer 13

这里是前面提到的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 } 

Answer 14

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

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

Answer 15

为了理解tail-callrecursion和non-tail-callrecursion之间的一些核心差异，我们可以探索这些技术的.NET实现。

以下是C＃，F＃和C ++ \ CLI中一些示例的文章：C＃，F＃和C ++ \ CLI 中的尾recursion冒险 。

C＃没有优化尾部recursion，而F＃却是。

原理的差异涉及循环与Lambda演算。 C＃devise时考虑了循环，而F＃则是从Lambda演算的原理构build的。 关于Lambda微积分的一个非常好的（和免费的）书，请参阅： Abelson，Sussman和Sussman的“计算机程序的结构和解释” 。

关于F＃中的尾部调用，有关非常好的介绍性文章，请参阅： F＃中尾部调用的详细介绍 。 最后，这里是一篇文章，介绍了非尾recursion和尾调用recursion（在F＃中）的区别： F sharp中的尾recursion与非尾recursion 。

如果您想了解一些C＃和F＃之间的tail-callrecursiondevise差异，请参阅： 在C＃和F＃中生成尾部调用操作码 。

如果您足够关心想知道什么条件阻止C＃编译器执行尾部调用优化，请参阅此文章： JIT CLR尾部调用条件 。

Answer 16

简而言之，尾recursion具有recursion调用作为函数中的最后一个语句，以便它不必等待recursion调用。

所以这是一个尾recursion，即N（x – 1，p * x）是函数中的最后一个语句，编译器很聪明地知道它可以优化为for循环（阶乘）。 第二个参数p带有中间产品值。

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

这是编写上述因子函数的非尾recursion方法（尽pipe一些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); } 

我写了一篇很长的文章“ 理解尾recursion – Visual Studio C ++ – Assembly View ”

Answer 17

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

在迭代和recursion的对比中，我们必须小心，不要把recursion过程的概念和recursion过程的概念混为一谈。 当我们将过程描述为recursion时，我们指的是过程定义引用（直接或间接）过程本身的语法事实。 但是，当我们将一个stream程描述为遵循线性recursion的模式时，我们正在谈论stream程如何演变，而不是如何编写stream程的语法。 看起来令人不安的是，我们将一个recursion过程（如事实调用者）称为生成一个迭代过程。 然而，这个过程实际上是迭代的：它的状态被它的三个状态variables完全捕获，并且解释器只需要跟踪三个variables来执行该过程。

stream程和过程之间的区别可能会造成混淆的一个原因是，大多数公共语言（包括Ada，Pascal和C）的实现都是这样devise的，即任何recursion过程的解释都会消耗大量的内存过程调用的次数，即使所描述的过程原则上是迭代的。 因此，这些语言只能通过诸如do，repeat，until，for和while之类的专用“循环结构”来描述迭代过程。 计划的实施不会分享这个缺陷。 它将在恒定空间中执行一个迭代过程，即使迭代过程由recursion过程描述。 带有这个属性的实现被称为尾recursion（tail-recursive）。 通过尾recursion实现，可以使用普通的过程调用机制来表示迭代，所以特殊的迭代构造只能用作语法糖。

Answer 18

尾recursion是你现在的生活。 你不断地重复使用同一个栈帧，因为没有理由或方法返回到“前一个”帧。 过去已经结束了，所以可以放弃。 你会得到一个框架，永远走向未来，直到你的过程不可避免地死亡。

_{当你考虑某些进程可能使用额外的帧时，类比就会崩溃，但如果堆栈不能无限增长，仍然被认为是尾recursion的。}

Answer 19

recursion意味着一个调用自己的函数。 例如：

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

尾recursion意味着结束函数的recursion：

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

请看，最后一件事情是未完成的函数（在Scheme中使用的术语）就是调用它自己。 另一个（更有用的）例子是：

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

在助手程序中，如果离开不是零的最后一件事就是自己调用（后面的东西和cdr的东西）。 这基本上是你如何映射一个列表。

尾recursion具有很大的优点，即interperter（或编译器，依赖于语言和供应商）可以对其进行优化，并将其转换为相当于while循环的东西。 事实上，在Scheme的传统中，大部分“for”和“while”循环都是以尾recursion的方式完成的（据我所知，没有for和while）。

Answer 20

理解tail call recursion的最好方法是： 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) 

^尾巴回报

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

然而，在尾recursion版本中，代码块中的最后调用（或尾调用）是tailrecsum(x - 1, running_total + x) ，这意味着最后一次调用方法本身，之后没有任何操作。

这一点很重要，因为这里看到的尾recursion不会增加内存，因为当底层VM看到一个函数调用自己在尾部位置（函数中最后一个expression式）时，它消除了当前的栈帧，被称为尾巴呼叫优化（TCO）。

Answer 21

这个问题有很多很好的答案，但我不禁要问，如何定义“尾recursion”，或者至less是“适当的尾recursion”。 也就是说，应该把它看作程序中特定expression式的属性吗？ 还是应该把它看作是编程语言实现的一个属性？

关于后一种观点，Will Clinger在“适当的尾recursion和空间效率”（PLDI 1998）中有一篇经典论文 ，它将“适当的尾recursion”定义为编程语言实现的一个属性。 该定义的构造允许忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的链接列表框）。

为了实现这一点，它使用渐近分析：不是像通常所看到的程序执行时间，而是程序空间的使用 。 这样，堆分配的链接列表与运行时调用堆栈的空间使用情况最终渐近地相等; 所以人们会忽视编程语言的实现细节（这个细节在实践中确实很重要，但是当试图确定一个给定的实现是否满足“属性尾recursion”的要求时，会有相当多的泥泞， ）

这篇论文值得仔细研究，原因如下：

• 它给出了一个程序的尾部expression式和尾部调用的归纳定义。 （这样一个定义，以及为什么这样的要求很重要，似乎是这里给出的其他答案的大部分内容。）

  这里是这些定义，只是为了提供一个文本的味道：

  定义1以核心scheme编写的程序的尾部expression式归纳如下。

  1. lambdaexpression式的主体是尾部expression式
  2. 如果(if E0 E1 E2)是尾部expression式，则E1和E2都是尾部expression式。
  3. 没有别的是尾巴expression。

  定义2 尾调用是一个过程调用的尾部expression式。

（一个尾recursion调用，或者正如文章所说，“自尾调用”是调用本程序的尾调用的特例。）

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

  例如，在分别给出机器的定义之后，1.基于堆栈的内存pipe理，2.垃圾收集但是没有尾部调用，3.垃圾收集和尾部调用，本文继续提供更先进的存储pipe理策略，比如4.“evlis尾recursion”，其中在尾调用中最后一个子expression式参数的评估中不需要保留环境，5.将闭包的环境仅仅减less到闭包的自由variables， 6. Appel和Shao定义的所谓“安全空间”语义。

• 为了certificate这些机器实际上属于六个不同的空间复杂性类别，本文针对每一对比较的机器提供了一些程序的具体示例，这些程序将在一台机器上暴露渐近式空间而不是另一台机器。

---

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