是否建议用Python编写递归函数

sanjay 发表于 Dev

桑杰

作为实验的一部分，我在python中编写了一个Verilog（逻辑门及其连接描述）。

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

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

1）如果我增加了堆栈限制，这sys.setrecursionlimit(15000)是否会影响时间性能（内存-我不在乎）？

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

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

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

最后，建议使用Python编写递归函数，还是应该转向其他语言？

如果有任何变通办法，使得我可以继续将python用于递归函数，我想知道是否有任何性能影响（尽管我可以进行性能分析）。

烈瑞恩

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())