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

Question

假设我们有这段代码:

a = 1

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

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

def func3():
    func1()

有没有办法让 func3 调用 func1 跳出它已经包含的“父函数”？意思是，回到“递归深度 0”，就好像它是从头开始一样？

谢谢!

Answer 1

某些语言提供 tail-call optimization ，这相当于在创建新堆栈帧之前丢弃了先前的堆栈帧。仅当递归调用是发生的最后一个操作时才有可能(否则您需要堆栈帧，因为它指向其余操作)。然而，Python 没有。

你有两个选择:

1. 如果函数是递归的但递归不是通过尾调用完成的，通常很容易convert to tail recursion通过将参数添加到函数签名。 (不过，您的示例中的代码已经采用这种形式。)一旦所有递归都通过尾调用完成，通常很容易 convert it to an iterative style .
2. 如果您想避免执行上述操作，您还可以将代码转换为迭代样式 explicitly uses a stack存储东西，因为堆栈的大小将或多或少是无限的，而调用堆栈通常非常小(这就是导致递归深度限制的原因)。

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

在您的情况下，代码要么进入无限循环，要么不进入无限循环，具体取决于 a，因此

 a = 1

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

 func3()

就足够了。

作为旁注:对于某些算法，memoization可以减少调用次数。如果函数的大输入的结果总是由重复计算的较小输入的结果组成 ("overlapping subproblems")，那么您可以保留返回值的全局缓存并在进行新调用之前检查缓存。通用内存代码可以使用 Python 编写 decorators .