Python基于遞歸算法實現(xiàn)的漢諾塔與Fibonacci數(shù)列示例
本文實例講述了Python基于遞歸算法實現(xiàn)的漢諾塔與Fibonacci數(shù)列。分享給大家供大家參考，具體如下：
這里我們通過2個例子，學(xué)習(xí)python中遞歸的使用。
1. 找出Fibonacci數(shù)列中，下標(biāo)為 n 的數(shù)（下標(biāo)從0計數(shù)）
Fibonacci數(shù)列的形式是這樣的：0,1,1,2,3,5,8,13……
① 使用while循環(huán)，python2代碼如下：
def fib(n):
a,b=0,1
count=0
while count<n:
a,b=b,a+b
count=count+1
print a
運(yùn)行結(jié)果如下：
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
② 使用遞歸（遞歸必須要有邊界條件），python2代碼如下：
def fib(n):
if n==0 or n==1:#遞歸的邊界條件
return n
else:
return fib(n-1)+fib(n-2)
運(yùn)行結(jié)果如下：
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
遞歸是最能表現(xiàn)計算思維的算法之一，我們以f(4)為例，看一下遞歸的執(zhí)行過程：
同一程序，使用遞歸雖然程序簡潔，但遞歸的執(zhí)行效率要比循環(huán)低，系統(tǒng)的資源消耗比循環(huán)大。因為遞歸是一層一層地往里面調(diào)用，結(jié)束后又一層一層地返回，所以遞歸的執(zhí)行效率并不高。那為什么還要使用遞歸呢？因為有一些問題，我們找不到非常明顯的循環(huán)方案，但容易找到明顯的遞歸方案。比如說著名的漢諾塔問題。
2. 漢諾塔
下圖是一個簡化版的漢諾塔游戲，只有4個盤子：
漢諾塔游戲規(guī)則如下：
python2代碼如下：
def hanoi(a,b,c,n):
if n==1:#遞歸結(jié)束條件
print a,'->',c
else:
hanoi(a,c,b,n-1)
print a,'->',c
hanoi(b,a,c,n-1)
運(yùn)行結(jié)果：
>>> hanoi('A','B','C',1)
A -> C
>>> hanoi('A','B','C',2)
A -> B
A -> C
B -> C
>>> hanoi('A','B','C',3)
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
在寫博客的過程中經(jīng)常要插入圖片，本文將使用Python實現(xiàn)對上傳的圖片自動壓縮，自動編碼，以及自動推送到遠(yuǎn)程倉庫，感興趣的可以了解一下2021-10-10
Python中optionParser模塊的使用方法實例教程
這篇文章主要介紹了Python中optionParser模塊的使用方法,功能非常強(qiáng)大,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了基于KL散度、JS散度以及交叉熵的對比，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-05-05
解讀FastAPI異步化為transformers模型打造高性能接口
這篇文章主要介紹了解讀FastAPI異步化為transformers模型打造高性能接口問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
這篇文章主要介紹了python編寫微信公眾號首圖的思路，根據(jù)微信公眾號首圖要求，可以上傳一個不超過5M的圖片，且圖片尺寸要是2.35：1的尺寸，具體實現(xiàn)思路及代碼感興趣的朋友跟隨小編一起看看吧2019-12-12
這篇文章主要介紹了python中的元組與列表及元組的更改，元組是由一對方括號構(gòu)成的序列。列表創(chuàng)建后，可以根據(jù)自己的需要改變他的內(nèi)容，下面更多詳細(xì)內(nèi)容，需要的小伙伴可以參考一下2022-03-03
Python聊天室?guī)Ы缑鎸崿F(xiàn)的示例代碼(tkinter,Mysql,Treading,socket)
這篇文章主要介紹了Python聊天室?guī)Ы缑鎸崿F(xiàn)的示例代碼(tkinter,Mysql,Treading,socket),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
python矩陣的轉(zhuǎn)置和逆轉(zhuǎn)實例
今天小編就為大家分享一篇python矩陣的轉(zhuǎn)置和逆轉(zhuǎn)實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-12-12
Python如何獲取當(dāng)前路徑并列出當(dāng)前路徑下的所有文件
這篇文章主要介紹了Python如何獲取當(dāng)前路徑并列出當(dāng)前路徑下的所有文件問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
這篇文章主要介紹了python 迭代器與生成器的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-08-08