是否建议用Python编写递归函数？
作为实验的一部分，我在python中编写了verilog (逻辑门及其连接性描述)模拟器。
我遇到了堆栈限制的问题，所以我做了一些阅读，发现Python没有“尾调用优化”特性(即在递归过程中动态删除堆栈条目)。
在这方面，我主要有两个问题：
1)如果我将堆栈限制提高到sys.setrecursionlimit(15000)，它在时间方面是否会影响性能(内存--我不在乎)？
( 2)假设我可以在没有堆栈跟踪的情况下生活，我是否可以绕过这一限制。
我之所以这样问是因为Verilog主要处理状态机，它可以使用递归函数以一种优雅的方式实现。
此外，如果可能添加递归函数调用，如果存在bug，则更多地依赖导致此错误的输入，而不是堆栈跟踪。
我对Python并不熟悉，所以专家可能会认为Python堆栈跟踪对于调试递归函数calls...if非常有用--在这种情况下，我非常乐意学习如何做到这一点。
最后，用Python编写递归函数是明智的，还是应该迁移到其他语言？
如果存在任何可以继续使用python进行递归函数的工作，我想知道是否存在任何性能影响(不过，我可以进行分析)。
回答 6
Stack Overflow用户
发布于 2014-08-14 11:28:50
( 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())现在，您可以拥有更多的fizzbuzz，而无需达到递归限制。
Stack Overflow用户
发布于 2014-08-14 00:03:42
Guido说，使用大量递归是“简单的非unpythonic”：http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
但无论如何，许多人都试图获得他们自己的支持。例如http://tomforb.es/adding-tail-call-optimization-to-python。或者只是谷歌的“蟒蛇尾巴呼叫”
Stack Overflow用户
发布于 2014-08-13 23:06:50
注意:这个答案仅限于你的最上面的问题，即“是否建议用Python编写递归函数？”
简短的回答是否定的，这不完全是“明智的”。如果没有尾调用优化，考虑到函数调用在内存和处理器时间上的密集程度，在Python中递归可能会变得非常缓慢。只要有可能，最好以迭代方式重写代码。
https://stackoverflow.com/questions/25297446
复制相似问题
腾讯云开发者
