---

????????大一學(xué)C的時(shí)候已經(jīng)接觸到漢諾塔遞歸的問題，當(dāng)時(shí)只是簡單了解過方法，最近開了算法課，打算重新捋一捋。

題目描述：
????????有三根柱子分別為A、B、C，柱子A上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤，要把所有盤子一個(gè)一個(gè)移動(dòng)到柱子C上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤子在小盤子上方，求解此過程。

（圖片來源：http://www.hannuota.cn/）

????????剛拿到題目，我假設(shè)n為1，即拿起來放過去即可；假設(shè)n為2，先把上面的小盤子拿起放到B，再把下面的大盤子拿起放到C，最后把小盤子拿起放到C；假設(shè)n為3…

????????當(dāng)n到5、6的時(shí)候，解答就變得困難了。我嘗試開始從前面的情況中尋找規(guī)律，但好像并不可觀…

???????????????漢諾塔小游戲: Tower of Hanoi.
（動(dòng)手能力強(qiáng)的朋友可以去上面這個(gè)網(wǎng)站玩一下模擬的小游戲）

網(wǎng)上檢索后發(fā)現(xiàn)遞歸是解這個(gè)題目的方法，接著我換了個(gè)思路…

????????從大的角度想，要把n個(gè)盤子移動(dòng)到目標(biāo)柱子，是不是要先解決把n-1個(gè)盤子移動(dòng)過去的問題呢？…按這路子一直套娃，解決掉最小子問題即1個(gè)盤子的時(shí)候，問題似乎好像就可以化繁為簡…
???????????????????????????

按這種思路，很容易就能想到設(shè)計(jì)這個(gè)遞歸算法的邏輯關(guān)鍵：

（A用From代替表示起點(diǎn)柱子，B用Helper代替表示輔助柱子，C用To代替表示目標(biāo)柱子）

問題規(guī)模為n時(shí)*

1、From頂部的n-1個(gè)盤子移動(dòng)到Helper

2、From最底部的大大大盤子移動(dòng)到To

3、Helper上面的n-1個(gè)盤子移動(dòng)到To

問題規(guī)模為n-1時(shí)

1、From頂部的（n-1）-1 個(gè)盤子移動(dòng)到Helper

2、From底部的大大盤子移動(dòng)到To

3、Helper上面的（n-1）-1 個(gè)盤子移動(dòng)到To
…

問題規(guī)模為2時(shí)

1、From頂部的 1 個(gè)盤子移動(dòng)到Helper

2、From底部的大盤子移動(dòng)到To

3、Helper上面的 1 個(gè)盤子移動(dòng)到To

來人！上圖（手動(dòng)起草）

????????這是遞歸算法的第一個(gè)空間棧中計(jì)算機(jī)所需要做的事情，但并不是三步即可搞定，它會(huì)從這個(gè)空間中直線引申出許多另外的空間，來解決當(dāng)前空間的子問題，再一步步回代，當(dāng)?shù)谝粋€(gè)空間中的事情解決了，問題也就解決了。

遞歸邏輯出來，可以根據(jù)其進(jìn)行碼代（分別對(duì)應(yīng)上圖3個(gè)步驟）：

//對(duì)應(yīng)圖中第一步：把n-1個(gè)盤子移動(dòng)到HelperHanoi(n-1, From, Helper, To);//對(duì)應(yīng)圖中第二步：把最底下的盤子移動(dòng)到ToMove(n, From, To);//對(duì)應(yīng)圖中第三步：把n-1個(gè)盤子移動(dòng)到ToHanoi(n-1, Helper, To, From);

然后是遞歸出口的問題（即n-1為1的時(shí)候）

//出口if (n==1) {Move(n,From,To);return;}

（跑一跑代碼，蕪湖，迎刃而解~）

完整的代碼：
（Move方法：打印解的步驟）

import java.util.*;public class Solution {public static void Hanoi(int n,String From,String To ,String Helper) {//出口if (n==1) {Move(n,From,To);return;}//對(duì)應(yīng)圖中第一步：把n-1個(gè)盤子移動(dòng)到HelperHanoi(n-1, From, Helper, To);//對(duì)應(yīng)圖中第二步：把最底下的盤子移動(dòng)到ToMove(n, From, To);//對(duì)應(yīng)圖中第三步：把n-1個(gè)盤子移動(dòng)到ToHanoi(n-1, Helper, To, From);}public static void Move(int n,String From,String To) {//打印解的步驟System.out.println("移動(dòng)" + n + "號(hào)盤子從" + From + "到" + To);}public static void main(String[] args) {//借助Helper，把5個(gè)盤子從From移動(dòng)到ToHanoi(5, "From", "To", "Helper");} }

想起我的數(shù)據(jù)結(jié)構(gòu)李師之前說的一番話：
????????遞歸代碼少，思路對(duì)了設(shè)計(jì)起來也是比較簡單，但真正一步步去細(xì)想和演算，是非常困難的一件事情，所以把這件事交給計(jì)算機(jī)，我們做不到的它可以幫我們做到…

（完）

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的经典汉诺塔（Java初学递归篇）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。