第三章第三節(jié) 棧與遞歸的實(shí)現(xiàn)
棧大家都熟悉，先進(jìn)后出，棧頂在下，棧底在上，添加元素會(huì)棧底位置增加
棧的特性決定了它在處理一些特殊情況的時(shí)候很占優(yōu)勢(shì)，例如，括號(hào)匹配，這節(jié)重點(diǎn) - 遞歸

漢諾塔相信大家都很熟悉，規(guī)則很簡(jiǎn)單，目的就是將x上的三個(gè)餅插到z上，大餅不能在小餅上面，一次只能移動(dòng)一個(gè)餅。如圖：

靈魂畫(huà)師之漢諾塔

二話不說(shuō)就是一個(gè)算法

void hanoi (int n, char x, char y, char z) {
    //函數(shù)意義：將塔座x上按直徑從小到大且自上而下編號(hào)為1-n 的n個(gè)圓盤(pán)按規(guī)則搬至z，y做輔助
    if(n == 1) {
        move(x, 1, z);
    } else {
        hanoi(n-1, x, z, y);
        move(x, n, z);
        hanoi(n-1, y, x, z);
    }
}

漢諾塔的遞歸其實(shí)挺簡(jiǎn)單的，但是它就是實(shí)實(shí)在在的對(duì)于遞歸核心思想的考驗(yàn) - 如何設(shè)計(jì)遞歸？
我認(rèn)為遞歸的核心在于1、如何將問(wèn)題一層層剝開(kāi)；2、剝開(kāi)到最后是一個(gè)最簡(jiǎn)單的操作。

我對(duì)于漢諾塔的遞歸思路是這樣的:

• 漢諾塔目的是將整個(gè)塔轉(zhuǎn)移，而這個(gè)塔每少一層，就是對(duì)于問(wèn)題的一層簡(jiǎn)化，直至最終只剩下一層，這個(gè)時(shí)候，漢諾塔就成為了最簡(jiǎn)單的一次操作了。所以先定下最基本操作，把“最上的某1層”從“起點(diǎn)”挪到“目的地”。
• 然后來(lái)看遞歸體如何設(shè)計(jì)，這個(gè)就是需要了解漢諾塔的規(guī)則了，漢諾塔不能同時(shí)挪動(dòng)多個(gè)，而且只能把小的放在大的上面，而我們有一個(gè)輔助塔座可以使用。這時(shí)如何一層層剝開(kāi)這個(gè)問(wèn)題的答案已經(jīng)出來(lái)了，就是我們每次轉(zhuǎn)移一層的時(shí)候，將這一層跟其上的所有層分離開(kāi)，如此完成問(wèn)題的一層層剝離。so，遞歸體就是，借助另外的那個(gè)塔座作輔助，將要挪動(dòng)的那一層上面的所有層先轉(zhuǎn)移到輔助塔座，然后轉(zhuǎn)移最下層到目的塔座，然后再將輔助塔座上的那幾層轉(zhuǎn)移到目的塔座。

emmm，大致就是這樣了，希望我說(shuō)清楚了，如果沒(méi)說(shuō)清的話，溜了溜了~

歡迎大家關(guān)注我的公眾號(hào)

半畝房頂