如何使用python避免嵌套函数中的深度递归

Question

假设我们有这个代码：

a = 1

def func1():
    if a == 1:
        func2()

def func2():
    if a == 1:
        func3()

def func3():
    func1()

有没有办法让 func3 call func1跳出它已经产生的“父函数”？意思是，回到“递归深度 0”，就好像它重新开始一样？

谢谢！

Answer 1

一些语言提供尾调用优化，这相当于在创建新的堆栈帧之前丢弃前一个堆栈帧。只有当递归调用是最后一个发生的操作时才有可能（否则你需要堆栈帧，因为它指向其余的操作）。然而，Python 没有。

您有两个选择：

1. 如果函数是递归的，但递归不是通过尾调用完成的，通常可以通过向函数签名添加参数来简单地转换为尾递归。（不过，您示例中的代码已经采用这种形式。）一旦使用尾调用完成所有递归，通常很容易将其转换为迭代样式。
2. 如果您想避免执行上述操作，您还可以将代码转换为显式使用堆栈来存储内容的迭代样式，因为堆栈的大小或多或少是无界的，而调用堆栈通常非常小（这就是导致递归深度限制的原因）。

请注意，当您拥有三个相互递归调用的函数时，这两件事都比较棘手。但总体思路是提出新代码，在不使用递归的情况下保留旧代码的行为，很明显，您如何做到这一点会因起始代码而异，尽管一般模式（上面链接）保持不变.

在您的情况下，代码要么进入无限循环，要么不进入，取决于a，所以

 a = 1

 def func3():
     while a == 1:
       pass

 func3()

就足够了。

附带说明：对于某些算法，记忆化可以减少调用次数。如果函数的大输入的结果总是由重复计算的小输入的结果组成（“重叠子问题”），那么您可以保留返回值的全局缓存并在进行新调用之前检查缓存。可以使用装饰器在 Python 中编写通用记忆代码。