前幾天逛b站的時候刷到了一個有關(guān)漢諾塔游戲與遞歸思想的講解演示視頻，我個人認為是目前為止b站上面，能夠?qū)h諾塔遞歸思想講解得最為直觀和通俗易懂的視頻。在這里貼上視頻鏈接，可以自行去觀摩一下：

在完整且反復(fù)地觀看了幾遍之后，我的心情久久不能平復(fù)，感嘆自己當(dāng)時在課堂上學(xué)習(xí)遞歸這一章節(jié)得時候，如果我的講師能夠拿著同等質(zhì)量的演示課件給臺下的學(xué)生授課，至少大家在初遇遞歸的時候多少能體面一些。

大多數(shù)人最初接觸到遞歸原理，大概率是源自漢諾塔這個游戲，作為遞歸算法及其思想最為經(jīng)典的案例，是通向遞歸世界的必經(jīng)之路。可漢諾塔是如何利用遞歸，在嚴格遵守游戲規(guī)則的前提下，好似萬劍歸宗般地、有條不紊地走向游戲終點？盡管源碼就呈現(xiàn)在眼前，大部分初學(xué)者也無法輕松理解漢諾塔的遞歸思想，我也不例外。事實上我對漢諾塔的遞歸思想不甚了然，過去我對遞歸的認知僅停留在斐波那契數(shù)列的遞歸思路（非常糟糕的例子），直到我打算重新審視漢諾塔遞歸原理，結(jié)合上述視頻的講解模型以及我個人的思考，重溫其中所蘊含的遞歸思想。

其實初學(xué)者對漢諾塔遞歸思想的理解最大困難在于，一旦柱子上的圓盤數(shù)量超出“簡單模式”的范疇，從直觀角度來說，之后圓盤的移動次序、軌跡看起來就會比較“凌亂”，盡管漢諾塔本身存在一定的游戲規(guī)則，即把A柱上的帶孔圓盤全部移到C柱上，并仍保持原有順序疊好；每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一柱上，不過這樣的游戲規(guī)則對于我們來說依舊是有很大的操作空間。此時我們的思維往往會更專注于盡可能多地移動圓盤以接近問題求解的終點，停留在一個較大的時空跨越尺度上，從而忽略將求解步驟拆分的思路。

所以何為遞歸？以我個人的理解，首先這是一種解決實際問題的有效手段，遞歸遵循固定步驟將一個問題規(guī)模由大到小、化繁為簡地不斷劃分，逐步求解的過程，基本思想是分而治之。因此，再復(fù)雜的漢諾塔也脫離不了游戲框架本身，完全可以參考“簡單模式”下漢諾塔的解題思路。

最簡單的漢諾塔只有A柱上1個圓盤，思路也很簡單，因為圓盤上方無其他圓盤阻擋，無需考慮其他圓盤的影響，直接將A柱上的圓盤遷移至C柱即可完成游戲；當(dāng)圓盤數(shù)量增至2個時，這時需要在移動的過程中考慮到圓盤彼此之間的影響，不過思路依舊很簡單，如圖所示：

在此過程中，分別重新賦予ABC這三個柱子Src、Tmp、Dst別稱，這有助于我們理解遞歸過程中圓盤的遷移軌跡，遵循上述遷移步驟，可以用最短的遷移次數(shù)達成目標(biāo)。從劇透的層面來說，以上“三部曲”就是漢諾塔遞歸的基本思路（真的嗎？我不信?。秩绾谓忉尭鄨A盤的例子呢？

原理基本類似，無論如何，為了能夠保持原有排列順序、移動全部的圓盤至終點，那么底層的圓盤就一定會比上層的圓盤先遷入終點，因此就需要每一層圓盤給相鄰的下層圓盤讓路，最極端的例子就是除最底層的大圓盤之外，其他上層圓盤均需要給它提前讓路。

到這里問題就簡化很多了，在每一輪遷移過程中，我們的目光僅需要放在當(dāng)前圓盤以及它以上的圓盤部分就足夠了。移動當(dāng)前最底層的圓盤，就需要將其以上全部圓盤遷移至一個臨時區(qū)域，然后恭迎當(dāng)前圓盤入座終點，接著再把上層圓盤從臨時區(qū)全部挪到終點便完事了，對照著來看不就是2層塔的遷移模式嘛？這種層層嵌套的形式讓漢諾塔具備了遞歸的特性，即具有固定的操作步驟，問題規(guī)模可以從大到小不斷劃分。

由上述步驟可得，漢諾塔遞歸算法的偽代碼如下：

此時新的疑問來了，關(guān)于Src、Tmp、Dst這三個參數(shù)，也就是ABC三個柱子的傳入順序貌似有些莫名其妙，不是太好理解。確實，關(guān)于傳參順序問題過去也是困擾我理解漢諾塔遞歸算法的攔路虎之一，但是如果結(jié)合n層漢諾塔的遷移步驟來看也不難理解，當(dāng)前函數(shù)棧幀的傳參順序為Src (A)、Tmp (B)、Dst (C)，符合3根柱子初始狀態(tài)的描述；假設(shè) n > 1 ，緊接著的傳參順序是Src、Dst、Tmp，需要遷移的圓盤數(shù)量變?yōu)?n - 1?，很明顯對應(yīng)的就是步驟1，所要表達的含義就是將除最下層以外的n-1個圓盤從Src遷移到Tmp，那么Tmp，也就是對應(yīng)著的B柱，就是這 n - 1個圓盤的目標(biāo)區(qū)域，因此原本的Dst位置就需要傳入Tmp參數(shù)，同時Dst參數(shù)就充當(dāng)臨時區(qū)域傳入原本的Tmp位置。MoveDisc對應(yīng)的是步驟2，將最底層的圓盤從Src遷移到Dst終點處，這沒什么好說的。同理可得最后的傳參順序Tmp，Src，Dst，意思就是將上層 n - 1個圓盤從Tmp遷移到Dst終點，此時，Tmp作為起點，Src充當(dāng)臨時區(qū)域。開頭的演示視頻中，采用的是調(diào)換柱子位置的方式來解釋步驟3的傳參順序，其想要表達的意思是在遷移過程中，各個柱子所發(fā)揮的作用也在不斷變化，因此需要我們及時更換視角。在此基礎(chǔ)上，使用Src、Tmp、Dst作為ABC參數(shù)的別名，可以輔助我們更好地理解傳參順序的問題。

最后附上漢諾塔C程序執(zhí)行效果：

所以……結(jié)束了嗎？試想一下漢諾塔的這種特征和數(shù)據(jù)結(jié)構(gòu)棧是什么關(guān)系？畢竟我個人覺得這兩者多少有些相似之處，準(zhǔn)備好3個棧，且只需要加上壓棧元素比棧頂元素小這個條件，逐個遷移棧內(nèi)的元素即可。本文觀點僅為個人愚見，難免有疏漏謬誤之處，歡迎批評指正。

參考資料：

• https://www.bilibili.com/video/BV1Zh411y7XB????(漢諾塔小游戲和遞歸思想)

• https://www.cnblogs.com/CVE-Lemon/p/16188008.html????(C語言漢諾塔遞歸算法實現(xiàn) - CVE-檸檬i)