如何避免Python中嵌套函数的深度递归

Question

假设我们有这段代码：

a = 1

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

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

def func3():
    func1()

有没有办法让func3在调用func1的时候，跳出它之前已经经历过的“父函数”？也就是说，能不能让它回到“递归深度0”，就像是重新开始一样？

谢谢！

Answer 1

不太确定你想在哪里停止递归，不过这可以作为一个好的起点：

def func1(parents = []):
    print "func1"
    if func1 not in parents:
        parents.append(func1)
        func2(parents)

def func2(parents = []):
    print "func2"
    if func2 not in parents:
        parents.append(func2)
        func3(parents)

def func3(parents = []):
    print "func3"
    if func3 not in parents:
        parents.append(func3)
        func1(parents)

func1()

输出结果：

func1
func2
func3
func1

Answer 2

如果你想要反复执行 func1、func2 和 func3 这几个函数，但又不想让它们一直无限循环下去，那么你应该使用循环，而不是递归。

可以试试：

def func1():
    pass # do stuff

def func2():
    pass # do more stuff

def func3():
    pass # something completely different

a = 1

while a == 1: # this will loop indefinately, unless one of the functions chages "a"
    func1()
    func2()
    func3()

Answer 3

有些编程语言提供了一种叫做“尾调用优化”的功能，这意味着在创建新的调用时，可以先丢掉之前的调用记录。这个优化只有在递归调用是最后一个操作时才能实现（否则你需要保留调用记录，因为它指向后面的操作）。不过，Python并不支持这种优化。

你有两个选择：

1. 如果你的函数是递归的，但没有使用尾调用，通常可以通过给函数添加参数来简单地将其转换为尾递归。（不过你示例中的代码已经是这种形式了。）一旦所有递归都使用了尾调用，通常可以很简单地将其转换为迭代风格。
2. 如果你想避免上面的做法，你也可以将代码转换为一种迭代风格，这种风格会明确使用一个栈来存储数据，因为你的栈的大小基本上是没有限制的，而调用栈通常比较小（这就是导致递归深度限制的原因）。

需要注意的是，当你有三个函数相互递归调用时，这两种做法会变得更加复杂。但总体思路是编写新的代码，保持旧代码的行为，而不使用递归，当然，具体怎么做会根据你原来的代码有所不同，尽管一般的模式（上面提到的）是相同的。

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

 a = 1

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

 func3()

就足够了。

顺便提一下：对于某些算法，使用“记忆化”可以减少调用次数。如果一个函数对大输入的结果总是由小输入的结果组合而成，而这些小输入的结果是重复计算的（这叫做“重叠子问题”），那么你可以保持一个全局缓存，存储返回的值，并在进行新调用之前先检查缓存。可以使用 装饰器 在Python中编写通用的记忆化代码。