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

Question

我已经在python中编写了一个verilog(逻辑门及其连接描述)模拟器作为实验的一部分.

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

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

1)如果我提高了堆栈限制,sys.setrecursionlimit(15000)它是否会影响性能(内存 - 我不在乎)？

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

另外,如果我可以添加,在递归函数调用的情况下,如果有错误,我更依赖于导致此错误的输入而不是堆栈跟踪.

我是Python新手,所以也许专家可能认为Python堆栈跟踪对于调试递归函数调用非常有用......如果是这种情况,我会非常乐意学习如何做到这一点.

最后,建议在Python中编写递归函数还是应该转移到其他语言？

如果有任何解决方法,我可以继续使用python进行递归函数,我想知道是否有任何性能影响(我可以做分析).

Answer 1

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

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

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

现在你可以在不达到递归限制的情况下获得更多的嘶嘶声。