哈諾塔問題相信只要學習計算機的人都知道。這是一個古老而又偉大的問題。在這篇文章中，主要是給出遞歸解決漢諾塔問題的代碼方法。畢竟面試的時候，HR比我們要變態很多，怎麼蹂躪我們怎麼玩。
一、什麼是漢諾塔問題
這個問題來源於印度。有三個金剛石塔，第一個從小到大摞著64片黃金圓盤。現在把圓盤按大小順序重新擺放在最後一個塔上。並且規定，在小圓盤上不能放大圓盤，在三個塔之間一次只能移動一個圓盤。
也就是說將 from 上的圓盤全部移動到 to 上，並且要保證小圓盤始終在大圓盤上。
如何來求解呢？很明顯這道題大家都知道使用遞歸的方式來做。不過如何去考慮遞歸呢？
在這裡我想說一下我個人目前關於遞歸的理解。遞歸其實就是一個方程式：f(n) = f(n-1) + a;也就是說在設計遞歸的時候應該考慮下面三個方面：
（1）求解f(n)的時候，假設f(n-1)已經求解出來了。我們不要去考慮f(n-1)是如何求解出來的。
（2）關鍵點在於遞歸的結束條件。
（3）遞歸往往和分治法是分不開的。對於複雜的遞歸，往往將遞歸拆分。然後再合併
整體的遞歸方法流程是這樣的。首先我們要寫一個遞歸方法。
（1）首先判斷遞歸結束時候的操作
（2）遞歸分解
而本題的漢諾塔就是使用典型的遞歸思想。首先我們求解f(n)
① 將 n-1 個圓盤從 from -> buffer
② 將 1 個圓盤從 from -> to
③ 將 n-1 個圓盤從 buffer -> to
④以上三步都是為了求解f(n)，最後我們給出遞歸結束的條件。只有一個圓盤的時候，只需一次移動操作即可。
二、代碼實現
分享到:
閱讀更多 Java的架構師技術棧 的文章
