最近在學C嘛，在遞歸這一節(jié)，老師舉到了漢諾塔作例子。在目瞪口呆于居然用這么少的代碼便能實現以至于感嘆遞歸是神的同時，我在代碼里加了一個統計次數的功能。

（代碼寫得比較爛不要在意）

運行程序，隨便輸幾個數，然后……我好像發(fā)現了什么奇奇怪怪的東西。

應該能發(fā)現，如果將層漢諾塔的移動次數記為，那么應該有

結論有了，接下來該寫證明過程了，當然其實也不是很難。

不妨將漢諾塔的三根軸記為

記層漢諾塔移動次數為，易見，

注意到，層漢諾塔的解法可拆解為三步：

①將上面的層漢諾塔從軸移動到軸

②將最下面的片從軸移動到軸

③將層漢諾塔從軸移動到軸

易見①③需要的步驟均為次，而②需要次

故而

可以通過湊系數得解

讓我想起了高中的數學題（

兩邊同時加，有，

由此可見是以為首項，為公比的等比數列。

，

證明完畢。