斐波那契數(shù)列：
1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10? ?...
1 ? ? 1 ? ? 2 ? ? 3 ? ? 5 ? ? 8 ? ?13 ? 21 ? 34 ? ?55? ?...

1.用迭代實(shí)現(xiàn)斐波那契數(shù)列(非遞歸方法)

            
              def fab(n): ? 
?? ?n1 = 1 ? ? ?
?? ?n2 = 1 ? ? ?
?? ?n3 = 1 ? ? 

?? ?if n < 1: ? 
?? ??? ?print('輸入有誤！')
?? ?
?? ?while (n-2) > 0: ? ?
?? ??? ?n3 = n2 + n1 ? #第三項(xiàng)為前兩項(xiàng)和
?? ??? ?n1 = n2 ? ? ? ? ? ?#計(jì)算完，整體后移，準(zhǔn)備計(jì)算下一項(xiàng) ?
?? ??? ?n2 = n3 ? ? ? ? ? ?
?? ??? ?n -= 1 ? ? ? ? ? ? ?

?? ?return n3 ? ? ? ? ? ?

a = int(input('請(qǐng)輸入要計(jì)算的斐波那契項(xiàng)數(shù)：'))
result = fab(a)
print('第%d項(xiàng)斐波那契數(shù)為%d' % (a, result))
            
          

2.遞歸方法
? 原理：（樹形結(jié)構(gòu)圖）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Fab(5)
? ? ? ? ? ? ? ? ? ? ? ? ? Fab(4) ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? Fab(3) ? ? ? ? ? ? ??
? ? ? ? ? ? ? Fab(3) ? ? + ? ? ?Fab(2) ? ? ? ? + ? ? ? ? ?Fab(2) ? ?+ ? ? ?Fab(1)
? ? ? Fab(2)+Fab(1)+Fab(1)+Fab(0) ?+ ?Fab(1)+Fab(0) ? ??
Fab(1)+Fab(0)

            
              def fab1(n):
?? ?if n < 1:
?? ??? ?print('輸入錯(cuò)誤！')

?? ?if n == 1 or n == 2:
?? ??? ?return 1 ? ? ? ? ? ? ? #如果求的是第一或者第二項(xiàng)，直接結(jié)果為1
?? ?else:
?? ??? ?return fab1(n-1) + fab1(n-2)

a = int(input('請(qǐng)輸入要計(jì)算的斐波那契項(xiàng)數(shù)：'))
result = fab(a)
print('第%d項(xiàng)斐波那契數(shù)為%d' % (a, result))
            
          

經(jīng)過比較，遞歸方法簡單，容易理解，但是會(huì)浪費(fèi)大量的CPU資源，計(jì)算時(shí)間也比非遞歸方法長了相當(dāng)多。非遞歸方法無非就是代碼稍微復(fù)雜一點(diǎn)點(diǎn)，但是計(jì)算時(shí)間卻很短，也幾乎不怎么占用CPU資源。這就是為什么不提倡使用遞歸方法的原因。
?