斐波那契數(shù)列（Fibonacci sequence）巡扇，又稱黃金分割數(shù)列蹋半、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入嗅榕，故又稱為“兔子數(shù)列”窥突，指的是這樣一個(gè)數(shù)列：1、1今布、2经备、3、5部默、8侵蒙、13、21傅蹂、34纷闺、……
一.運(yùn)用遞歸函數(shù)
1.遞歸函數(shù)：在函數(shù)的內(nèi)部,可以調(diào)用其他的函數(shù),如果一個(gè)函數(shù)在內(nèi)部調(diào)用自身本身,這個(gè)函數(shù)就是遞歸函數(shù).
2.使用遞歸解決問(wèn)題的思路：
（1）.寫(xiě)出臨界條件
（2）.找這一次和上一次的關(guān)系
（3）.假設(shè)當(dāng)前函數(shù)已經(jīng)能用,調(diào)用自身計(jì)算上一次的結(jié)果,再求出本次的結(jié)果
思路：
'''
求斐波那契數(shù)列：1,1,2,3,5,8,13,21,34,55,89.....
找臨界值f(1) = 1
f(2) = 1
f(3) = f(1)+f(2)
f(n) = f(n-1)+f(n-2)
'''
3.代碼：
def func(n):
if n==1 or n==2:
return 1
else:
return func(n-1)+func(n-2)
print(func(4))
print(func(5))
print(func(6))
print(func(7))
print(func(40))
注意:使用遞歸函數(shù)需要注意防止棧溢出,在計(jì)算機(jī)中函數(shù)是通過(guò)棧(stack)這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的,每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用,就會(huì)增加一層棧幀,每當(dāng)函數(shù)返回,棧就會(huì)減一層棧幀,棧的大小是有限制的,所以當(dāng)調(diào)用的次數(shù)過(guò)多的時(shí)候,會(huì)導(dǎo)致棧溢出
4.運(yùn)行結(jié)果：
二.運(yùn)用for循環(huán)
for循環(huán)
語(yǔ)法：
for 變量 in 序列：
循環(huán)體
序列：列表 ，元組 份蝴，字典 犁功，set集合 ，字符串 婚夫，range
執(zhí)行過(guò)程：依次從序列中取出一個(gè)元素賦值給變量浸卦，然后執(zhí)行一次循環(huán)體，
繼續(xù)去下一個(gè)请敦，當(dāng)所有的元素都被取出【序列為空】的情況下镐躲，循環(huán)完畢，退出循環(huán)侍筛。
2.代碼：
def feibo(n):
a = 0
b = 1
if n == 1 or n == 2:
return 1
for x in range(1,n):
a,b = b,a+b
return b
print(feibo(1))
print(feibo(2))
print(feibo(3))
print(feibo(4))
print(feibo(5))
print(feibo(6))
print(feibo(7))
3.運(yùn)行結(jié)果：
三.兩者比較
遞歸考慮棧溢出，遞歸性能不如循環(huán)撒穷。n值大的話循環(huán)很快就能出結(jié)果匣椰，遞歸則很慢。遞歸函數(shù)的優(yōu)點(diǎn)是定義簡(jiǎn)單,邏輯清晰,理論上所有的遞歸函數(shù)都可以寫(xiě)成循環(huán)的方式,但是循環(huán)的邏輯不如遞歸清晰.
