借漢諾塔理解棧與遞歸

我們先說，在一個函數中，調用另一個函數。

首先，要意識到，函數中的代碼和平常所寫代碼一樣，也都是要執行完的，只有執行完代碼，或者遇到return，才會停止。

那么，我們在函數中調用函數，執行完了，就會重新回到本函數中，繼續向下執行，直到結束。

在執行其它函數時，本函數相當于中斷了，不執行了。那我們重新回來的時候，要從剛才暫停的地方開始，繼續執行，這期間，所有現場信息都要原封不動，就相當于時間暫停了一樣，什么都不能改變，這樣才能做到程序的準確。

所以，通常，在執行另一個函數之前，電腦會將現場信息壓入一個系統棧，為被調用的函數分配存儲區，然后開始執行被調函數。執行完畢后，保存計算結果，釋放被調函數的空間，按照被調函數里保存的返回地址，返回到原函數。

那什么是遞歸函數呢？

就是多個函數嵌套調用。不同的是，這些函數是同一個函數，只是參數可能不同，甚至參數也一樣，只是存儲空間不同。

每一層遞歸所需信息構成一個棧，每一塊內存儲著所有實在參數，所有局部變量，上一層的返回地址，等等一切現場信息。每執行完就彈出。

遞歸函數有著廣泛應用，主要適合可以把自身分化成一樣的子問題的問題。比如漢諾塔。

漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

思路：函數（n,a,b,c)含義是把n個盤子從a柱子搬到c柱子的方法

一個盤子，直接搬過去。

多個盤子，我們把n-1個盤子都移動到另一個柱子上，把最大的搬過去然后把剩下的搬過去。

def hanoi(n, a, b, c):

if n == 1:

print(a, '-->', c)

else:

hanoi(n - 1, a, c, b)

print(a, '-->', c)

hanoi(n - 1, b, a, c)

# 調用

hanoi(3, 'A', 'B', 'C')

結果：

A --> C

A --> B

C --> B

A --> C

B --> A

B --> C

A --> C

我們的棧：

第一次：

我們把hanoi(3, 'A', 'B', 'C')存了起來，調用了hanoi(3-1, 'A', 'C', 'B'),現在棧里壓入了3, 'A', 'B', 'C'，還有函數執行到的位置等現場信息。然后執行hanoi(3-1, 'A', 'C', 'B')，發現要調用hanoi(3-1-1, 'A', 'B', 'C')，我們又把3-1, 'A', 'C', 'B'等信息壓入了棧，現在棧是這樣的：

棧頭

2, 'A', 'C', 'B'

3, 'A', 'B', 'C'

棧尾

然后執行hanoi(3-1-1, 'A', 'B', 'C')，發現n=1了，打印了第一條A --> C，然后釋放掉了hanoi(3-1-1, 'A', 'B', 'C')的空間，并通過記錄的返址回到了hanoi(3-1, 'A', 'C', 'B')，然后執行打印語句A --> B，然后發現要調用hanoi(3-1-1, 'C', 'A', 'B')，此時棧又成了：

2, 'A', 'C', 'B'

3, 'A', 'B', 'C'

調用hanoi(1, 'A', 'C', 'B')發現可以直接打印，C --> B。

然后我們又回到了2, 'A', 'C', 'B'這里。發現整個函數執行完了，那就彈出吧。這時棧是這樣的：

3, 'A', 'B', 'C'

只有這一個。

我們繼續執行這個函數的代碼，發現

def hanoi(n, a, b, c):

if n == 1:

print(a, '-->', c)

else:

hanoi(n - 1, a, c, b)//執行到了這里

print(a, '-->', c)

hanoi(n - 1, b, a, c)

那我們就繼續執行，發現要打印A --> C

然后繼續，發現要調用? ? ? ? hanoi(n - 1, b, a, c)，那我們繼續把現場信息壓棧，繼續執行就好了。

遞歸就是把大問題分解成小問題進而求解。

具體執行就是通過系統的棧來實現返回原函數的功能。

多色漢諾塔問題：

奇數號圓盤著藍色，偶數號圓盤著紅色，如圖所示。現要求將塔座A 上的這一疊圓盤移到塔座B 上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規則：

規則(1)：每次只能移動1 個圓盤；

規則(2)：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；

規則(3)：任何時刻都不允許將同色圓盤疊在一起；

其實雙色的漢諾塔就是和無色的漢諾塔算法類似，通過推理可知，無色漢諾塔的移動規則在雙色漢諾塔這里的移動規則并沒有違反。

這里說明第一種就可以了：Hanoi（n-1，A,C,B）;

在移動過程中，塔座上的最低圓盤的編號與n-1具有相同奇偶性，塔座b上的最低圓盤的編號與n-1具有不相同的奇偶性，從而塔座上的最低圓盤的編號與n具有相同的奇偶性，塔座上c最低圓盤的編號與n具有不同的奇偶性；

所以把打印操作換成兩個打印即可

總：因為遞歸可能會有重復子問題的出現。

就算寫的很好，無重復子問題，也會因為來回調用、返回函數，而速度較慢。所以，有能力的可以改為迭代或動態規劃等方法。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。