用程序算斐波那契數(shù)列最常見的就是迭代與遞歸算法赖舟。
為了評價各算法程序效率如何
安裝 profiler 來計時和能看到每行的運行次數(shù)
先在系統(tǒng)下輸入命令pip install line_profiler安裝
使用也很簡單吟孙，在要計時的函數(shù)定義前加上@profile這個裝飾符
然后在系統(tǒng)下輸入命令kernprof -l -v 被計時的源程序.py
開始看第一個程序呼寸，輸入?yún)?shù)n算第n項的Fibonacci數(shù)。以下皆是在Python 3.7環(huán)境下運行
1.? 非遞歸的迭代解法
def Fibonacci_sequence_01 (n: int) -> int: #參數(shù)n是表示求第n項Fibonacci數(shù)
? ? '返回單項的for迭代解法'
??? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? if n>=2:
? ? ? ? prev_num, current_num = 0, 1
? ? ? ? for i in range(2, n+1):
? ? ? ? ? ? prev_num, current_num = current_num, prev_num+current_num
? ? ? ? return current_num
? ? elif n==1:
? ? ? ? return 1
? ? elif n==0:
? ? ? ? return 0
? ? else:
? ? ? ? return None
Fibonacci_sequence_01(1200)
用算到第1200項Fibonacci數(shù)來測量下用時
在我的電腦上Total time: 0.002855秒
2.? 典型的遞歸解法精肃，算法可讀性很好
def Fibonacci_sequence_02 (n: int) -> int: #參數(shù)n是表示求第n項Fibonacci數(shù)
? ? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? def Calculate_Fibonacci_sequence (n: int) -> int:
? ? ? ? '返回單項的遞歸解法'
? ? ? ? if n>=2:
? ? ? ? ? ? return Calculate_Fibonacci_sequence(n-1) + Calculate_Fibonacci_sequence(n-2)
? ? ? ? elif n==1:
? ? ? ? ? ? return 1
? ? ? ? elif n==0:
? ? ? ? ? ? return 0
? ? if n>=0:
? ? ? ? Calculate_Fibonacci_sequence(n)
? ? else:
? ? ? ? return None
然而，時間復(fù)雜度是：O(1.618 ^ n)周偎，沒有實用價值。這個時間復(fù)雜度的詳解見“算法的時間復(fù)雜度”這篇文章
3.? 尾遞歸解法
遞歸解法的一個缺點是遞歸調(diào)用會一層一層壓棧撑帖，占用椚乜玻空間達O(n)。特別是Python默認只設(shè)1000層胡嘿，超過就拋出異常了
尾遞歸算法相當(dāng)于迭代的變形蛉艾，理論上尾遞歸不需要保留調(diào)用前信息，椫缘校空間只需要O(1)勿侯。但是Python沒有針對尾遞歸形式做識別，尾遞歸調(diào)用時還是有一層一層壓棧動作缴罗，超出默認棧深度就不行了助琐。對于不支持尾遞歸優(yōu)化的語言，這時要用一個叫“蹦床（Trampoline）”的技巧
“蹦床”也就是對遞歸函數(shù)進行包裝面氓，蹦床攔截了傳給遞歸函數(shù)的參數(shù)兵钮，遞歸函數(shù)代碼的加載過程都透過這個蹦床。每次的遞歸調(diào)用舌界，實際都被蹦床轉(zhuǎn)化為蹦床去拿攔截的參數(shù)調(diào)用一次遞歸函數(shù)掘譬，這樣棧空間占用一直為O(1)
來看裝飾器樣式呻拌，樣子如：
先對尾遞歸函數(shù)加上裝飾器
@proper_tail_call
def Fibonacci_sequence(n):
然后使用時就是原樣不變的函數(shù)調(diào)用樣式
Fibonacci_sequence(n)
好了葱轩，下面就是完整的尾遞歸裝飾器及尾遞歸解法斐波那契數(shù)
import functools
import inspect
class TailCallException(Exception):
? ? def __init__(self, *args, **kwargs):
? ? ? ? self.args = args
? ? ? ? self.kwargs = kwargs
def proper_tail_call(func):
? ? '用于return式尾遞歸的蹦床裝飾器代碼。使用方法：在定義尾遞歸函數(shù)語句前一行寫裝飾器“@proper_tail_call”'
? ? @functools.wraps(func)
? ? def wrapper(*args, **kwargs):
? ? ? ? frame = inspect.currentframe()
? ? ??? if frame.f_back and frame.f_back.f_back and frame.f_code ==frame.f_back.f_back.f_code: #先判斷當(dāng)前是否為遞歸調(diào)用（遞歸的話是_wrapper->被裝飾函數(shù)->_wrapper）柏锄，再判斷是否存在前級和前前級調(diào)用
? ? ? ? ? ? raise TailCallException(*args, **kwargs)
? ? ? ? else:
? ? ? ? ? ? while True:
? ? ? ? ? ? ? ? try:
? ? ? ? ? ? ? ? ? ? return func(*args, **kwargs)
? ? ? ? ? ? ? ? except TailCallException as e:
? ? ? ? ? ? ? ? ? ? args = e.args
? ? ? ? ? ? ? ? ? ? kwargs = e.kwargs
? ? return wrapper
def Fibonacci_sequence_03 (n: int) -> int: #參數(shù)n是表示求第n項Fibonacci數(shù)
??? assert isinstance(n, int), 'n is an error of non-integer type.'
? ? @proper_tail_call
? ? def Calculate_Fibonacci_sequence (n: int, prev_num: int =0, current_num: int =1) -> int:
? ? ? ? '返回單項的return式尾遞歸解法'
? ? ? ? if n>=2:
? ? ? ? ? ? return Calculate_Fibonacci_sequence(n-1, current_num, prev_num+current_num)
? ? ? ? elif n==1:
? ? ? ? ? ? return current_num
? ? if n>=1:
? ? ? ? return Calculate_Fibonacci_sequence (n)
? ? elif n==0:
? ? ? ? return 0
? ? else:
? ? ? ? return None
Fibonacci_sequence_03(1200)
還是用算到第1200項Fibonacci數(shù)來測量下用時酿箭，Total time: 0.011484秒
未完待續(xù)……
