Python 是否优化尾递归？

小能豆

javascript

我有以下一段代码，它因以下错误而失败：

RuntimeError：超出最大递归深度

我尝试重写此代码以允许尾部调用优化 (TCO)。我相信如果 TCO 发生，此代码将会成功。

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

我是否应该得出结论：Python 不执行任何类型的 TCO，或者我只需要对其进行不同的定义？

阅读 38

2024-06-28

共1个答案

小能豆

是的，您说得对，Python 默认不执行尾部调用优化 (TCO)。您遇到的错误“超出最大递归深度”是由于trisum使用 la进行递归调用时达到了 Python 的递归限制n。

TCO 是一种优化技术，其中优化尾部位置的函数调用（函数返回之前的最后一个操作）以重用当前堆栈帧，而不是创建新的堆栈帧。这有助于避免递归中的堆栈溢出错误

Python 的解释器不会自动优化尾调用，这主要是由于 Python 处理函数调用和管理其调用堆栈的方式：

递归限制： Python 强制执行递归限制，以防止无限递归消耗所有可用堆栈空间。达到此限制时，它会引发RuntimeError“超出最大递归深度”消息。
默认无 TCO： Python 的 CPython 解释器（最常用的 Python 实现）不执行 TCO。每次递归调用都会创建一个新的堆栈框架，这会导致较大的值达到递归深度限制n。

为了避免达到 Python 中的递归限制，您可以重写递归函数以使用迭代而不是递归。以下是trisum使用迭代方法重写函数的方法：

def trisum_iterative(n):
    csum = 0
    while n > 0:
        csum += n
        n -= 1
    return csum

print(trisum_iterative(1000))

总之，Python 缺乏尾部调用优化，这意味着像这样的递归函数trisum在的大值下会达到递归深度限制n。为了避免这个问题，在处理可能很大的输入时，你应该迭代地重写这样的函数。这种方法不仅可以避免递归深度错误，而且在大型迭代的时间和空间复杂度方面也往往更有效率。

2024-06-28