本文實例講述了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è)計有所幫助。