詳解python使用遞歸、尾遞歸、循環(huán)三種方式實現斐波那契數列
在最開始的時候所有的斐波那契代碼都是使用遞歸的方式來寫的，遞歸有很多的缺點，執(zhí)行效率低下，浪費資源，還有可能會造成棧溢出，而遞歸的程序的優(yōu)點也是很明顯的，就是結構層次很清晰，易于理解
可以使用循環(huán)的方式來取代遞歸，當然也可以使用尾遞歸的方式來實現。
尾遞歸就是從最后開始計算, 每遞歸一次就算出相應的結果, 也就是說, 函數調用出現在調用者函數的尾部, 因為是尾部, 所以根本沒有必要去保存任何局部變量. 直接讓被調用的函數返回時越過調用者, 返回到調用者的調用者去。尾遞歸就是把當前的運算結果（或路徑）放在參數里傳給下層函數，深層函數所面對的不是越來越簡單的問題，而是越來越復雜的問題，因為參數里帶有前面若干步的運算路徑。尾遞歸是極其重要的，不用尾遞歸，函數的堆棧耗用難以估量，需要保存很多中間函數的堆棧。直接遞歸的程序中需要保存之前n步操作的所有狀態(tài)極其耗費資源，而尾遞歸不需要，尾部遞歸是一種編程技巧。如果在遞歸函數中，遞歸調用返回的結果總被直接返回，則稱為尾部遞歸。尾部遞歸的函數有助將算法轉化成函數編程語言，而且從編譯器角度來說，亦容易優(yōu)化成為普通循環(huán)。這是因為從電腦的基本面來說，所有的循環(huán)都是利用重復移跳到代碼的開頭來實現的。如果有尾部歸遞，就只需要疊套一個堆棧，因為電腦只需要將函數的參數改變再重新調用一次
為了加深對尾遞歸、遞歸和循環(huán)的對比，這里以斐波那契數列的實現舉例：
#!usr/bin/env python
#encoding:utf-8
'''''''
__Author__:沂水寒城
功能：尾遞歸
'''
import time
def Fib_recursion(num):
'''''
直接使用遞歸法求解斐波那契數量的第num個數字
'''
if num<2:
return num
return Fib_recursion(num-1)+Fib_recursion(num-2)
def Fib_tail_recursion(num,res,temp):
'''''
使用尾遞歸法求解斐波那契數量的第num個數字
'''
if num==0:
return res
else:
return Fib_tail_recursion(num-1, temp, res+temp)
def Fib_circle(num):
'''''
直接使用循環(huán)來求解
'''
a=0
b=1
for i in range(1,num):
c=a+b
a=b
b=c
return c
if __name__ == '__main__':
num_list=[5,10,20,30,40,50]
for num in num_list:
start_time=time.time()
print Fib_recursion(num)
end_time=time.time()
print Fib_tail_recursion(num,0,1)
end_time2=time.time()
print Fib_circle(num)
end_time3=time.time()
print '正在求解的斐波那契數字下標為%s' %num
print '直接遞歸耗時為 ：', end_time-start_time
print '尾遞歸調用耗時為：', end_time2-end_time
print '直接使用循環(huán)耗時為：', end_time3-end_time2
結果如下：
5 5 5 正在求解的斐波那契數字下標為5 直接遞歸耗時為 ： 6.38961791992e-05 尾遞歸調用耗時為： 2.31266021729e-05 直接使用循環(huán)耗時為： 1.97887420654e-05 55 55 55 正在求解的斐波那契數字下標為10 直接遞歸耗時為 ： 6.60419464111e-05 尾遞歸調用耗時為： 3.31401824951e-05 直接使用循環(huán)耗時為： 1.8835067749e-05 6765 6765 6765 正在求解的斐波那契數字下標為20 直接遞歸耗時為 ： 0.00564002990723 尾遞歸調用耗時為： 3.09944152832e-05 直接使用循環(huán)耗時為： 2.09808349609e-05 832040 832040 832040 正在求解的斐波那契數字下標為30 直接遞歸耗時為 ： 0.39971113205 尾遞歸調用耗時為： 1.69277191162e-05 直接使用循環(huán)耗時為： 1.19209289551e-05 102334155 102334155 102334155 正在求解的斐波那契數字下標為40 直接遞歸耗時為 ： 39.0365440845 尾遞歸調用耗時為： 2.19345092773e-05 直接使用循環(huán)耗時為： 1.78813934326e-05 12586269025 12586269025 12586269025 正在求解的斐波那契數字下標為50 直接遞歸耗時為 ： 4915.68643498 尾遞歸調用耗時為： 2.19345092773e-05 直接使用循環(huán)耗時為： 2.09808349609e-05
畫圖圖表更加清晰地可以看到差距：
因為差距太大，導致尾遞歸和循環(huán)的兩種方式的時間增長幾乎是水平線，而直接遞歸的時間增長接近90度。
這一次，感覺自己好有耐心，一直就在那里等著程序出結果，可以看到三者的時間對比狀況，很明顯的：直接遞歸的時間增長的極快，而循環(huán)的性能還要優(yōu)于尾遞歸，這就告訴我們盡量減少遞歸的使用，使用循環(huán)的方式代替遞歸無疑是一種提高程序運行效率的方式。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
今天小編就為大家分享一篇Pytorch 多塊GPU的使用詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
本文主要介紹了NumPy進行統(tǒng)計分析，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-05-05
這篇文章主要介紹了在VScode中引用自定義模塊問題,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-07-07
本文主要介紹了pytest中配置文件pytest.ini使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
itertools是python內置的模塊，使用簡單且功能強大。本文將詳細為大家講解一下itertools模塊的使用方法，感興趣的小伙伴可以學習一下2022-05-05
在本篇文章里小編給各位整理了關于python設置環(huán)境變量的作用和實例內容知識點，需要的朋友們學習參考下。2019-07-07
這篇文章主要給大家介紹了關于Python內置數據結構列表與元組的相關資料,列表是順序存儲的數據結構,類似于數據結構中的順序表,在存儲上是相連的一大塊內存空間,在物理和邏輯上都是連續(xù)的,需要的朋友可以參考下2021-08-08
巧妙使用Python裝飾器處理if...elif...else
大家好，今天在 Github 閱讀 EdgeDB[1] 的代碼，發(fā)現它在處理大量if…elif…else的時候，巧妙地使用了裝飾器，方法設計精巧，分享給大家一下，歡迎收藏學習，喜歡點贊支持2021-11-11
今天小編就為大家分享一篇使用Python監(jiān)視指定目錄下文件變更的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10
這篇文章主要給大家介紹了關于如何向Pandas?DataFrame添加行的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2022-03-03