什么是尾递归？

问题描述 投票：1512回答：27

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

algorithm language-agnostic functional-programming recursion tail-recursion
27个回答
1524
投票

考虑一个添加前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，因为Python解释器不支持tail call optimization。然而，虽然尾调用优化是part of the ECMAScript 2015 spec，大多数JavaScript解释器don't support it。

19
投票

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

理解起来非常简单直观。

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

我理解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）。

编辑

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

11
投票

在Java中，这是Fibonacci函数的可能尾递归实现：

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);
}
10
投票

这是一个Common Lisp示例，它使用尾递归来执行阶乘。由于无堆栈特性，人们可以执行疯狂的大因子计算......

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

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

9
投票

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

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

9
投票

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

所以这是一个尾递归，即N（x - 1，p * x）是函数中的最后一个语句，编译器很聪明地知道它可以被优化为for循环（factorial）。第二个参数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);
}

我写了一篇名为“Understanding Tail Recursion – Visual Studio C++ – Assembly View”的长篇文章

enter image description here

8
投票

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

这是Structure and Interpretation of Computer Programs关于尾递归的摘录。

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

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

6
投票

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

当你考虑某些进程可能使用额外的帧但是如果堆栈没有无限增长时仍然被认为是尾递归的话，这个类比就会崩溃。

6
投票

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

考虑计算数字因子的问题。

一个简单的方法是：

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

假设你调用factorial（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），但没有一个调用将任何额外的变量添加到堆栈。因此编译器可以取消堆栈。

641
投票

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

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

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

5
投票

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

这篇文章包含C＃，F＃和C ++ \ CLI中的一些示例：Adventures in Tail Recursion in C#, F#, and C++\CLI。

C＃不优化尾调用递归，而F＃则优化。

原理的差异涉及循环与Lambda演算。 C＃的设计考虑了循环，而F＃是根据Lambda演算的原理构建的。有关Lambda演算原理的非常好（并且免费）的书，请参阅Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman。

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

如果您想了解C＃和F＃之间尾调用递归的一些设计差异，请参阅Generating Tail-Call Opcode in C# and F#。

如果您非常关心要知道哪些条件阻止C＃编译器执行尾调用优化，请参阅以下文章：JIT CLR tail-call conditions。

4
投票

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

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

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

取自this超级棒的帖子。请考虑阅读。

4
投票

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

(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)))

在辅助程序中，如果左边不是nil，它会做的最后一件事就是调用自己（在有些事情和cdr之后）。这基本上是您映射列表的方式。

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

3
投票

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

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

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

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

  • 它给出了程序尾部表达式和尾部调用的归纳定义。 （这样的定义，以及为什么这些呼叫很重要，似乎是这里给出的大多数其他答案的主题。） 以下是这些定义，只是为了提供文本的味道： 定义1以核心方案编写的程序的尾部表达式归纳定义如下。 lambda表达式的主体是尾部表达式 如果(if E0 E1 E2)是尾部表达式，那么E1和E2都是尾部表达式。 没有别的东西是尾巴表达。 定义2尾调用是一个尾部表达式，它是一个过程调用。

（尾递归调用，或者正如文章所说，“自尾调用”是尾调用的特例，其中自己调用过程。）

  • 它为评估Core Scheme提供了六种不同“机器”的正式定义，其中每台机器具有相同的可观察行为，除了每个机器所处的渐近空间复杂度类。 例如，在为机器定义后，分别为：1。基于堆栈的内存管理，2。垃圾收集但没有尾调用，3。垃圾收集和尾调用，本文继续介绍更高级的存储管理策略，如4.“evlis tail recursion”，其中不需要在尾部调用中对最后一个子表达式参数的评估中保留环境，5。将闭包的环境简化为该闭包的自由变量，以及6. Appel and Shao定义的所谓“安全换空间”语义。
  • 为了证明这些机器实际上属于六个不同的空间复杂性类别，对于每对比较的机器，本文提供了程序的具体示例，这些程序将在一台机器上暴露渐近空间而不在另一台机器上。

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

2
投票

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

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

缺点是如果写得不正确，它们会导致无限循环和其他意外结果。

我将解释Simple Recursive函数和Tail Recursive函数

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

  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)

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

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

  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

最后，事实（4）= 4 * 3 * 2 * 1 = 24的结果

enter image description here

Tail Recursion会是

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)

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

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

  1. 在堆栈内存中，我们有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的输出

最后，事实（4,1）= 24的结果

enter image description here

2
投票

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

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解释器也不会进行尾调用优化，因此像这样排列代码不会给运行时带来好处。）

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

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

当调用堆栈有太多帧对象被推入时，会导致堆栈溢出。调用函数时，帧对象被压入调用堆栈，并在函数返回时弹出调用堆栈。 Frame对象包含诸如局部变量之类的信息以及函数返回时返回的代码行。

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

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

编译器或解释器必须具有尾调用优化作为其能够识别何时可以应用尾调用优化的特征。即便如此，您可能已经重新排列递归函数中的代码以使用尾调用优化，如果可读性的潜在降低值得优化，则由您决定。

1
投票

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

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

这里也有一些关于尾递归的书中有趣的注释：

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

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

1
投票

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

187
投票

重要的一点是尾递归基本上等于循环。这不仅仅是编译器优化的问题，而是表达性的基本事实。这有两种方式：你可以采取任何形式的循环

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

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

129
投票

“Lua编程”一书中的摘录显示了how to make a proper tail recursion（在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

......正如我之前所说，尾调用是一种转向。因此，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）。如果输入一个非常高的数字，可能会导致堆栈溢出。

68
投票

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

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

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

64
投票

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

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

这是一个尾递归的factorial版本：

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

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

62
投票

行话文件有关于尾递归定义的说法：

尾递归/ n./

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

31
投票

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

通常在递归中，你有一个基本情况，它停止递归调用并开始弹出调用堆栈。使用经典示例，尽管比Lisp更多C-ish，但是阶乘函数说明了尾递归。检查基本情况后发生递归调用。

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

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

27
投票

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

我写了一篇关于这个主题的blog帖子，里面有堆栈帧的图形示例。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.