在Python中编写递归函数是否可取

Question

我在Python里写了一个Verilog模拟器（主要是描述逻辑门和它们的连接），这是我实验的一部分。

我遇到了栈限制的问题，所以我查了一下，发现Python没有“尾调用优化”这个功能（也就是说，递归进行时，不能动态地移除栈中的条目）。

在这方面，我主要有两个问题：

1) 如果我把栈限制提高到 sys.setrecursionlimit(15000)，这会在时间上影响性能吗（内存方面我不太在意）？

2) 有没有办法绕过这个限制，假设我可以不依赖栈跟踪。
我问这个是因为Verilog主要处理状态机，而状态机可以用递归函数优雅地实现。

另外，我想补充一下，在递归函数调用的情况下，如果出现了bug，我更依赖于导致这个bug的输入，而不是栈跟踪。

我对Python还很陌生，所以也许专家会说Python的栈跟踪在调试递归函数调用时非常有用……如果是这样的话，我很乐意学习如何使用它。

最后，写递归函数在Python中是否可行，还是说我应该转向其他语言？

如果有任何解决办法让我继续在Python中使用递归函数，我想知道这样做是否会有性能影响（不过我可以进行性能分析）。

Answer 1

注意：这个回答只针对你最上面的那个问题，也就是“在Python中写递归函数是否可取？”

简单来说，答案是否定的，写递归函数并不是特别“推荐”。因为在Python中，没有尾调用优化，递归会变得非常慢，这主要是因为函数调用会消耗很多内存和处理器时间。所以，尽量把你的代码改成循环的方式来写会更好。

Answer 2

针对你提到的第一个问题，改变递归的限制是有风险的，因为这可能会导致底层的C语言栈溢出。你可以看看这个问题：Python中最大的递归深度是多少？如何增加它？

Answer 3

很多事情都取决于你想实现的递归解决方案的具体情况。让我给你举个具体的例子。假设你想计算一个列表中所有数值的总和。你可以通过把第一个数加上剩下部分的总和来设置递归，这样的递归方式应该很明显。不过，这样的递归子问题只比原问题小1，所以递归的调用会随着列表中项目的数量而增加。对于很大的列表，这会成为一个问题。另一种递归方式是注意到，所有数值的总和可以看作是列表前半部分的总和加上后半部分的总和。同样，这样的递归方式也很明显，结束条件是当你处理到长度为1的子列表时。然而，对于这种方式，调用的层数只会增长到列表大小的对数（log₂），这样你就可以处理非常大的列表而不会出现调用堆栈溢出的问题。并不是所有的问题都能分解成大小减半的子问题，但当可以这样做时，这是避免堆栈溢出的一种好方法。

如果你的递归解决方案是尾递归，那么你可以很容易地将其转换为循环，而不是递归调用。

如果没有尾递归的情况，另一种可能性是使用循环来实现，并显式地在一个栈上存储你的中间状态。

Answer 4

查看 Python是否优化尾递归？

Guido Van Rossum（Python的创始人）表示，使用大量递归的做法是“根本不符合Python风格的”。你可以在这里了解更多： http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

不过，很多人还是尝试自己实现这个功能。例如，http://tomforb.es/adding-tail-call-optimization-to-python。或者你可以在网上搜索“python尾调用”。

Answer 5

2) 有没有什么办法可以绕过这个限制，假设我可以不需要堆栈跟踪。我问这个是因为Verilog主要处理状态机，而状态机可以通过递归函数优雅地实现。

其实有办法可以避免尾调用，而不需要对你现有的逻辑做太多改动。你只需要把尾调用改写成返回一个“懒加载”的函数，然后用一个叫做跳板的东西来调用这个函数。如果你需要在状态转换之间传递复杂的状态，可以使用继续传递风格来传递这些状态。这种写代码的方式非常适合用来编写状态机。

举个例子，假设你开始时有一个使用尾调用的递归实现的fizzbuzz状态机，用来控制下一个状态的转换：

def start():
    return increment(0)

def fizz(n):
    print 'fizz'
    return increment(n)

def buzz(n):
    print 'buzz'
    return increment(n)

def fizzbuzz(n):
    print 'fizzbuzz'
    return increment(n)

def increment(n):
    n = n + 1
    if n > 100:
        return terminate()
    elif n % 3 == 0 and n % 5 == 0: 
        return fizzbuzz(n)
    elif n % 3 == 0: 
        return fizz(n)
    elif n % 5 == 0:
        return buzz(n)
    else:
        print n
        return increment(n)

def terminate():
    raise StopIteration

try:
    start()
except StopIteration:
    pass

为了避免尾调用，你只需把所有的尾调用包裹在一个lambda函数（或者用functools.partial）中，然后加上一个跳板：

def start():
    return lambda: increment(0)

def fizz(n):
    print 'fizz'
    return lambda: increment(n)

def buzz(n):
    print 'buzz'
    return lambda: increment(n)

def fizzbuzz(n):
    print 'fizzbuzz'
    return lambda: increment(n)

def increment(n):
    n = n + 1
    if n > 2000:
        # strictly speaking, transitions that takes no arguments
        # like terminate don't need to be wrapped in lambda
        # this is added here only for symmetry with others
        return lambda: terminate()
    elif n % 3 == 0 and n % 5 == 0: 
        return lambda: fizzbuzz(n)
    elif n % 3 == 0: 
        return lambda: fizz(n)
    elif n % 5 == 0:
        return lambda: buzz(n)
    else:
        print n
        return lambda: increment(n)

def terminate():
    raise StopIteration

def trampoline(func): 
    try:
        while True:
            func = func()
    except StopIteration:
        pass

trampoline(lambda: start())

这样你就可以有更多的fizzbuzz，而不会触及递归限制。