斐波那契數列：
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資源。這就是為什么不提倡使用遞歸方法的原因。
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
