斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：
1讯壶、1料仗、2、3伏蚊、5立轧、8、13、21氛改、34匀借、……
在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞推的方法定義：F(1)=1平窘，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)
即吓肋，除前兩位數(shù)等于1外，后面一個(gè)數(shù)是前兩個(gè)數(shù)的和瑰艘；
在python實(shí)現(xiàn)斐波那契數(shù)列的打印時(shí)是鬼，會(huì)有三種方法
實(shí)現(xiàn)代碼如下：
# 方法一：直接用遞歸求斐波那契數(shù)列第n個(gè)數(shù)值
# 該種求法，n越大效率越低紫新，因?yàn)槊看吻笾稻郏紩?huì)重新把前面的數(shù)算一遍
# 每次遞歸，都會(huì)重新創(chuàng)建棧芒率，n較大時(shí)很容易爆棧
def feibona(n):
if n < 2:
return n
return feibona(n - 1) + feibona(n - 2)
# 方法二：使用尾遞歸求斐波那契數(shù)列第n個(gè)數(shù)值
# 該種求法囤耳，效率較高
def feibona_tial(n, a, b):
if n == 0:
return a
return feibona_tial(n - 1, b, a + b)
# 方法三：循環(huán)求斐波那契數(shù)列第n個(gè)數(shù)值
# 該種求法，效率最高
def feibona_while(n):
a = 0
b = 1
if n == 0:
return a
if n == 1:
return b
for i in range(1, n):
c = a + b
a = b
b = c
return c
if __name__ == '__main__':
for i in range(100):
print(feibona_while(i)) # 循環(huán)
for i in range(100):
print(feibona_tial(i, 0, 1)) # 尾遞歸
for i in range(100):
print(feibona(i)) # 遞歸
對(duì)于以上三種實(shí)現(xiàn)方法偶芍，運(yùn)行后很容易就會(huì)發(fā)現(xiàn)
1.循環(huán)實(shí)現(xiàn)充择，效率最高；
2.尾遞歸實(shí)現(xiàn)匪蟀，效率次之椎麦，也較快；
3.遞歸實(shí)現(xiàn)材彪，當(dāng)數(shù)字較大時(shí)观挎，速度越來越慢；
這里有必要說一下段化，并不是所有語(yǔ)言都支持尾遞歸的嘁捷，比如python中其實(shí)就是不支持尾遞歸的，
因?yàn)閷?duì)于較大的層數(shù)調(diào)用显熏，尾遞歸依然會(huì)爆棧雄嚣，
比如我在調(diào)用尾遞歸時(shí)，n=998不會(huì)報(bào)錯(cuò)佃延，但是n=999時(shí)就會(huì)爆棧
但是在爆棧層數(shù)之前慢哈，尾遞歸比普通遞歸的效率高很多很多很多浑吟；
所以大家在使用，遞歸扣蜻、尾遞歸時(shí)坐桩，需要酌情考慮尺棋，遞歸層級(jí)較低時(shí)可以使用尾遞歸；
能用循環(huán)實(shí)現(xiàn)的，還是使用循環(huán)膘螟，邏輯雖然復(fù)雜點(diǎn)成福，但效率仍然不失是最佳的；
