Python 程式練習 5 ─ 河內塔

http://4rdp.blogspot.com/2021/12/python-5.html?m=0

如左圖所示，有一碟盤子尺寸由下而上依次變小，然後要搬移這些盤子從最左搬到最右邊，中間有一個緩衝區，所以共有三處可以放盤子，搬動的規則如下：

一、每次只能搬一個盤子

二、大盤子不能疊在小盤子上面

請用遞迴的方法，寫出 N 個盤子，需要幾步才能完成所有盤子的搬移？

有些特定的問題需要用特定的方法才能解，比如河內塔就需要遞迴解題。

所有的 FOR loop 都可以用遞迴來處理，若說傳統 FOR loop 是以正向思考解決問題，那遞迴就是逆向思考來解問題，不過它有個前提，這問題須能在有限步驟內解決，而且處理問題也不能中途停止，因為這將會沒有解答可以逆推出結果。

最近 Andy 計算機概論課程上了遞迴 (Recursion)，這對資工的同學是非常重要的程式設計技巧，老師出了 一些作業，他寫的唉唉叫，問我會不會，雖然我有多年程式經驗，但遞迴不是我熟悉的程式技巧，因此沒辦法幫他甚麼忙，他看了同學程式範例兩天，然後親自寫河內塔程式，才充分悟道，因此他建議學習這個單元的同學，一定要寫一遍河內塔程式，就可以搞清楚遞迴機制，他學習遞迴這方法後的心得是分而治之 (Divide and Conquer)，就是要切割問題，然後一塊一塊處理掉。