使用While循环实现Python尾递归“技巧”

Question

我看过几个使用 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中的递归算法，以及在优化递归算法时需要注意哪些缺陷或“坑”？

- Robin Andrews

---

这就是尾调用优化通常被转换为命令式代码的方式，没错。 - undefined

严格来说，tail_exp_2并没有使用递归...因此并不存在真正的尾调用优化。 - undefined

@hiroprotagonist 我倾向于同意，但我曾看到这种方法被吹捧为在Python中实现尾递归优化的一种方式。所以如果这不是递归，那它到底是什么，它与递归有什么关系？ - undefined

@lambda.xy.x 所以如果你覆盖变量，你实际上是在构建一个调用栈，还是只是循环利用一个变量？而且如果是后者，那是否严格属于递归？ - undefined

请记住，递归技术上（可能不是理论上）只是使用堆栈数据结构的一种花哨方式。尝试使用循环和自定义堆栈重写一些递归算法。 - undefined

Answer 1

任何递归算法都可以被替换为迭代算法。然而，有些例子需要添加额外的堆栈来管理在原始形式中由递归调用处理的状态。使用尾递归时，没有需要管理的状态，因此不需要单独的堆栈。

一些编程语言利用这个事实，并设计他们的编译器在递归代码中优化尾调用，生成等同于循环的机器代码。Python不进行尾调用优化，因此这与您的问题无关。手动重写代码不是尾调用优化，而只是一种特定类型的重构。

Python选择不进行尾调用优化有几个原因。这并不是因为不可能。Python代码被编译成字节码，因此理论上至少有机会将递归调用转换为循环（在实践中更为复杂，因为Python变量名是动态的，您不能保证运行时函数名称是否引用了您期望的内容，这是“Monkeypatching”技术所利用的一个事实）。但是，尾调用优化的最大问题通常是它覆盖了有用的调试信息，这些信息通常由调用堆栈保留，例如您处于递归的深度以及这些先前函数调用的确切状态。即使可能存在性能提升，Python开发人员已决定他们更喜欢普通递归的简单性和可调试性。

如果要将算法从递归实现重写为迭代实现，您始终可以这样做。但在某些情况下，它可能会变得更加复杂。有时候，一些算法的递归实现可能会更短、更简单且更易于理解，尽管迭代等效物可能会更快（并且不会因大量输入而达到递归限制）。将尾调用转换为循环通常是相当简单的。那些使用递归返回值进行复杂操作的代码通常无法进行尾调用优化。

- Blckknght