斐波那契數列(Fibonacci)遞歸與非遞歸的性能對比

費波那契數列由0和1開始，之後的數就由之前的兩數相加 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,……….

遞歸算法

用遞歸算法來求值,非常好理解.偽代碼:

f(n) = 0                (n=0)
f(n) = 1                (n=1)
f(n) = f(n-1) + f(n-2)  (n>1)

實現:

def f(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    elif n>1:
        return f(n-1) + f(n-2)

非遞歸算法

def f(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n>1:

        prev = 1    #第n-1項的值
        p_prev = 0  #第n-2項的值
        result = 1  #第n項的值

        for i in range(1,n):
           result = prev+p_prev 
           p_prev = prev
           prev = result
        return result

功能實現了,但是代碼比較冗長,函數是要對前兩項做特殊判斷.現在優化一下,如何才能更通用,即使是第0個和第1個也能運用到for循環呢?假設在 0, 1, 1, 2, 3, 5, 8, 13... 之前還有兩項, 是-1和1, 即: -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,這樣就通用了:

def f(n):
    prev = 1
    p_prev = -1
    result = 0
    for i in range(n+1):
        result = prev+p_prev
        p_prev = prev
        prev = result
    return result

現在評估一下他們的性能: 寫一個性能裝飾器.

def perfromce_profile(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        rtn = func(*args, **kwargs)
        end = time.time()
        print end-start
        return rtn
    return wrapper

他不能用在遞歸方法中. 所以最終還是寫了這麼個方法:

import time

def f0(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    elif n>1:
        return f(n-1) + f(n-2)

def f(n):
      prev = 1
      p_prev = -1
      result = 0
      for i in range(n+1):
          result = prev+p_prev
          p_prev = prev
          prev = result
      return result   

def perfromce_profile():
    start = time.time()
    f0(1000000)
    end = time.time()
    print end-start
    start = time.time()
    f(1000000)
    print time.time()-start



if __name__ == '__main__':
    perfromce_profile() 

看出性能對比了吧:

54.2904469967
27.7642970085

所以用遞歸弊端還是不少