https://stackoverflow.com/questions/33923
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
在开始学习 lisp 时，我遇到了这个术语 尾递归. 。它到底是什么意思？
解决方案
考虑一个将前 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，因为现代 JavaScript 解释器支持 尾调用优化 但 Python 解释器则不然。
其他提示
在 传统递归, ，典型的模型是先执行递归调用，然后获取递归调用的返回值并计算结果。通过这种方式，直到每次递归调用返回后，您才能获得计算结果。
在 尾递归, ，您首先执行计算，然后执行递归调用，将当前步骤的结果传递到下一个递归步骤。这导致最后一个语句的形式为 (return (recursive-function params)). 基本上，任何给定递归步骤的返回值与下一个递归调用的返回值相同.
这样做的结果是，一旦您准备好执行下一个递归步骤，您就不再需要当前的堆栈帧。这允许进行一些优化。事实上，使用正确编写的编译器，您永远不应该出现堆栈溢出 暗笑 带有尾递归调用。只需将当前堆栈帧重用于下一个递归步骤即可。我很确定 Lisp 会这么做。
重要的一点是尾递归本质上等同于循环。这不仅仅是编译器优化的问题，而是关于表达能力的基本事实。这是双向的：你可以采用任何形式的循环
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);
}
（用参数较少的函数“包装”尾递归函数是一种常见的函数惯用法。）
本书摘录于此 Lua 编程 节目 如何进行正确的尾递归 （在 Lua 中，但也应该适用于 Lisp）以及为什么它更好。
A 尾调用 尾部递归]是一种打扮成一种呼唤的goto。当函数将另一个呼叫称为最后一个动作时，就会发生尾声，因此无事可做。例如，在以下代码中，调用
g是一个尾调用：function f (x) return g(x) end后
f来电g, ，这无关。在这种情况下，当调用函数结束时，程序无需返回调用功能。因此，在尾声调用后，该程序无需保留有关堆栈中调用功能的任何信息。...由于适当的尾部调用没有堆栈空间，因此程序可以对的“嵌套”尾巴呼叫的数量没有限制。例如，我们可以将以下数字称为参数的以下函数；它永远不会溢出堆栈：
function foo (n) if n > 0 then return foo(n - 1) end end...正如我之前说的那样，尾巴是一种Goto。因此，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）。如果你输入一个非常大的数字，可能会导致堆栈溢出。
使用常规递归，每个递归调用都会将另一个条目推送到调用堆栈上。递归完成后，应用程序必须将每个条目一直弹出回来。
使用尾递归，根据语言的不同，编译器可能能够将堆栈折叠为一个条目，因此可以节省堆栈空间......大型递归查询实际上可能会导致堆栈溢出。
基本上尾递归可以优化为迭代。
这里不再用文字来解释，而是举个例子。这是阶乘函数的方案版本：
(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 尾递归函数使用常量堆栈空间。
行话文件对尾递归的定义有这样的说法：
尾递归 /n./
如果您还没有厌倦它，请参阅尾递归。
尾递归是指递归算法中最后一条逻辑指令中的最后一次递归调用。
通常在递归中，你有一个 基本情况 这就是停止递归调用并开始弹出调用堆栈的原因。举一个经典的例子，尽管阶乘函数比 Lisp 更接近 C，但它说明了尾递归。发生递归调用 后 检查基本情况条件。
factorial(x, fac=1) {
if (x == 1)
return fac;
else
return factorial(x-1, x*fac);
}
对阶乘的最初调用是 factorial(n) 在哪里 fac=1 （默认值），n 是要计算阶乘的数字。
这意味着您不需要将指令指针压入堆栈，只需跳转到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。
我写了一个 博客 关于这个主题的帖子，其中有堆栈帧的图形示例。
这是一个比较两个函数的快速代码片段。第一个是传统的递归，用于查找给定数字的阶乘。第二种使用尾递归。
非常简单且直观易懂。
判断递归函数是否为尾递归的一个简单方法是看它是否在基本情况下返回具体值。这意味着它不会返回 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);
}
}
对我来说最好的理解方式 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) 这意味着最后一次调用是对该方法本身进行的，此后不再执行任何操作。
这一点很重要，因为这里看到的尾递归不会使内存增长，因为当底层虚拟机看到一个函数在尾部位置（函数中要计算的最后一个表达式）调用自身时，它会消除当前的堆栈帧，这称为尾调用优化（TCO）。
编辑
注意。请记住，上面的示例是用 Python 编写的，其运行时不支持 TCO。这只是一个例子来解释这一点。Scheme、Haskell 等语言支持 TCO
在 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);
}
这是一个使用尾递归进行阶乘的 Common Lisp 示例。由于无堆栈的性质，人们可以执行非常大的阶乘计算......
(defun ! (n &optional (product 1))
(if (zerop n) product
(! (1- n) (* product n))))
然后为了好玩你可以尝试 (format nil "~R" (! 25))
我不是 Lisp 程序员，但我认为 这 会有帮助的。
基本上，这是一种编程风格，递归调用是您所做的最后一件事。
简而言之，尾递归将递归调用作为 最后的 在函数中声明，这样就不必等待递归调用。
所以这是尾递归，即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++ – 程序集视图"
这是 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
}
这是摘录自 计算机程序的结构和解释 关于尾递归。
与迭代和递归相比，我们必须小心，不要将递归过程的概念与递归程序的概念混淆。当我们将程序描述为递归时，我们指的是句法事实，即该过程定义（直接或间接地）是指该程序本身。但是，当我们将过程描述为遵循线性递归的模式时，我们正在谈论该过程的演变方式，而不是谈论如何编写过程的语法。我们将递归程序（例如事实 - 生成迭代过程）提到的递归程序似乎令人不安。然而，这个过程实际上是迭代的：它的状态完全被其三个状态变量捕获，而解释器只需要跟踪三个变量才能执行该过程。
过程和过程之间的区别可能令人困惑的一个原因是，大多数通用语言的实施（包括ADA，Pascal和C）的设计是设计的，以使任何递归过程的解释都消耗了一定数量即使所描述的过程原则上是迭代的，程序调用的数量也是如此。结果，这些语言只能通过诉诸特殊用途的“循环结构”（例如，重复，直到，for，for，for，for，for）来描述迭代过程。 方案的实施不能共享此缺陷。即使递归过程描述了迭代过程，它也会在恒定空间中执行迭代过程。使用此属性的实施称为尾部回复。 通过尾部回复的实现，可以使用普通程序调用机制来表达迭代，因此特殊的迭代构建体仅作为句法糖有用。
尾递归就是你现在的生活。您不断地一遍又一遍地回收相同的堆栈帧，因为没有理由或方法返回到“前一个”帧。过去的事情已经过去了，所以可以抛弃它。你得到一帧，永远进入未来，直到你的进程不可避免地消亡。
当您考虑某些进程可能会利用额外的帧但如果堆栈不无限增长时仍然被认为是尾递归时，这个类比就不成立了。
尾递归是一个递归函数，该功能在递归调用返回后未完成计算的函数的末端（“尾巴”）呼叫自己。许多编译器优化以将递归呼叫更改为尾部递归或迭代呼叫。
考虑计算数字的阶乘问题。
一个简单的方法是：
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)，但没有任何调用向堆栈添加任何额外的变量。因此编译器可以取消堆栈。
为了了解尾调用递归和非尾调用递归之间的一些核心区别，我们可以探索这些技术的 .NET 实现。
以下文章包含一些 C#、F# 和 C++\CLI 示例： C#、F# 和 C++\CLI 中的尾递归历险记.
C# 不会优化尾部调用递归，而 F# 会优化。
原理上的差异涉及循环与循环。拉姆达演算。C# 的设计考虑了循环，而 F# 是根据 Lambda 演算原理构建的。有关 Lambda 演算原理的一本非常好的（且免费）书籍，请参阅 计算机程序的结构和解释，作者：Abelson、Sussman 和 Sussman.
关于 F# 中的尾部调用，有一篇非常好的介绍性文章，请参阅 F# 中尾调用的详细介绍. 。最后，这里有一篇文章介绍了非尾递归和尾调用递归之间的区别（在 F# 中）： 尾递归 vs 尾递归F 升调的非尾递归.
如果您想了解 C# 和 F# 之间尾调用递归的一些设计差异，请参阅 在 C# 和 F# 中生成尾部调用操作码.
如果您非常想知道哪些条件会阻止 C# 编译器执行尾部调用优化，请参阅本文： JIT CLR 尾部调用条件.
有两种基本的递归： 头递归 和 尾递归。
在 头递归, ，一个函数进行递归调用，然后执行更多计算，例如使用递归调用的结果。
在一个 尾递归 功能，所有计算首先发生，递归调用是发生的最后一件事。
取自 这 超级棒的帖子。请考虑阅读它。
递归意味着函数调用自身。例如：
(define (un-ended name)
(un-ended 'me)
(print "How can I get here?"))
尾递归是指结束函数的递归：
(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）。
这个问题有很多很好的答案......但是，我不禁会替代如何定义“尾随递归”或至少“适当的尾部递归”。即：人们是否应该将其视为程序中特定表达式的属性？或者我们应该将其视为一种财产 编程语言的实现?
有关后一种观点的更多信息，有一个经典的 纸 Will Clinger 的《正确的尾部递归和空间效率》（PLDI 1998），将“正确的尾部递归”定义为编程语言实现的一个属性。该定义的构造是为了允许忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链表表示）。
为了实现这一点，它使用渐近分析：不是人们通常看到的程序执行时间，而是程序 空间使用. 。这样，堆分配链表与运行时调用堆栈的空间使用最终是渐近等效的；因此，人们会忽略编程语言的实现细节（这一细节在实践中确实非常重要，但是当人们试图确定给定的实现是否满足“属性尾递归”的要求时，可能会使情况变得更加混乱）
这篇论文值得仔细研究，原因如下：
它给出了一个归纳定义 尾部表达 和 尾部调用 一个程序的。（这样的定义以及为什么这样的调用很重要，似乎是此处给出的大多数其他答案的主题。）
以下是这些定义，只是为了提供文本的风味：
定义1 这 尾部表达 用CoreScheme编写的程序的定义归纳如下。
- lambda 表达式的主体是尾部表达式
- 如果
(if E0 E1 E2)是一个尾部表达式，那么两者E1和E2是尾部表达式。 - 其他都不是尾部表达式。
定义2 A 尾调用 是一个尾部表达式，它是一个过程调用。
（尾递归调用，或者如本文所述，“自尾调用”是尾调用的一种特殊情况，其中过程被调用本身。）
它为评估核心方案的六种不同“机器”提供了正式定义，其中每台机器都有相同的可观察行为 除了 为了 渐进的 每个所在的空间复杂度类别。
例如，在分别给出具有 1 的机器的定义之后。基于堆栈的内存管理，2。垃圾回收但没有尾部调用，3。除了垃圾收集和尾部调用之外，本文继续介绍更高级的存储管理策略，例如 4。“evlis 尾递归”，其中在尾调用中最后一个子表达式参数的求值过程中不需要保留环境，5。减少关闭环境 只是 该闭包的自由变量，以及 6。所谓的“空间安全”语义定义为 阿佩尔和邵.
为了证明这些机器实际上属于六个不同的空间复杂度类别，本文为所比较的每一对机器提供了具体的程序示例，这些程序将在一台机器上暴露渐近空间爆炸，而在另一台机器上则不会。
（现在阅读我的答案，我不确定我是否能够真正抓住要点 克林格纸. 。但是，唉，我现在无法投入更多时间来制定这个答案。）
递归函数是一个函数 自己调用
它允许程序员使用 最少的代码量.
缺点是他们可以 导致无限循环 以及其他意想不到的结果，如果 写得不正确.
我将解释两者 简单递归函数和尾递归函数
为了写一个 简单的递归函数
- 要考虑的第一点是您何时应该决定从循环中出来，这是if循环
- 第二个是如果我们是自己的函数要做什么流程
从给出的例子来看：
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)
- 代入n=4
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
If 循环失败，所以它转到 else 循环，所以它返回 4 * fact(3)
在堆栈内存中，我们有
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)
在堆栈内存中，我们有
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)
在堆栈内存中，我们有
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
这 尾递归 将会
public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
- 代入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)
在堆栈内存中，我们有
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)
在堆栈内存中，我们有
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)
在堆栈内存中，我们有
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
这里很多人已经解释了递归。我想引用 Riccardo Terrell 所著的《.NET 中的并发，并发和并行编程的现代模式》一书中关于递归带来的一些优点的一些想法：
“功能递归是在FP中迭代的自然方法，因为它避免了状态突变。在每次迭代期间，一个新值将传递到循环构造函数中以进行更新（突变）。此外，可以构成递归功能，使您的程序更模块化，并引入利用并行化的机会。”
以下是同一本书中关于尾递归的一些有趣的注释：
Tail-Call Recursion是一种将常规递归功能转换为优化版本的技术，该版本可以处理大型输入而没有任何风险和副作用。
注意尾声呼叫作为优化的主要原因是改善数据局部性，内存使用情况和缓存使用情况。通过进行尾声，Callee使用与呼叫者相同的堆栈空间。这降低了记忆压力。它略微改善了高速缓存，因为将相同的内存重复使用以用于后续的呼叫者并可以留在缓存中，而不是驱逐较旧的高速缓存线以腾出新的高速缓存线。
A 尾递归 函数是一个递归函数，它在返回之前执行的最后一个操作是进行递归函数调用。即立即返回递归函数调用的返回值。例如，您的代码如下所示：
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 参数有效地用作一种全局变量。）
但尾调用优化的好处是可以防止堆栈溢出错误。（我会注意到，通过使用迭代算法而不是递归算法，您可以获得同样的好处。）
当调用堆栈上压入了太多帧对象时，就会导致堆栈溢出。当调用函数时，框架对象被压入调用堆栈，并在函数返回时从调用堆栈中弹出。框架对象包含局部变量以及函数返回时返回到哪一行代码等信息。
如果您的递归函数进行过多的递归调用而不返回，则调用堆栈可能会超出其帧对象限制。（数量因平台而异；在 Python 中默认为 1000 个帧对象。）这会导致 堆栈溢出 错误。（嘿，这就是这个网站名称的由来！）
但是，如果递归函数所做的最后一件事是进行递归调用并返回其返回值，那么它没有理由需要将当前帧对象保留在调用堆栈上。毕竟，如果递归函数调用后没有代码，则没有理由保留当前帧对象的局部变量。因此我们可以立即删除当前帧对象，而不是将其保留在调用堆栈上。最终结果是您的调用堆栈的大小不会增加，因此不会堆栈溢出。
编译器或解释器必须将尾调用优化作为一项功能，以便能够识别何时可以应用尾调用优化。即使如此，您也可能会重新排列递归函数中的代码以利用尾调用优化，而这种潜在的可读性下降是否值得优化则取决于您。
与普通递归相比，尾递归相当快。它很快，因为祖先调用的输出不会写入堆栈中以保持跟踪。但在正常递归中，所有祖先调用写入堆栈中的输出来保持跟踪。
