TRE=Tail Recursion Elimination

创始人是不愿意实现TRE的.他专门用了一篇文章来阐述原因.

1.不利于查BUG.

2.现有的1000递归深度够用.

3.递归不是所有编程的基础,也不是一个日常工具.

4.他举了个例子说明第四点,大概是指Python动态的特性不适合递归:

def f(x):    print 'original'    if x > 0:        return f(x-1)    return 0g = fdef f(x):    print 'new'    return xprint g(5)

最终结果是4:

originalnew4

最后总结:

After all TRE only addresses recursion that can easily be replaced by a loop.

意思应该是说所有真正需要TRE的地方都能轻松改写为循环.

看来我是不能指望Python语言支持TRE了.

 

但还是有很多顽强的程序员用各种方法变相支持TRE.比如下面这位还用装饰器的形式实现了.

class TailCaller(object) :    def __init__(self, f) :        self.f = f    def __call__(self, *args, **kwargs) :        ret = self.f(*args, **kwargs)        while type(ret) is TailCall :            ret = ret.handle()        return retclass TailCall(object) :    def __init__(self, call, *args, **kwargs) :        self.call = call        self.args = args        self.kwargs = kwargs    def handle(self) :        if type(self.call) is TailCaller :            return self.call.f(*self.args, **self.kwargs)        else :            return self.f(*self.args, **self.kwargs)@TailCallerdef fact(n, r=1) :    if n <= 1 :        return r    else :        return TailCall(fact, n-1, n*r) print fact(2500)

 

最朴素的形式是:

def TCO(f):        def inner(*nkw,**kw):        result=f(*nkw,**kw)        while callable(result):            result=result()        return result    return inner        def fab(n,s=1):    if n<2:        return s    else:        return lambda :fab(n-1,s*n)tcoFab=TCO(fab)print tcoFab(2500)

这个更容易理解,性能也应该会更好,只是行文略显复杂了一点点.主要是由于Python运行时的动态特性,你不能使用更酷的装饰器形式fab=TCO(fab).

我个人是比较支持这种朴素形式的.

 

网上还有其他一些什么抛出异常法之类的,用到了sys模块,太复杂了,看不懂,故不用.