什么是尾递归？

Question

在开始学习 lisp 时，我遇到了“尾递归”这个术语。 它到底是什么意思？

Answer 1

递归函数是一种自行调用的函数，

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

缺点是，如果编写不当，它们可能导致无限循环和其他意外结果。

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

为了编写简单递归函数

1. 首先要考虑的一点是你应该什么时候决定出来
   循环的内容就是if循环
2. 第二个就是如果我们是自己的函数要做什么流程

从给定的例子来看：

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)

1. 替换 n=4

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

If 循环失败，那么它会转到 else< /代码> 循环
所以它返回 4 *fact(3)

2. 在堆栈内存中，我们有 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)

3. < p>在堆栈内存中，我们有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)

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

   代入 n=1

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

If 循环为 true，

因此返回 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);
    }
}

1. 替换 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)

2. 在堆栈内存中，我们有 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)

2. 在堆栈内存中，我们有 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)

3. 在堆栈内存中，我们有 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< /strong>

Answer 2

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

非常简单且直观易懂。

判断递归函数是否为尾递归的一个简单方法是看它是否在基本情况下返回具体值。 这意味着它不会返回 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);
    }
}

Answer 3

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

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 解释器也不执行尾部调用优化，因此安排您的像这样的代码不会带来运行时优势。）

您可能必须使代码更加难以阅读才能利用尾部调用优化，如阶乘示例中所示。 （例如，基本情况现在有点不直观，并且累加器参数实际上被用作一种全局变量。）

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

当调用堆栈上推送了太多帧对象时，就会导致堆栈溢出。 当调用函数时，框架对象被压入调用堆栈，并在函数返回时从调用堆栈中弹出。 框架对象包含局部变量以及函数返回时返回到哪一行代码等信息。

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

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

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

Answer 4

这个问题有很多很好的答案......但我忍不住插话如何定义“尾递归”，或者至少是“正确的尾递归”。 即：是否应该将其视为程序中特定表达式的属性？ 或者我们应该将其视为编程语言实现的一种属性？

有关后一种观点的更多信息，有一个经典的 Will Clinger 的论文，“正确的尾部递归和空间效率”(PLDI 1998)，将“正确的尾部递归”定义为编程语言实现的属性。 该定义的构造是为了允许忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链表表示）。

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

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

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

  以下是这些定义，只是为了提供文本的风格：

  <块引用>

  定义1用CoreScheme编写的程序的尾部表达式归纳定义如下。

  1. lambda 表达式的主体是尾表达式
  2. 如果(if E0 E1 E2)是尾部表达式，则E1和E2都是尾部表达式。
  3. 没有别的东西是尾部表达式。

  定义 2尾部调用是作为过程调用的尾部表达式。

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

• 它为用于评估 Core 的六种不同“机器”提供了正式定义方案，其中每台机器都具有相同的可观察行为，除了各自所处的渐近空间复杂度类之外。

  例如，在分别给出了以下机器的定义：1.基于堆栈的内存管理，2.垃圾收集但无尾部调用，3.垃圾收集和尾部调用，本文继续介绍更高级的存储管理策略，例如 4.“evlis 尾递归”，其中在尾部调用中最后一个子表达式参数的求值过程中不需要保留环境，5.将闭包的环境减少到只是 该闭包的自由变量，以及 6. 由 Appel 和 Shao。

• 为了证明这些机器实际上属于六个不同的空间复杂度类别，本文针对每对进行比较的机器，提供了具体的程序示例，将在一台机器上暴露渐近空间爆炸，而在另一台机器上则不会。

---

（现在阅读我的答案，我不确定我是否能够真正抓住Clinger paper。但是，唉，我不能现在就花更多时间来制定这个答案。）

Answer 5

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

在头递归中，函数进行递归调用，然后
执行更多计算，也许使用的结果
例如，递归调用。

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

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

Answer 6

递归意味着函数调用自身。 例如：

(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 不为零，它所做的最后一件事是调用自身（在 cons Something 和 cdr Something 之后）。 这基本上就是映射列表的方式。

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

Answer 7

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

以下文章包含一些 C#、F# 和 C++\CLI 示例： C#、F# 和 C++\CLI 中的尾递归冒险。

C# 不会优化尾部调用递归，而 F# 会优化。

原理上的差异涉及循环与 Lambda 演算。 C# 的设计考虑了循环，而 F# 是根据 Lambda 演算原理构建的。 有关 Lambda 演算原理的一本非常好的（免费）书籍，请参阅 计算机程序的结构和解释，作者：阿贝尔森、萨斯曼和萨斯曼。

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

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

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

Answer 8

对我来说，理解尾调用递归的最好方法是递归的一种特殊情况，其中最后一次调用（或尾调用）是函数本身。

比较Python中提供的示例：

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

^RECURSION

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

^TAIL RECURSION

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

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

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

编辑

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

Answer 9

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

我在 http://blogs.msdn.com/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx" rel="noreferrer">博客 上发表了一篇文章主题，其中有堆栈帧的图形示例。

Answer 10

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

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

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

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

Answer 11

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

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

Answer 12

尾递归就是你现在的生活。 您不断地一遍又一遍地回收相同的堆栈帧，因为没有理由或方法返回到“前一个”帧。 过去的事情已经过去了，所以可以抛弃它。 你得到一帧，永远进入未来，直到你的进程不可避免地消亡。

_{当您考虑某些进程可能会利用额外的帧但如果堆栈不无限增长时仍被视为尾递归时，这个类比就不成立了。}

Answer 13

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

Answer 14

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

考虑函数定义为：

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) 循环，而尾递归在优化为向后跳转时，与循环同构。

Answer 15

尾递归是函数调用的递归函数
本身位于函数的末尾（“尾部”），其中不进行任何计算
递归调用返回后完成。 许多编译器优化为
将递归调用更改为尾递归或迭代调用。

考虑计算数字的阶乘问题。

一个简单的方法是：

  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)，但没有任何调用将任何额外变量添加到堆栈中。 因此编译器可以取消堆栈。

Answer 16

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

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

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

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

Answer 18

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

Answer 19

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

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

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

Answer 20

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

所以这是一个尾递归，即 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++ – 程序集视图"

Answer 21

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

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

（用参数较少的函数“包装”尾递归函数是常见的函数惯用语。）

Answer 22

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

尾调用 [尾递归] 是一种 goto 修饰
作为呼叫。 当一个尾调用发生时
函数调用另一个函数作为其最后一个函数
行动，所以它没有其他事可做。
例如，在下面的代码中，
对 g 的调用是尾调用：

函数 f (x) 
    返回 g(x) 
  结尾 
  

f调用g之后，就没有别的了
去做。 在这种情况下，程序
不需要返回调用方
函数被调用时的函数
结束。 因此，在尾部调用之后，
该程序不需要保留任何
有关调用函数的信息
在堆栈中。 ...

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

函数 foo (n) 
    如果n>   0 然后返回 foo(n - 1) 结束 
  结尾 
  

...正如我之前所说，尾部调用是
有点转到。 因此，一个非常有用的
正确尾部调用的应用
Lua 用于状态机编程。
此类应用程序可以代表每个
通过函数来​​表示； 改变状态
是去（或打电话）一个特定的
功能。 举个例子，让我们
考虑一个简单的迷宫游戏。 迷宫
有多个房间，每个房间最多可容纳
四门：东、南、北
西方。 在每一步中，用户输入一个
运动方向。 如果有一扇门
朝那个方向，用户去
对应的房间； 否则，
程序打印一条警告。 目标是
从最初的房间到最后的房间
房间。

这个游戏是一个典型的状态机，
当前房间是状态。
我们可以用一个来实现这样的迷宫
每个房间的功能。 我们用尾巴
要求从一个房间搬到另一个房间
其他。 有四个房间的小迷宫
可能看起来像这样：

功能室1 () 
    本地移动 = io.read() 
    如果 move == "south" 则返回 room3() 
    elseif move == "east" 然后返回 room2() 
    else print("无效移动") 
         return room1() -- 留在同一个房间 
    结尾 
  结尾 

  多功能厅2 () 
    本地移动 = io.read() 
    如果 move == "south" 则返回 room4() 
    elseif move == "west" 然后返回 room1() 
    else print("无效移动") 
         返回房间2() 
    结尾 
  结尾 

  多功能厅3 () 
    本地移动 = io.read() 
    如果 move == "north" 则返回 room1() 
    elseif move == "east" 然后返回 room4() 
    else print("无效移动") 
         返回房间3() 
    结尾 
  结尾 

  多功能厅4 () 
    打印（“恭喜！”） 
  结尾 
  

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

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

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

Answer 23

使用常规递归，每个递归调用都会将另一个条目推送到调用堆栈上。 递归完成后，应用程序必须将每个条目一直弹出回来。

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

基本上尾递归可以优化为迭代。

Answer 24

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

尾递归 /n./

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

Answer 25

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

(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 尾递归函数使用常量堆栈空间。

Answer 26

在传统递归中，典型的模型是先执行递归调用，然后获取递归调用的返回值并计算结果。 通过这种方式，直到每次递归调用返回后，您才能获得计算结果。

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

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

Answer 27

考虑一个将前 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) code>，因为默认的第二个参数）。

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 解释器不支持）。

Answer 28

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

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

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

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

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

Answer 29

已经发布了许多好的答案，但让我添加一个非常简短的答案。

递归调用尾递归函数时，不会增加堆栈。

这是上述所有解释的本质结果。 程序员使用的技术因问题而异，但通常归结为将待处理的结果作为参数传递给函数，而不是将部分结果留在堆栈上。

请参阅 Yilmaz 的上述答案，他提供了一个阶乘示例。

Answer 30

• Tail Recursive Function 是一种递归函数，其中递归调用是函数中最后执行的事情。

常规递归函数，我们有堆栈，每次我们在该递归函数中调用递归函数时，都会在调用堆栈中添加另一层。 在正常的递归中
空间：O(n)尾递归使空间复杂度来自

O(N)=>O(1)

• 尾调用优化意味着可以从另一个函数调用一个函数而不增加调用堆栈。

• 我们应该在递归解决方案中编写尾递归。 但某些语言实际上并不支持其引擎中向下编译语言的尾递归。 从 ecma6 开始，规范中就出现了尾递归。 但是编译js的引擎都没有实现尾递归。 在js中你不会实现O(1)，因为编译器本身不知道如何实现这个尾递归。 截至 2020 年 1 月 1 日，Safari 是唯一支持尾部调用优化的浏览器。

• Haskell 和 Java 都有尾递归优化

常规递归阶乘

function Factorial(x) {
  //Base case x<=1
  if (x <= 1) {
    return 1;
  } else {
    // x is waiting for the return value of Factorial(x-1)
    // the last thing we do is NOT applying the recursive call
    // after recursive call we still have to multiply.
    return x * Factorial(x - 1);
  }
}

我们的调用堆栈中有 4 个调用。

Factorial(4); // waiting in the memory for Factorial(3)
4 * Factorial(3); //  waiting in the memory for Factorial(2)
4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

• 我们正在进行 4 个 Factorial() 调用，空间复杂度为 O(n)
• 这可能会导致 Stackoverflow

尾部递归阶乘

function tailFactorial(x, totalSoFar = 1) {
  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop
  if (x === 0) {
    return totalSoFar;
  } else {
    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()
    // we are not doing any additional computaion with what we get back from this recursive call
    return tailFactorial(x - 1, totalSoFar * x);
  }
}

• 我们在进行递归调用后不需要记住任何东西