遞歸的原則
- 遞歸算法必須具有基本情況台囱。
- 遞歸算法必須改變其狀態(tài)并向基本情況靠近氏淑。
- 遞歸算法必須以遞歸方式調(diào)用自身
漢諾塔問題
法國數(shù)學(xué)家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候骇径，在其中一根針上從下到上地穿好了由大到小的64片金片躯肌，這就是所謂的漢諾塔。不論白天黑夜破衔，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片清女，不管在哪根針上，小片必須在大片上面晰筛。僧侶們預(yù)言嫡丙，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅传惠，而梵塔迄沫、廟宇和眾生也都將同歸于盡。（來源：互動百科）
該問題可以簡化出以下要點：
- 64片金片卦方，從一根針移動到另一根針上羊瘩，可以借助第三根針
- 大片永遠(yuǎn)不能放在小片的上面
漢諾塔問題的經(jīng)典解法
假設(shè)金片都在寶石針A上，我們需要把這些金片借助寶石針B盼砍，移動到C上尘吗。總共有n片需要移動浇坐。
- 將較小的n-1片睬捶，從A，借助C近刘，移動到B上擒贸。
- 將最大的第n片，從A觉渴，直接移動到C上介劫。
- 將較小的n-1片，從B案淋，借助A座韵，移動到C上
這一思路的核心假設(shè)是在我們處理n片的時候，已經(jīng)具備了處理n-1片的的能力踢京。這就是遞歸的思想誉碴。當(dāng)問題簡化至移動1片時，我們就可以直接解決了瓣距。
#將num片金片黔帕，從from_needle,借助by_needle,向to_needle移動
def moveTower(num, from_needle, to_needle, by_needle):
if 1 == num :
print('Move Plate %d from %s to %s'%(num, from_needle, to_needle)) #只剩一個時，可不經(jīng)過借助針蹈丸，直接移動
else:
moveTower(num-1, from_needle, by_needle, to_needle)
print('Move Plate %d from %s to %s'%(num, from_needle, to_needle)) # 打印出每次單片的移動
#所有的移動最終都可以追溯至單片的移動蹬屹，因而侣背，但打印出所有單片的移動就是打印出了所有的移動
moveTower(num-1, by_needle, to_needle, from_needle )
def main():
num = 3
moveTower(num, 'A', 'C', 'B') # 從A借助B移動到C
if __name__ == "__main__":
main()
當(dāng)需要移動3片時，實驗結(jié)果如下:
Move Plate 1 from A to C
Move Plate 2 from A to B
Move Plate 1 from C to B
Move Plate 3 from A to C
Move Plate 1 from B to A
Move Plate 2 from B to C
Move Plate 1 from A to C
可以用手動方法驗證慨默，結(jié)果是正確的贩耐。
當(dāng)移動10片時，運行結(jié)果如下：
Move Plate 1 from A to B
Move Plate 2 from A to C
Move Plate 1 from B to C
Move Plate 3 from A to B
Move Plate 1 from C to A
Move Plate 2 from C to B
Move Plate 1 from A to B
Move Plate 4 from A to C
Move Plate 1 from B to C
Move Plate 2 from B to A
Move Plate 1 from C to A
Move Plate 3 from B to C
Move Plate 1 from A to B
Move Plate 2 from A to C
Move Plate 1 from B to C
Move Plate 5 from A to B
... ...
Move Plate 4 from A to C
Move Plate 1 from B to C
Move Plate 2 from B to A
Move Plate 1 from C to A
Move Plate 3 from B to C
Move Plate 1 from A to B
Move Plate 2 from A to C
Move Plate 1 from B to C
總共進行了1023步移動厦取。
