Python基于遞歸算法實現(xiàn)的漢諾塔與Fibonacci數(shù)列示例

更新時間：2018年04月18日 14:20:57 作者：快遞小可

這篇文章主要介紹了Python基于遞歸算法實現(xiàn)的漢諾塔與Fibonacci數(shù)列,結(jié)合實例形式分析了漢諾塔與Fibonacci數(shù)列的遞歸實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了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

運行結(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)

運行結(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)

運行結(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è)計有所幫助。

您可能感興趣的文章: