Python中使用裝飾器來優化尾遞歸-Python教學-PHP中文網

Python中使用裝飾器來優化尾遞歸

高洛峰

發布： 2017-03-02 10:55:03

原創

1691 人瀏覽過

這裡我們用典型的斐波那契數列作為例子,來展示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)

登入後複製

這段程式我們來測試一下，呼叫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,如下：

@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神奇的打破了呼叫堆疊的限制。

這下即使我們Fib(20000)，也能在780ms跑出結果（780ms是以前博文提到那台2000元的上網本跑出來的結果）

不賣關子了，下面我們來看看這段神奇的程式碼：

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&#39;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

登入後複製

使用的方法前面已經展示了，令我感到大開眼界的是，作者用了拋出異常然後自己捕獲的方式來打破調用棧的增長，簡直是太匪夷所思了。而且效率問題，和直接尾遞歸Fib相比大概造成了五倍的時間開銷。

最後很不可思議的，尾遞歸優化的目的達成了。

更多Python中使用裝飾器來優化尾遞歸相關文章請關注PHP中文網！