快捷導(dǎo)航

詳解python使用遞歸、尾遞歸、循環(huán)三種方式實現(xiàn)斐波那契數(shù)列

更新時間：2018年01月16日 16:22:47 作者：Together_CZ

本篇文章主要介紹了python使用遞歸、尾遞歸、循環(huán)三種方式實現(xiàn)斐波那契數(shù)列，非常具有實用價值，需要的朋友可以參考下

在最開始的時候所有的斐波那契代碼都是使用遞歸的方式來寫的，遞歸有很多的缺點，執(zhí)行效率低下，浪費資源，還有可能會造成棧溢出，而遞歸的程序的優(yōu)點也是很明顯的，就是結(jié)構(gòu)層次很清晰，易于理解

可以使用循環(huán)的方式來取代遞歸，當(dāng)然也可以使用尾遞歸的方式來實現(xiàn)。

尾遞歸就是從最后開始計算, 每遞歸一次就算出相應(yīng)的結(jié)果, 也就是說, 函數(shù)調(diào)用出現(xiàn)在調(diào)用者函數(shù)的尾部, 因為是尾部, 所以根本沒有必要去保存任何局部變量. 直接讓被調(diào)用的函數(shù)返回時越過調(diào)用者, 返回到調(diào)用者的調(diào)用者去。尾遞歸就是把當(dāng)前的運算結(jié)果（或路徑）放在參數(shù)里傳給下層函數(shù)，深層函數(shù)所面對的不是越來越簡單的問題，而是越來越復(fù)雜的問題，因為參數(shù)里帶有前面若干步的運算路徑。尾遞歸是極其重要的，不用尾遞歸，函數(shù)的堆棧耗用難以估量，需要保存很多中間函數(shù)的堆棧。直接遞歸的程序中需要保存之前n步操作的所有狀態(tài)極其耗費資源，而尾遞歸不需要，尾部遞歸是一種編程技巧。如果在遞歸函數(shù)中，遞歸調(diào)用返回的結(jié)果總被直接返回，則稱為尾部遞歸。尾部遞歸的函數(shù)有助將算法轉(zhuǎn)化成函數(shù)編程語言，而且從編譯器角度來說，亦容易優(yōu)化成為普通循環(huán)。這是因為從電腦的基本面來說，所有的循環(huán)都是利用重復(fù)移跳到代碼的開頭來實現(xiàn)的。如果有尾部歸遞，就只需要疊套一個堆棧，因為電腦只需要將函數(shù)的參數(shù)改變再重新調(diào)用一次

為了加深對尾遞歸、遞歸和循環(huán)的對比，這里以斐波那契數(shù)列的實現(xiàn)舉例：

#!usr/bin/env python  
#encoding:utf-8    
''''''' 
__Author__:沂水寒城 
功能：尾遞歸 
'''   
import time 
def Fib_recursion(num): 
  ''''' 
  直接使用遞歸法求解斐波那契數(shù)量的第num個數(shù)字 
  ''' 
  if num<2: 
   return num  
  return Fib_recursion(num-1)+Fib_recursion(num-2) 
 
def Fib_tail_recursion(num,res,temp): 
  ''''' 
  使用尾遞歸法求解斐波那契數(shù)量的第num個數(shù)字 
  ''' 
  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 '正在求解的斐波那契數(shù)字下標(biāo)為%s' %num 
    print '直接遞歸耗時為 ：', end_time-start_time 
    print '尾遞歸調(diào)用耗時為：', end_time2-end_time 
    print '直接使用循環(huán)耗時為：', end_time3-end_time2

結(jié)果如下：

5 
5 
5 
正在求解的斐波那契數(shù)字下標(biāo)為5 
直接遞歸耗時為 ： 6.38961791992e-05 
尾遞歸調(diào)用耗時為： 2.31266021729e-05 
直接使用循環(huán)耗時為： 1.97887420654e-05 
55 
55 
55 
正在求解的斐波那契數(shù)字下標(biāo)為10 
直接遞歸耗時為 ： 6.60419464111e-05 
尾遞歸調(diào)用耗時為： 3.31401824951e-05 
直接使用循環(huán)耗時為： 1.8835067749e-05 
6765 
6765 
6765 
正在求解的斐波那契數(shù)字下標(biāo)為20 
直接遞歸耗時為 ： 0.00564002990723 
尾遞歸調(diào)用耗時為： 3.09944152832e-05 
直接使用循環(huán)耗時為： 2.09808349609e-05 
832040 
832040 
832040 
正在求解的斐波那契數(shù)字下標(biāo)為30 
直接遞歸耗時為 ： 0.39971113205 
尾遞歸調(diào)用耗時為： 1.69277191162e-05 
直接使用循環(huán)耗時為： 1.19209289551e-05 
102334155 
102334155 
102334155 
正在求解的斐波那契數(shù)字下標(biāo)為40 
直接遞歸耗時為 ： 39.0365440845 
尾遞歸調(diào)用耗時為： 2.19345092773e-05 
直接使用循環(huán)耗時為： 1.78813934326e-05 
12586269025 
12586269025 
12586269025 
正在求解的斐波那契數(shù)字下標(biāo)為50 
直接遞歸耗時為 ： 4915.68643498 
尾遞歸調(diào)用耗時為： 2.19345092773e-05 
直接使用循環(huán)耗時為： 2.09808349609e-05

畫圖圖表更加清晰地可以看到差距：