解释一下尾调用优化的重要性以及为什么Python需要它。

Question

解释一下尾调用优化的重要性以及为什么Python需要它。

pythontail-recursiontail-call-optimization

20

显然，关于Python是否需要尾递归优化（TCO）已经引起了很大的争议。这一问题在有人向Guido发送了SICP的副本之后达到了高潮，因为他不“理解”。我和Guido一样。我理解尾递归优化的概念。我只是想不出Python真正需要它的原因。

为了让我更容易理解，你能给出一个可以使用TCO大大简化的代码片段吗？

- Jason Baker

3

+1，我也完全不理解这场混乱的原因。 - Dan Lew

8

讨论并不是Python 需要 TCO，而是指Guido因错误的理由拒绝了它。 - Mauricio Scheffer

我很高兴没有人将这个问题关闭为主观性意见。 - Sergey Orshanskiy

4个回答

6

如果你非常想使用递归来完成可以用循环实现的事情，那么“尾调用优化”确实是必须的。然而，Python的至高无上的独裁者（BDFL）Guido强烈主张使用循环来表达循环 - 因此他不会特别处理尾调用（牺牲堆栈跟踪转储和调试的一致性）。

- Alex Martelli

5

尾调用优化可以更轻松地编写递归函数，而不必担心堆栈溢出问题：

def fac(n, result=1):
        if n > 1:
                return fac(n - 1, n * result)
        return result

没有尾调用优化，使用一个大数字调用此函数可能会导致堆栈溢出。

- Zifre

3

标准学术案例。有现实世界中使用的案例吗？ - ebo

7

实际上，这不是尾递归。乘法在尾部，而不是递归中。 - Javier

3

定义一个函数 fac(n)，它的作用是计算 n 的阶乘，即 n!。函数中使用了 reduce 函数和 operator 模块中的 mul 函数，reduce 函数会对序列进行累积操作，mul 函数用于计算两个数的乘积。range(1, n+1) 生成了从 1 到 n 的整数序列，并传递给 reduce 函数进行累乘操作。 - John Fouhy

5

@Javier，乘法运算在尾部执行，且没有“等待”的操作需要执行，一旦递归调用返回，就完成了。因此，这是尾递归。如果我说错了，请纠正我。 - user59634

3

异步状态机常见于 F# 服务器代码中。@ebo 问是否有现实世界使用的例子，这是一个标准的学术例子。 - J D

显示剩余2条评论

1

Guido在后续的帖子中指出，TCO允许将状态机实现为相互递归调用的函数集合，这样可以更加清晰地编写代码。然而，在同一篇文章中，他提出了一种同样清晰的替代方案，而不需要使用TCO。

- barracel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Javier · Accepted Answer

个人而言，我非常重视尾调用优化；主要是因为它使递归与迭代一样高效（或者说将迭代作为递归的子集）。在极简语言中，你可以获得巨大的表达能力，而不会牺牲性能。

然而，在“实用”语言（如Python）中，通常有许多其他构造可用于几乎所有情况，因此它不那么关键。当然，它总是一个好东西，可以应对未预见的情况。

个人而言，我非常重视尾调用优化；主要是因为它使递归与迭代一样高效（或者说将迭代作为递归的子集）。在极简语言中，你可以获得巨大的表达能力，而不会牺牲性能。

然而，在“实用”语言（如Python）中，通常有许多其他构造可用于几乎所有情况，因此它不那么关键。当然，它总是一个好东西，可以应对未预见的情况。