原文鏈接（轉(zhuǎn)載請(qǐng)注明出處）漢諾塔的圖解遞歸算法
起源
漢諾塔（又稱河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具俱萍。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子熄求，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤缩搅。大梵天命令婆羅門把圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上钝荡。并且規(guī)定，在小圓盤上不能放大圓盤犯助，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤栗竖。
抽象為數(shù)學(xué)問(wèn)題
如下圖所示暑脆，從左到右有A、B狐肢、C三根柱子添吗，其中A柱子上面有從小疊到大的n個(gè)圓盤，現(xiàn)要求將A柱子上的圓盤移到C柱子上去处坪，期間只有一個(gè)原則：一次只能移到一個(gè)盤子且大盤子不能在小盤子上面根资，求移動(dòng)的步驟和移動(dòng)的次數(shù)
解：
(1) n == 1
第1次 1號(hào)盤 A---->C sum = 1 次
(2) n == 2
第1次 1號(hào)盤 A---->B
第2次 2號(hào)盤 A---->C
第3次 1號(hào)盤 B---->C sum = 3 次
（3）n == 3
第1次 1號(hào)盤 A---->C
第2次 2號(hào)盤 A---->B
第3次 1號(hào)盤 C---->B
第4次 3號(hào)盤 A---->C
第5次 1號(hào)盤 B---->A
第6次 2號(hào)盤 B---->C
第7次 1號(hào)盤 A---->C sum = 7 次
不難發(fā)現(xiàn)規(guī)律：
1個(gè)圓盤的次數(shù) 2的1次方減1
2個(gè)圓盤的次數(shù) 2的2次方減1
3個(gè)圓盤的次數(shù) 2的3次方減1
。 同窘。 。 部脚。 想邦。
n個(gè)圓盤的次數(shù) 2的n次方減1
故：移動(dòng)次數(shù)為：2^n - 1
調(diào)用方法的棧機(jī)制（特點(diǎn)：先進(jìn)后出）
從主線程開(kāi)始調(diào)用方法（函數(shù)）進(jìn)行不停的壓棧和出棧操作，函數(shù)的調(diào)用就是將函數(shù)壓如棧中委刘，函數(shù)的結(jié)束就是函數(shù)出棧的過(guò)程丧没，這樣就保證了方法調(diào)用的順序流，即當(dāng)函數(shù)出現(xiàn)多層嵌套時(shí)锡移，需要從外到內(nèi)一層層把函數(shù)壓入棧中呕童，最后棧頂?shù)暮瘮?shù)先執(zhí)行結(jié)束（最內(nèi)層的函數(shù)先執(zhí)行結(jié)束）后出棧，再倒數(shù)第二層的函數(shù)執(zhí)行結(jié)束出棧淆珊，到最后夺饲，第一個(gè)進(jìn)棧的函數(shù)調(diào)用結(jié)束后從棧中彈出回到主線程，并且結(jié)束施符。
算法分析（遞歸算法）
我們?cè)诶糜?jì)算機(jī)求漢諾塔問(wèn)題時(shí)往声，必不可少的一步是對(duì)整個(gè)實(shí)現(xiàn)求解進(jìn)行算法分析。到目前為止戳吝，求解漢諾塔問(wèn)題最簡(jiǎn)單的算法還是同過(guò)遞歸來(lái)求浩销，至于是什么是遞歸，遞歸實(shí)現(xiàn)的機(jī)制是什么听哭，我們說(shuō)的簡(jiǎn)單點(diǎn)就是自己是一個(gè)方法或者說(shuō)是函數(shù)慢洋，但是在自己這個(gè)函數(shù)里有調(diào)用自己這個(gè)函數(shù)的語(yǔ)句塘雳，而這個(gè)調(diào)用怎么才能調(diào)用結(jié)束呢？普筹，這里還必須有一個(gè)結(jié)束點(diǎn)粉捻，或者具體的說(shuō)是在調(diào)用到某一次后函數(shù)能返回一個(gè)確定的值，接著倒數(shù)第二個(gè)就能返回一個(gè)確定的值斑芜，一直到第一次調(diào)用的這個(gè)函數(shù)能返回一個(gè)確定的值肩刃。
實(shí)現(xiàn)這個(gè)算法可以簡(jiǎn)單分為三個(gè)步驟：
（1） 把n-1個(gè)盤子由A 移到 B；
（2） 把第n個(gè)盤子由 A移到 C杏头；
（3） 把n-1個(gè)盤子由B 移到 C盈包；
從這里入手，在加上上面數(shù)學(xué)問(wèn)題解法的分析醇王，我們不難發(fā)現(xiàn)呢燥，移到的步數(shù)必定為奇數(shù)步：
（1）中間的一步是把最大的一個(gè)盤子由A移到C上去；
（2）中間一步之上可以看成把A上n-1個(gè)盤子通過(guò)借助輔助塔（C塔）移到了B上寓娩，
（3）中間一步之下可以看成把B上n-1個(gè)盤子通過(guò)借助輔助塔（A塔）移到了C上叛氨；
java源代碼
package demo;
/**
* 目的：實(shí)現(xiàn)漢諾塔問(wèn)題求解
* 作者：Dmego 時(shí)間：2016-10-15
*/
import java.util.Scanner;
public class TowersOfHanoi {
static int m =0;//標(biāo)記移動(dòng)次數(shù)
//實(shí)現(xiàn)移動(dòng)的函數(shù)
public static void move(int disks,char N,char M)
{
System.out.println("第" + (++m) +" 次移動(dòng) : " +" 把 "+ disks+" 號(hào)圓盤從 " + N +" ->移到-> " + M);
}
//遞歸實(shí)現(xiàn)漢諾塔的函數(shù)
public static void hanoi(int n,char A,char B,char C)
{
if(n == 1)//圓盤只有一個(gè)時(shí)，只需將其從A塔移到C塔
TowersOfHanoi.move(1, A, C);//將編b號(hào)為1的圓盤從A移到C
else
{//否則
hanoi(n - 1, A, C, B);//遞歸棘伴，把A塔上編號(hào)1~n-1的圓盤移到B上寞埠，以C為輔助塔
TowersOfHanoi.move(n, A, C);//把A塔上編號(hào)為n的圓盤移到C上
hanoi(n - 1, B, A, C);//遞歸，把B塔上編號(hào)1~n-1的圓盤移到C上焊夸，以A為輔助塔
}
}
public static void main(String[] args) {
Scanner imput = new Scanner(System.in);
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("******************************************************************************************");
System.out.println("這是漢諾塔問(wèn)題（把A塔上編號(hào)從小號(hào)到大號(hào)的圓盤從A塔通過(guò)B輔助塔移動(dòng)到C塔上去");
System.out.println("******************************************************************************************");
System.out.print("請(qǐng)輸入圓盤的個(gè)數(shù)：");
int disks = imput.nextInt();
TowersOfHanoi.hanoi(disks, A, B, C);
System.out.println(">>移動(dòng)了" + m + "次仁连，把A上的圓盤都移動(dòng)到了C上");
imput.close();
}
}
圖解程序運(yùn)行流程
（1）函數(shù)hanoi(int n,char A,char B,char C)的功能是把編號(hào)為n的圓盤借助B從A移動(dòng)到 C上。
（2）函數(shù)move(int n ,char N ,char M)的功能是把1編號(hào)為n的圓盤從N 移到M上
程序運(yùn)行截圖
