Jor*_*ack 182 python stack-overflow recursion stack tail-recursion
我有以下代码失败,出现以下错误:
RuntimeError:超出最大递归深度
我试图重写它以允许尾递归优化(TCO).我相信如果发生TCO,这段代码应该是成功的.
def trisum(n, csum):
if n == 0:
return csum
else:
return trisum(n - 1, csum + n)
print(trisum(1000, 0))
我是否应该断定Python不执行任何类型的TCO,或者我只是需要以不同的方式定义它？
Joh*_*ooy 190
不,自从Guido更喜欢能够进行适当的追溯之后,它永远不会
http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html
http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html
您可以使用这样的转换手动消除递归
>>> def trisum(n, csum):
... while True: # change recursion to a while loop
... if n == 0:
... return csum
... n, csum = n - 1, csum + n # update parameters instead of tail recursion
>>> trisum(1000,0)
500500
Tho*_*hel 164
编辑(2015-07-02): 随着时间的推移,我的答案变得非常受欢迎,因为它最初是一个链接而不是其他任何东西,我决定花一些时间重新写它(但是,最初的答案可以在最后找到).
编辑(2015-07-12):我最后发布了一个执行尾调用优化的模块(处理尾递归和延续传递方式):https://github.com/baruchel/tco
人们经常声称尾递归不适合pythonic编码方式,并且不应该关心如何将它嵌入循环中.我不想与这种观点争论; 但有时我喜欢尝试或实现新的想法作为尾递归函数而不是循环由于各种原因(专注于想法而不是过程,在我的屏幕上同时有20个短函数,而不是只有三个"pythonic"功能,在交互式会话中工作而不是编辑我的代码等).
在Python中优化尾递归实际上非常简单.虽然它被认为是不可能或非常棘手的,但我认为它可以通过优雅,简短和通用的解决方案来实现; 我甚至认为大多数这些解决方案都不会使用Python功能.清晰的lambda表达式与非常标准的循环一起工作,可以实现快速,高效且完全可用的工具,以实现尾递归优化.
为了个人方便,我写了一个小模块,通过两种不同的方式实现这种优化.我想在这里讨论我的两个主要功能.
Y组合器是众所周知的; 它允许以递归方式使用lambda函数,但它本身不允许在循环中嵌入递归调用.单凭Lambda演算不能做这样的事情.然而,Y组合器的微小变化可以保护实际评估的递归调用.因此可以延迟评估.
这是Y组合子的着名表达式:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
稍微改变一下,我可以得到:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
函数f现在返回一个执行完全相同调用的函数,而不是调用自身,但是由于它返回它,因此可以在以后从外部完成评估.
我的代码是:
def bet(func):
b = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = b(*args)
while callable(out):
out = out()
return out
return wrapper
该功能可以按以下方式使用; 这里有两个使用factorial和Fibonacci的尾递归版本的例子:
>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55
显然递归深度不再是问题:
>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42
这当然是该功能的唯一真实目的.
这个优化只能做一件事:它不能用于评估另一个函数的尾递归函数(这来自可调用的返回对象都作为进一步的递归调用而没有区别的事实).由于我通常不需要这样的功能,所以我对上面的代码非常满意.但是,为了提供更通用的模块,我想更多一点,以找到解决此问题的方法(参见下一节).
关于这个过程的速度(然而这不是真正的问题),它恰好是相当不错的; 使用更简单的表达式,使用以下代码甚至可以更快地评估尾递归函数:
def bet1(func):
def wrapper(*args):
out = func(lambda *x: lambda: x)(*args)
while callable(out):
out = func(lambda *x: lambda: x)(*out())
return out
return wrapper
我认为评估一个表达式,甚至复杂,比评估几个简单表达式要快得多,这是第二个版本的情况.我没有在我的模块中保留这个新功能,我认为不能使用它而不是"官方"功能.
这是一个更通用的功能; 它能够处理所有尾递归函数,包括那些返回其他函数的函数.通过使用异常从其他返回值中识别递归调用.这个解决方案比前一个慢; 可以通过使用一些特殊值作为主循环中检测到的"标志"来编写更快的代码,但我不喜欢使用特殊值或内部关键字的想法.使用异常有一些有趣的解释:如果Python不喜欢尾递归调用,当发生尾递归调用时应该引发异常,并且pythonic方法将捕获异常以便找到一些干净解决方案,这实际上是这里发生的......
class _RecursiveCall(Exception):
def __init__(self, *args):
self.args = args
def _recursiveCallback(*args):
raise _RecursiveCall(*args)
def bet0(func):
def wrapper(*args):
while True:
try:
return func(_recursiveCallback)(*args)
except _RecursiveCall as e:
args = e.args
return wrapper
现在可以使用所有功能.在以下示例中,f(n)对n的任何正值求值为identity函数:
>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42
当然,可以认为异常并不是用于意图重定向解释器(作为一种goto陈述或者可能是一种延续传递方式),我不得不承认.但是,我再次发现使用try单行作为return声明的想法很有趣:我们尝试返回一些东西(正常行为),但由于递归调用发生(异常),我们无法做到这一点.
初步答复(2013-08-29).
我写了一个非常小的插件来处理尾递归.你可以在那里找到我的解释:https://groups.google.com/forum/？hl = fr#!topic/comp.lang.python/dIsnJ2BoBKs
它可以在另一个函数中嵌入一个用尾递归样式编写的lambda函数,该函数将它作为循环进行评估.
在我看来,这个小函数中最有趣的特性是函数不依赖于一些脏的编程黑客,而只依赖于lambda演算:当插入另一个lambda函数时,函数的行为被改为另一个函数.看起来很像Y-combinator.
问候.
Jon*_*nts 20
Guido这个词是在http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
我最近在Python历史博客中发布了一篇关于Python功能特性起源的文章.关于不支持尾递归消除(TRE)的一个侧面评论立即引发了一些关于Python没有做到这一点的可能性的评论,包括其他人试图"证明"TRE可以添加到Python的最近博客条目的链接容易.所以,让我捍卫自己的立场(这就是我不想在语言中使用TRE).如果你想要一个简短的答案,它只是简单的unpythonic.这是一个很长的答案:
CPython没有也可能永远不会支持基于Guido关于这个主题的声明的尾调用优化.我听说过,由于它如何修改堆栈跟踪,它使调试变得更加困难.
小智 5
除了优化尾递归，您还可以通过以下方式手动设置递归深度：
import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))