时间戳

首页 > 解决方案 > 使用 While 循环的 Python 尾递归“Hack”

python - 使用 While 循环的 Python 尾递归“Hack”

问题描述

我已经看到了一些使用while True循环让 Python 进行尾调用优化的示例。例如

def tail_exp(base, exponent, acc=1):
    if exponent == 0:
        return acc
    return tail_exp(base, exponent - 1, acc * base)

变成


def tail_exp_2(base, exponent, acc=1):
    while True:
        if exponent == 0:
            return acc
        exponent, acc = exponent - 1, acc * base

我很想知道这种技术是否适用于 Python 中的所有/大多数递归算法，以及在以这种方式优化递归算法时是否有任何缺点或“陷阱”需要注意？

标签： pythonrecursiontail-recursion

解决方案

任何递归算法都可以用迭代算法代替。但是，一些示例需要在代码中添加一个额外的堆栈，以管理由原始形式的递归调用处理的状态。使用尾递归，没有需要管理的状态，因此不需要单独的堆栈。

一些编程语言利用这一事实并设计它们的编译器以优化递归代码中的尾调用，从而生成相当于循环的机器代码。Python不进行尾调用优化，因此这与您的问题并不相关。手动重写代码不是尾调用优化，它只是一种特殊的重构。

Python 选择不进行尾调用优化有几个原因。不是因为不可能。Python 代码被编译成字节码，所以至少理论上有机会将递归调用转换为循环，如果开发人员需要的话（实际上它有点复杂，因为 Python 变量名是动态的，你不能必须告诉函数名称是否指的是您在运行时所期望的，这是猴子补丁等技术使用的事实）。然而，尾调用优化的最大问题是它通常会覆盖有用的调试信息，这些信息通常会由调用堆栈保存，比如你的递归到底有多深，以及那些先前函数调用的确切状态。Python 开发人员已经决定，他们更喜欢普通递归的简单性和可调试性，而不是尾调用优化的性能优势，即使后者是可能的。

如果您想将算法从递归实现重写为迭代实现，您可以随时这样做。但是，在某些情况下，它可能会变得更加复杂。一些算法的递归实现可以更短、更简单、更容易推理，即使迭代等效可能更快（并且不会达到大输入的递归限制）。不过，将尾调用转换为循环通常非常简单。复杂的情况通常也不适合尾调用优化，因为它们正在使用递归返回的值做复杂的事情。

推荐阅读