偶然在國外一個網站瞅到的，非常的酷，發出來共用一下。一般來說，Python和Java，C#一樣是沒有尾遞歸自動優化的能力的，遞歸調用受到調用棧長度的限制被廣泛的詬病，但是這個狂人用一個匪夷所思的方法解決了這個問題併在Python上實現了，從此Python的遞歸調用再也不用受到調用棧長度的制約，太酷了 ...
偶然在國外一個網站瞅到的，非常的酷，發出來共用一下。一般來說，Python和Java，C#一樣是沒有尾遞歸自動優化的能力的，遞歸調用受到調用棧長度的限制被廣泛的詬病，但是這個狂人用一個匪夷所思的方法解決了這個問題併在Python上實現了，從此Python的遞歸調用再也不用受到調用棧長度的制約，太酷了。
首先我們還是從遞歸說起，之前我發過一篇 《淺談遞歸過程以及遞歸的優化》其中用到了斐波那契數來作為例子.線性遞歸的演算法由於太過一低效就被我們Pass掉了，我們先來看尾遞過方式的調用：
1 def Fib(n,b1=1,b2=1,c=3):2 if n<3:
3 return 1
4 else:
5 if n==c:
6 return b1+b2
7 else:
8 return Fib(n,b1=b2,b2=b1+b2,c=c+1)
9
這段程式我們來測試一下，調用 Fib(1001)結果：
>>> def Fib(n,b1=1,b2=1,c=3):
... if n<3:
... return 1
... else:
... if n==c:
... return b1+b2
... else:
... return Fib(n,b1=b2,b2=b1+b2,c=c+1)
...
>>> Fib(1001)
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L
>>>
如果我們用Fib(1002)，結果，茶几了，如下：
.....
File "<stdin>", line 8, in Fib
File "<stdin>", line 8, in Fib
File "<stdin>", line 8, in Fib
File "<stdin>", line 8, in Fib
File "<stdin>", line 8, in Fib
File "<stdin>", line 8, in Fib
RuntimeError: maximum recursion depth exceeded
>>>
好了，現在我們來尾遞歸優化
我們給剛纔的Fib函數增加一個Decorator,如下：
1 @tail_call_optimized
2 def Fib(n,b1=1,b2=1,c=3):3 if n<3:
4 return 1
5 else:
6 if n==c:
7 return b1+b2
8 else:
9 return Fib(n,b1=b2,b2=b1+b2,c=c+1)
恩，就是這個@tail_call_optimized的裝飾器 ，這個裝飾器使Python神奇的打破了調用棧的限制。
這下即使我們Fib(20000)，也能在780ms跑出結果（780ms是以前博文提到那台2000元的上網本跑出來的結果）
不賣關子了，下麵我們來看看這段神奇的代碼：
1 import sys 2
3 class TailRecurseException:
4 def __init__(self, args, kwargs):
5 self.args = args
6 self.kwargs = kwargs
7
8 def tail_call_optimized(g):
9 """
10 This function decorates a function with tail call
11 optimization. It does this by throwing an exception
12 if it is it's own grandparent, and catching such
13 exceptions to fake the tail call optimization.
14
15 This function fails if the decorated
16 function recurses in a non-tail context.
17 """
18 def func(*args, **kwargs):
19 f = sys._getframe()
20 if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
21 raise TailRecurseException(args, kwargs)
22 else:
23 while 1:
24 try:
25 return g(*args, **kwargs)
26 except TailRecurseException, e:
27 args = e.args
28 kwargs = e.kwargs
29 func.__doc__ = g.__doc__
30 return func
31
使用的方法前面已經展示了，令我感到大開眼界的是，作者用了拋出異常然後自己捕獲的方式來打破調用棧的增長，簡直是太匪夷所思了。而且效率問題，和直接尾遞歸Fib相比大概造成了五倍的時間開銷。
最後很不可思議的，尾遞歸優化的目的達成了。
