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

1.用迭代實現斐波那契數列(非遞歸方法)

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

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

?? ?return n3 ? ? ? ? ? ?

a = int(input('請輸入要計算的斐波那契項數：'))
result = fab(a)
print('第%d項斐波那契數為%d' % (a, result))
            
          

2.遞歸方法
? 原理：（樹形結構圖）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 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('輸入錯誤！')

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

a = int(input('請輸入要計算的斐波那契項數：'))
result = fab(a)
print('第%d項斐波那契數為%d' % (a, result))
            
          

經過比較，遞歸方法簡單，容易理解，但是會浪費大量的CPU資源，計算時間也比非遞歸方法長了相當多。非遞歸方法無非就是代碼稍微復雜一點點，但是計算時間卻很短，也幾乎不怎么占用CPU資源。這就是為什么不提倡使用遞歸方法的原因。
?