如何理解漢諾塔的遞歸？

我做了個動畫

三個盤子的漢諾塔你總會吧:

然後你移完發現左邊柱子下面又蹦出來一個盤子

好吧, 那就把中間的柱子看成目標柱

然後把最大的移到右邊, 然後就和搬三個一模一樣了

更多的話也是一樣的...

所以

所以說一共就三步

1. 把 n-1 號盤子移動到緩衝區
2. 把1號從起點移到終點
3. 然後把緩衝區的n-1號盤子也移到終點

所以寫成py代碼就是

def move(n,from,buffer,to):
if n==1:
print("Move",n,"from",from,"to",to)
else:
move(n-1,from,to,buffer)
move(1,from,buffer,to)
move(n-1,buffer,from,to)


1. 要從a到b 那c就是緩衝 move(n-1,from,to,buffer)
2. 要從a到c 那b就是緩衝 move(1,from,buffer,to)
3. 要從b到c 那a就是緩衝 move(n-1,buffer,from,to)

毫無理解難度啊...

C++那不一樣的嗎

using namespace std;
#include &
#include &

void move (int n, char from, char buffer, char to){
if (n == 1) {
cout &<&< "Move" &<&< n &<&< " from " &<&< from &<&< " to " &<&< to &<&< endl; } else { move (n-1, from, to, buffer); move (1, from, buffer, to); move (n-1, buffer, from, to); } } //別打我, 我習慣不換行了, 反正現在有格式化工具...... //main()你自己寫吧

Mathematica的話...我會直接Fold一個迭代器

迭代器會自己去找合適的緩衝區...

這就是 Frame - Stewart 演算法

不過講道理這麼寫挺欠揍的...誰?給我 pull 這種代碼我直接打上去了2333

Get["https://raw.githubusercontent.com/GalAster/Deus/master/Packages/_
_Raw/HanoiTower.wl", CharacterEncoding -&> "UTF8"]
HanoiShow@HanoiMove[10, Pillar -&> 5] // ListAnimate


漢諾塔永遠只有三步：

圖中是最常見的五層(五珠)漢諾塔，

那麼問題來了，怎樣把冰箱門打開？

這又變成了一道m層漢諾塔的問題(m=n-1)。

推導下去最終就得到了一個兩層漢諾塔該怎麼移動的問題，

這個相信你閉著眼也知道該怎麼搞了。

【白雲大媽的冰箱理論其實蘊含了深刻的哲學道理 -_-!!!】

【不想看公式的話，往下翻有實操技巧】

……………公式解釋……………

關於漢諾塔的公式：

可以這樣理解：

其中

代表把冰箱門打開又合上，即完成兩次n-1層漢諾塔的過程，

冰箱門打開或者合上需要的步數都是一樣的，

……………實操技巧……………

實際操作的時候有一個規律：

思考一下：

好吧，這裡其實只是想引出個階段性目標的概念。

比如，

那怎樣把3號串珠移動到C柱上呢？

5是奇數，那麼階段性目標就是比當前目標小2的下一個奇數。

5→3→1，

這樣第一步該怎麼走就確定了。

偶數也是同樣的道理，

6層漢諾塔的推理就是6→4→2。

配圖是臨時找了個頁游截的圖，

只是為了更加直觀。

之前隨手寫的答案，公式確實有問題，

使用LaTeX重新編輯了一下，

多謝評論區的朋友指正。

遞歸當然只能以遞歸的思路理解，把它展開純屬自討苦吃。

遞歸思路，說白了是如下三步：

1、對於問題N，如果N-1已經解決了，那麼N是否很容易解決。

甲：想上天？你先給我找個天一樣高的梯子！

乙：想要天一樣高的梯子？你先給我弄棵天一樣高的樹！

甲：想要天一樣高的樹？你先給我弄把能頂到天的鋸子！

……

舉例來說，如果要把一個N層漢諾塔從A搬到C，那麼：

如果前N-1層可以找別人搞定，咱只管搬第N層，會不會變得非常容易？

你看，這一下就簡單了：這時當它只有兩層就好了，先把前N-1層看作一個整體，把它搬到B；然後把最下面的第N層搬到C；然後再把前N-1層從B搬到C。

類似的，假如接到「搬前N-1層」這個任務的是我們，怎麼搬呢？

簡單，像前東家一樣，把前N-2層外包出去，我們只搬第N-1層——其實和前面討論過的「外包N-1層，只搬第N層」完全一樣嘛。

依此類推，一層層「外包」下去——我不管你們有多傷腦筋，反正只要你們把我外包給你的活幹了，我就能幹了我的活！

注意，這裡千萬別管「接到外包工作的傢伙有多傷腦筋」——丟給他就讓他頭疼去，我們就別再撿回來痛苦自己了。

這一步就是「遞推」。

注意這裡的搬法：搬第N層，就需要把前N-1層搬兩次，另外再把第N層搬一次；搬第N-1層，又需要把前N-2層搬兩次，然後再把N-1層搬一次，依此類推。

很容易知道，一共需要搬2^N-1次。

2、一步步遞推下去，終究會有個「包工頭」，接到「搬第一層」的任務。

第一層怎麼搬？

太簡單了，讓搬哪搬哪。

換句話說，到此，「遞推」就到了極限，簡單粗暴直接做就可以了。

3、既然第一層搬了，那麼第二層當然就可以搬了；第二層搬了，第三層又可以搬了……依次類推，直到第N層。於是問題搞定。

這一步就是「回歸」。

如上三步加起來，就是「遞歸」。

推而廣之，任何問題，不管規模為N時有多複雜，只要把N-1那塊「外包」給別人做之後，我們在這個基礎上可以輕易完成N，那麼它很可能就適合用「遞歸」解決。

那麼，怎麼最終確定它能不能用「遞歸」做呢？

看當N取1或2之類最簡情況時，問題是否可以解決——然後寫程序解決它。

容易看出，「遞歸」其實和「數學歸納法」的思路非常像：證明N=1時成立；證明若N=n-1成立，則N=n時也成立；如上兩步得證，則命題在n&>1時一定成立（n為自然數）。

你看，我們沒必要從1開始逐一驗證每個自然數，只要證明了「基礎條件」、再證明了「遞推條件」，大自然的規律會幫我們搞定一切。

換句話說，只要我們：

1、寫程序告訴電腦「如何分解一個問題」

2、寫程序告訴電腦「當該問題分解到最簡時如何處理」

那麼，「具體如何遞推、如何回歸」這個簡單問題就不要再操心了，電腦自己能搞定。

——寫出問題分解方法、寫出分解到最簡後如何解決，這是我們的任務；把問題搞定，是電腦的任務。這就是遞歸的魅力。

正是由於這種「我提供思路你搞定細節」的特點，「一切皆遞歸」的函數系語言才被稱為「聲明式編程」（而不是必須一步一步指導電腦如何做的「命令式編程」）。

這麼簡單輕鬆的事，非要自己吭哧吭哧一步步做出來——O(2^N)規模啊——難怪你們要陷入困境。

搞清楚遞歸只要搞清兩點：

1. 結束條件
2. 把問題規模縮小

在什麼是遞歸這個問題 李冰答主借用了網路上的一張圖片，非常形象，此處引用一下

出口條件就是圖中的小鯉魚，規模縮小是找個除了規模更小其他都一模一樣的自己

在漢諾塔問題中小鯉魚就是只有一個盤子的時候

但是如何讓自己規模縮小呢？

由於小的盤子不能在大的盤子上，最後一個盤子挪的時候前n-1個盤子必須已經被挪開，因此問題被分為三步，如下（手拙，望包涵）：

經過這樣的分解，一個挪n個盤子的問題被轉化成了：兩次挪n-1個盤子的過程加一個直接move的過程。問題規模由n變為n-1，就可以繼續縮小直到找到小鯉魚——只剩一個盤子的情況。

用JS簡單實現了下，對照注釋和前面的解釋理解一下：

//把n個盤子借住helper從from柱子挪到to柱子上
function hanoi(n,from,to,helper){
//判斷是否找到我們的小鯉魚，找到我就直接返回，沒找到我就把自己規模縮小
if(n==1){
console.log("move a plate from "+ from + " to " + to);
return;
}
hanoi(n-1,from,helper,to);//把n-1個從from挪到helper上，藉助to
move(from,to);//把第n個盤子直接從from挪到to
hanoi(n-1,helper,to,from);//把n-1個從helper挪到from上，藉助to
}
//把一個盤子從一個柱子挪到另一個柱子上
function move(from,to)
{
console.log("move a plate from "+ from + " to " + to);
}


最後划下重點：對於遞歸問題，要抓住兩點：結束條件和如何讓問題規模縮小問題。遞歸問題的正確性是根據數學歸納法來證明的，只要找到這兩點也就可以使用數學歸納法了。

特別注意分析問題的時候不要讓自己按著程序運行的順序鑽進去，這樣會很容易困惑和亂掉，盯准關鍵兩點，問題自然迎刃而解。

遞歸就是數學歸納法。

翻一翻以前用數學歸納法求解數列的題，想想數學歸納法的幾個步驟，在回過頭看看漢諾塔、斐波那契數列的函數代碼。

是不是以一毛一樣？

首先，你有n個盤子，你想要把它們順時針移動，那麼你要做的是什麼呢？？

所以漢諾塔的每一步，其實都能分為三個小的步驟，包括對前面n-1個盤子的遞歸處理，對第n個盤子的處理，和對前面n-1個盤子的再次遞歸處理。

以下是我的理解，有不正確的地方或錯別字歡迎指出/討論。

首先初始化這個問題：

1. 對於1個環，直接A→C即可

2. 對於2個環，A→B，A→C，B→C三步即可

整個問題，整體上抽象成這兩步。

1. 將底盤n以上的環（n-1個）移動到B

2. 將底盤n從A移動到C

3. 將B上的環（n-1個）移動到C

其中第1步和第3步的步數是一樣的，因為環的數量一樣（n-1個），只是目標的柱子不同而已。

def hanoi(n,a,b,c):
if n==1: # 1個環的情況，也是遞歸的出口
print(a,"-&>",c)
else: # n &> 1時，用抽象出的3步來移動
hanoi(n-1,a,c,b) # 將n-1個環從a移動到b上
print(a,"-&>",c) # 將底盤從a移動到c上
hanoi(n-1,b,a,c) # 將b上的n-1個環移動到c上


這個問題最近挺困擾我，網上看了很多文章都在說用函數的角度去理解整個過程，確實是沒錯而且是一種聰明的辦法，但是有強迫症的我還是花了些時間去思考了一下遞歸每一步的運行，說一下個人的理解吧。 如有不正確以及不完善的，還請前輩指正。

首先貼上漢諾塔程序java代碼

分割線------------------

推薦看一下 3Blue1Brown 關於漢諾塔的視頻，相信大家會受益匪淺。

如果你有耐心翻到這裡看到這個回答，相信大部分前面的回答並沒有讓你完全明白漢諾塔的遞歸演算法應該怎麼理解，那麼我希望這個答案會是你瀏覽的最後一個。ps：篇幅稍微有點長，請耐心閱讀，相信我，會有價值的。（畢竟是個人理解，若其中有不正確的地方望大家多多指正哈）

要用程序來解決這個問題，我們先定義一個移動函數：move（移動數，開始柱，中轉柱，目標柱），例如 move（2，A，B，C） 表示將2個盤子從A柱（開始柱）藉助B柱（中轉柱）移動到C柱（目標柱）。

關於開始柱，中轉柱，目標柱這三個概念可以用移動過程中的某個狀態來理解，看下面一張圖應該就能明白：

以上圖的三層漢諾塔為例，開始柱指的是開始狀態時存放所有盤子的柱子，中轉柱指的是中間狀態時暫時存放n-1個（三層就是3-1個）盤子的柱子，目標柱指的是盤子最終要移動到的柱子。這裡需要注意，開始柱，中轉柱，目標柱並不是一成不變的，而是會根據層次的不同而改變。（如果這裡暫時不能理解的話，先讀下去，再回頭你就能明白了）。

接著我們分情況討論一下盤子的移動：

情況一：當盤子只有1個（調用 move（1，A，B，C））

當盤子只有一個的時候，只要直接將盤子從開始柱移動到目標柱就可以了，並沒有中間狀態（即不用藉助中轉柱），在move方法中可以用一句話表示該移動動作 print（"A---&>C"）;

情況二：當盤子有2個（調用 move（2，A，B，C））

這個情況分三個步驟進行：

step1. 把除了最大的盤子之外的盤子從A移到B

A---&>B (開始柱---&>中轉柱) 【相當於調用 move（1，A，C，B）】

step2. 把最大的盤子從A移到C

A---&>C (開始柱---&>目標柱) 【相當於調用 move（1，A，B，C）】

step3. 把除了最大的盤子之外的盤子從B移到C

B---&>C (中轉柱---&>目標柱) 【相當於調用 move（1，B，A，C）】

我想對於以上兩個情況大家應該是沒有什麼疑問的，是可以確定的。然後我們來看三層的情況:

情況三：當盤子有3個（調用 move（3，A，B，C））

這個情況同樣分三步進行：

step1. 把除了最大的盤子之外的盤子從A移到B（注意對於這個步驟來說此時A為開始柱，C為中轉柱，B為目標柱，這樣才能完成把最上面的2個盤子從A---&>B的任務）

A---&>C (開始柱---&>中轉柱) 【相當於調用 move（1，A，B，C）】

A---&>B (開始柱---&>目標柱) 【相當於調用 move（1，A，C，B）】

C---&>B (中轉柱---&>目標柱) 【相當於調用 move（1，C，A，B）】

step2. 把最大的盤子從A移到C（對於這個步驟來說此時A為開始柱，B為中轉柱，C為目標柱，這樣才能把最大的盤子從A---&>C）

A---&>C (開始柱---&>目標柱) 【相當於調用 move（1，A，B，C），即直接執行 print（"A---&>C"）】

step3. 把除了最大的盤子之外的盤子從B移到C（注意對於這個步驟來說此時B為開始柱，A為中轉柱，C為目標柱，這樣才能完成把處於step2中的中轉柱的2個盤子從B---&>C的任務）

B ---&> A (開始柱---&>中轉柱) 【相當於調用 move（1，B，C，A）】

B ---&> C (開始柱---&>目標柱) 【相當於調用 move（1，B，A，C）】

A ---&> C (中轉柱---&>目標柱) 【相當於調用 move（1，A，B，C）】

情況三的描述可能一下子不是那麼好理解，但是大家應該能發現情況三的step1和step3的形式和整整個情況二的形式很像吧？而且要注意到分析的層次不相同時，開始柱，中轉柱，目標柱是不一樣的。對於step1來說中轉柱是C，對於step3來說中轉柱是A，對於整個情況三來說中轉柱是B。

前面我們已經確定了情況二調用的函數是 move（2，A，B，C），其等價於

A---&>B

A---&>C

B---&>C

這三步，然後情況三的step1是

A---&>C

A---&>B

C---&>B

這三步，跟情況二的形式是一樣的，根據前面情況二的轉化，那這三步就可以轉化成函數 move（2，A，C，B)

情況三的step3同理，做轉化就成了函數 move（2，B，A，C）

而情況三的step2可以直接用一句 print（"A---&>C"） 來代替 move（1，A，B，C）

所以整個情況三就可以這樣來表示：

move（2，A，C，B) //step1. 把除了最大的盤子之外的盤子從A移到B

print（"A---&>C"） //step2. 把最大的盤子從A移到C

move（2，B，A，C） //step3. 把除了最大的盤子之外的盤子從B移到C

我們又知道情況三調用的函數是 move（3，A，B，C），所以以上三行代碼其實就等價於函數 move（3，A，B，C）。

來到這裡應該就可以發現一點端倪了，情況四（4層）調用的函數是 move（4，A，B，C），其用偽代碼表示就是

move（3，A，C，B) //step1. 把除了最大的盤子之外的盤子從A移到B

print（"A---&>C"） //step2. 把最大的盤子從A移到C

move（3，B，A，C） //step3. 把除了最大的盤子之外的盤子從B移到C

對此有懷疑的小夥伴可以自己寫出情況四的每步具體步驟然後再做轉化，限於篇幅這裡不再列出。

那其實可以總結出：對於n（n&>1）層漢諾塔，調用函數 move（n，A，B，C）來遞歸解決該問題，該函數執行的是

move（n-1，A，C，B) //step1. 把除了最大的盤子之外的盤子從A移到B

print（"A---&>C"） //step2. 把最大的盤子從A移到C

move（n-1，B，A，C） //step3. 把除了最大的盤子之外的盤子從B移到C

然後有了以上的理解之後，我們就可以嘗試寫出解決該問題的代碼了，Python實現：

def move(n,A,B,C):
if n==1: # 1個盤子，直接列印出移動動作
print(A,"---&>",C)
else: # n &> 1時，用抽象出的3步來移動
move（n-1，A，C，B) #step1. 把除了最大的盤子之外的盤子從A移到B
print(A,"---&>",C) #step2. 把最大的盤子從A移到C
move（n-1，B，A，C）#step3. 把除了最大的盤子之外的盤子從B移到C


so，讀到這裡，我大膽猜測大部分人心裡應該明白得七七八八了，如果說我猜錯了，別急，我們還可以從函數的角度來理解這個問題。

或許有一部分人知道這個函數如何編寫，也似懂非懂的了解這個函數注釋的意義，但是可能會糾結為什麼函數寫成這樣子就能詳細地列出具體的移動步驟（我就是這部分人啊，研究這個問題沒少鑽牛角尖），下面就跟大家分享下我的另外一個見解。

well，假設現在我們要移動一個4層的漢諾塔，從A---&>C：

那麼我們必須先將上面3個盤子移動到B，然後再將最大的盤子從A移動到C，接著將在B上的三個盤子從B移動到A才能達到目的。這個過程的關鍵在於第一步，怎麼把上面的3個盤子從A移動到B？

OK，前面說要移動4個就必須先移動上面3個，所以這裡我們要移動3個就必須移動上面2個，但是並不是移動到B哦，因為B已經被我們預定好了要用於存放前面移動的3個盤子，如果是將上面2個盤子移動到B，那根據遊戲規則第三個盤子就沒辦法放進去B了，這樣子就沒辦法完成B存放3個盤子的預定目標，所以要移動的上面兩個是計劃放在C上。

那問題接著就到了該怎麼移動上面2個盤子，這時你可能會想要先移走最上面的盤子（這時候要移到B，因為C被我們預定了要存放2個盤子，且B這時候是沒有盤子的），沒錯，那最上面的盤子怎麼移？直接移唄怎麼移，最上面的盤子都沒限制的。所以要移動1個盤子的時候，直接移動： A---&>B，注意，這個步驟中A為開始柱，B為目標柱。

這時你已經移開最上面的盤子了，就可以把第二盤子移走了，A---&>C，然後把最小的盤子放到第二個盤子上，B---&>C，這樣就完成了移動2個盤子的任務了。

總結下移動兩個盤子的步驟：

A---&>B

A---&>C

B---&>C

這三個步驟就是move（2，A，B，C）所做的事情，是可以詳細列出每步移動的動作的。

既然最上面的2個盤子都調用move（2，A，B，C）移開了，那麼第3個盤子自然也可以從A---&>B了，之後再把放在C上面的2個盤子從C移動到B上就完成了移動上面3個盤子的任務了。前面的move（2，A，B，C）函數既然可以將2個盤子從A藉助B移動到C並列出詳細的移動動作，那麼move（2，C，A，B）也就能將放在C上的2個盤子從C藉助A移動到B並列出詳細的移動動作，如此說來，移動3個盤子的步驟就可以總結如下了：

move（2，A，B，C）

A---&>B

move（2，C，A，B）

這三個步驟就是move（3，A，C，B）所做的事情，因為我們已經證明move（2，A，B，C）和move（2，C，A，B）是可以詳細列出移動2個盤子時每步移動的動作的，而中間的A---&>B是一步顯而易見的移動動作，所以可以確定move（3，A，C，B）是能列出每步的移動動作的。

然後根據同樣的分析，最上面的3個盤子都移開了，接著只要將第4個盤子從A---&>C，然後將放在B上的3個盤子移動到C上就完成全部任務了。前面我們已經證明move（3，A，C，B）能將3個盤子從A藉助B移動到C並且列出詳細的移動動作，那麼move（3，B，A，C）也能將3個盤子從B藉助A移動到C並列出每步的移動動作，這樣，移動4個盤子的步驟就出來了：

move（3，A，C，B）

A---&>C

move（3，B，A，C）

這三個步驟就是最開始move（4，A，B，C）函數所做的事情，因為我們已經證明move（3，A，C，B）和move（3，B，A，C）是可以詳細列出移動3個盤子時每步移動的動作的，而中間的A---&>C是一步顯而易見的移動動作，所以可以確定move（4，A，B，C）是能列出每步的移動動作的。

需要說明的是，從xx藉助xx移動到xx這樣的說法在上面出現了很多次，「從」後面代表的就是開始柱，「藉助」後面代表的是中轉柱，「移動到」後面代表的是目標柱。你也能注意到到 開始柱，中轉柱，目標柱 在不同層級下是不一樣的。

根據以上的分析，希望大家就能明白move(n,A,B,C)遞歸函數的意義了（忘記函數具體內容的往前翻哦）可能有些啰嗦，但是已經儘力表達了我想表達的東西，希望能幫上大家一點忙吧，溜了~

----------------------------------- 我是分割線么？------------------------

ps： 大家都默默收藏了答案，不如再順手點個贊讓更多人看到？hiahiahia~

代碼如下：

首先，題主你需要先理解n=2的情況，非常簡單：

1. 執行move(1,a,c,b)，列印出A--&>B；

2. 執行A--&>C；

3. 執行move(1,b,a,c)，列印出B--&>C；

因此n=2時，相當於是將A中的兩個盤子按照規則搬到了C中。

1. 執行move(2,a,c,b)，帶入我們之前所理解的結果，即將A中的上面2個盤子按照規則搬到了B中，並且列印出過程；

2. 將A中最下面的盤子搬到c中，列印A--&>C；

3. 執行move(2,b,a,c)，即將B中的2個盤子按規則搬到C中，並且列印出過程。

用我們當年OI競賽敎練的話來說：你就是個將軍！（雖然這句話原本是在講動態規劃的時候說的，不過用在這裡也毫不違和）

你就是個將軍，你的任務就是要把n個漢諾塔從第一個搬到第三個柱子去。

那麼你祇需要喊一個手下，讓他先幫你把n-1個塔從一號柱搬到二號柱，然後你把一號柱最底下的塔搬到三號柱上，再讓這個手下幫你把二號柱上剩餘的塔搬到三號柱，這樣你的任務就完成了。

至於你的手下怎麼做，那是他的事情，你無需操心。他可能一次性也搬不完，那麼他再去找手下來做，方法跟你一樣。

package number;
import java.util.Scanner;
public class Hannuota {
int n;
char start;
char middle;
char end;
public void hanoi(int n,char start,char middle,char end){
this.n=n;
this.start=start;
this.middle=middle;
this.end=end;
if(n==1){
move(start,end);
}else{
hanoi(n-1,start,end,middle);
//將在A(start)柱子上的前n-1個盤子移動到B(end)柱子上
move(start,end);
//將在A(start)柱子上的最大的n盤移動到C(end)柱子上
hanoi(n-1,middle,start,end);
//將在B(start)柱子上的前n-1個盤子移動到C(end)柱子上
}
}
public void move(char start,char end){
System.out.println(start+"-&>"+end);
}
public static void main(String args[]){
int n;
Scanner scan=new Scanner(System.in);
System.out.println("how many Hanoi plate do you have:");
n=scan.nextInt();
Hannuota han=new Hannuota();
han.hanoi(n, "A", "B", "C");
}
}


輸出的計算結果：

how many Hanoi plate do you have:
3
A-&>C
A-&>B
C-&>B
A-&>C
B-&>A
B-&>C
A-&>C


這個程序本身並不複雜，但理解起來卻不容易。我的程序是這樣

我想了很久這個程序運行的過程。終於有點眉頭。當盤子為3時，程序的運營順序是