這裡我們用典型的斐波那契數列作為例子,來展示Python中使用裝飾器來優化尾遞歸的範例,需要的朋友可以參考下
尾遞歸簡介
尾遞歸是函數傳回最後一個操作是遞歸調用，則該函數是尾遞歸。
遞歸是線性的例如factorial函數每一次呼叫都會創建一個新的棧(last-in-first-out)透過不斷的壓棧，來創建遞歸, 很容易導致棧的溢出。而尾遞歸則使用目前堆疊透過資料覆蓋來最佳化遞歸函數。
階乘函數factorial, 透過把計算值傳遞的方法完成了尾遞歸。但python不支出編譯器優化尾遞歸所以當遞歸多次的話還是會報錯(學習用)。
eg：
def factorial(n, x):
if n == 0:
return x
else:
return factorial(n-1, n*x)
print factorial(5, 1) # 120#尾遞歸最佳化##這裡用到了斐波那契數來當例子.線性遞歸的演算法由於太過一低效就被我們Pass掉了，我們先來看尾遞過方式的呼叫：
(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)
>>> 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 >>>
..... 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 >>>
@tail_call_optimized 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)
恩，就是這個@tail_call_optimized的裝飾器，這個裝飾器讓Python神奇的打破了呼叫堆疊的限制。
class TailRecurseException: def __init__(self, args, kwargs): self.args = args self.kwargs = kwargs def tail_call_optimized(g): """ This function decorates a function with tail call optimization. It does this by throwing an exception if it is it's own grandparent, and catching such exceptions to fake the tail call optimization. This function fails if the decorated function recurses in a non-tail context. """ def func(*args, **kwargs): f = sys._getframe() if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: raise TailRecurseException(args, kwargs) else: while 1: try: return g(*args, **kwargs) except TailRecurseException, e: args = e.args kwargs = e.kwargs func.__doc__ = g.__doc__ return func
