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

Question

作为实验的一部分，我用 python 编写了一个 verilog(基本上是逻辑门及其连接描述)模拟器。

我遇到了堆栈限制的问题，所以我做了一些阅读，发现 Python 没有“尾调用优化”功能(即随着递归的进行动态删除堆栈条目)

这方面我主要有两个问题:

1) 如果我将堆栈限制提高到 sys.setrecursionlimit(15000) 是否会影响时间(内存 - 我不关心)方面的性能？

2) 假设我可以在没有堆栈跟踪的情况下生活，有什么方法可以绕过这个限制。
我问这个是因为 Verilog 主要处理状态机，可以使用递归函数以优雅的方式实现。

此外，如果我可以添加，在递归函数调用的情况下，如果存在错误，我更多地依赖导致此错误的输入而不是堆栈跟踪。

我是 Python 的新手，所以专家可能会争辩说 Python 堆栈跟踪对于调试递归函数调用非常有用……如果是这样的话，我会非常乐意学习如何做到这一点。

最后，用 Python 编写递归函数是否可取，还是我应该转向其他语言？

如果有任何变通方法可以让我继续使用 python 进行递归函数，我想知道是否会对性能产生任何影响(不过我可以进行分析)。

Answer 1

2) Is there any way I can circumvent this limitation assuming that I can live without a stack-trace. I ask this because Verilog mainly deals with state-machines which can be implemented in an elegant way using recursive functions.

有一种方法可以在不过多改变现有逻辑的情况下避免尾调用，只需重写尾调用以返回一个 thunk 并使用 trampoline。调用那个thunk。如果需要在转换之间传递复杂状态，可以使用 continuation passing style传递它们。这种编写代码的风格非常适合编写状态机。

一个例子可能更清楚，假设您从 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。