什么是尾递归？

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

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

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

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

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

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

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

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

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

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

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

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

这里不是用文字来解释，而是举个例子。这是阶乘函数的 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 尾递归函数使用常量堆栈空间。

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

尾递归 /n./

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

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

尾叫 [tail recursion] 是一种 goto 装扮 作为电话。尾部调用发生在以下情况下 函数调用另一个作为其最后一个 行动，所以它没有别的可做。 例如，在以下代码中， 对的调用是尾部调用：g

function f (x)
  return g(x)
end

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

因为正确的尾部调用使用 no 堆栈空间，对 “嵌套”尾部调用的数量 程序可以使。例如，我们可以 使用 any 调用以下函数 数字作为参数;它永远不会 溢出堆栈：

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

...正如我之前所说，尾部呼叫是一种 有点去。因此，一个非常有用的 在 Lua 用于对状态机进行编程。 此类应用程序可以表示每个 按函数表示;更改状态 是去（或打电话给）一个特定的 功能。举个例子，让我们 考虑一个简单的迷宫游戏。迷宫 有几个房间，每个房间最多有 四扇门：北门、南门、东门和 西。在每个步骤中，用户输入一个 运动方向。如果有一扇门 在该方向上，用户转到 相应的房间;否则， 程序打印警告。目标是 从最初的房间到最后的房间 房间。

这个游戏是一个典型的状态机， 其中，当前房间是状态。 我们可以用一个来实现这样的迷宫 每个房间的功能。我们使用 tail 从一个房间移动到 另一个。一个有四个房间的小迷宫 可能看起来像这样：

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

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

while(E) { S }; return Q

其中 和 是表达式 和 是语句序列，并将其转换为尾递归函数EQS

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

当然，必须定义 、 和 才能计算某些变量的一些有趣值。例如，循环函数ESQ

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

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

考虑一个简单的函数，将前 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);
    }
}

如果调用 ，则 JavaScript 解释器将评估以下内容：recsum(5)

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

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

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

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

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

尾递归是指结束函数的递归：

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

看，un-ended 函数（过程，在 Scheme 术语中）做的最后一件事就是调用自己。另一个（更有用的）例子是：

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

在帮助程序过程中，如果左边不是 nil，它做的最后一件事就是调用自己（AFTER cons something 和 cdr something）。这基本上就是你映射列表的方式。

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

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

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
}

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

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

非常简单直观地理解。

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

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

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

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

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

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

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

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

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

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

如果您足够关心想知道哪些条件阻止 C# 编译器执行尾调用优化，请参阅以下文章：JIT CLR 尾调用条件。

对我来说，最好的理解方式是递归的特殊情况，其中最后一次调用（或尾部调用）是函数本身。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)recsumx + ..

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

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

编辑

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

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

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

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

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

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

尾递归是你现在的生活。您不断地一遍又一遍地回收相同的堆栈帧，因为没有理由或方法返回到“上一个”帧。过去已经结束了，所以它可以被丢弃。你得到一个框架，永远走向未来，直到你的过程不可避免地死去。

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

这个问题有很多很好的答案......但我忍不住对如何定义“尾递归”，或者至少是“适当的尾递归”提出了另一种看法。也就是说：是否应该将其视为程序中特定表达式的属性？还是应该将其视为编程语言实现的属性？

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

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

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

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

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

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

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

  定义 2尾调用是尾部表达式，即过程调用。

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

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

  例如，在分别给出 1.基于堆栈的内存管理， 2.垃圾回收，但没有尾声， 3.垃圾回收和尾部调用，本文继续介绍更高级的存储管理策略，例如 4.“evlis 尾递归”，在尾部调用中最后一个子表达式参数的计算过程中不需要保留环境， 5.将闭包的环境简化为仅该闭包的自由变量，以及 6.Appel 和 Shao 定义的所谓“空间安全”语义。

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

---

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

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

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

一个简单的方法是：

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

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

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

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

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

许多人已经在这里解释了递归。我想引用 Riccardo Terrell 所著的《Concurrency in .NET， Modern patterns of concurrent and parallel programming》一书中关于递归带来的一些优势的一些想法：

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

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

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

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

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

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

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

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

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

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循环失败，因此进入循环 所以它回来了else4 * 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. 在堆栈内存中，我们有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循环失败，因此进入循环 所以它回来了elsefact(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循环为 true

所以它回来了running_total

的输出running_total = 24

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

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

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

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

当调用堆栈推送到的帧对象过多时，会导致堆栈溢出。调用函数时，帧对象被推送到调用堆栈上，并在函数返回时从调用堆栈中弹出。Frame 对象包含局部变量等信息，以及函数返回时要返回到的代码行。

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

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

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

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

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

考虑定义为以下的函数：

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)

如果你检查每个涉及递归情况的 RHS，你会发现 RHS 的整个主体都是对 的调用，而且仅此而已。这个定义是尾递归的。g(...)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

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

然而，有些语言（例如 Scheme）确实要求所有实现来优化尾递归函数，甚至可能是所有处于尾部位置的调用。

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

• 尾递归函数是一种递归函数，其中递归调用是函数中最后执行的事物。

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

O(N)=>O(1)

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

• 我们应该在递归解中写尾递归。但某些语言实际上并不支持其引擎中的尾递归，该引擎将语言编译下来。自 ECMA6 以来，规范中一直存在尾递归。B没有一个编译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 次阶乘 （） 调用，空间为 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);
  }
}

• 在进行递归调用后，我们不需要记住任何内容