一次看懂遞迴 (Recursion) 的思維模式（一）
遞迴的基礎思維
這篇系列文章，是想要帶領程式的初學者進入遞迴（Recursion）的世界。或許閱讀文章的你，對基本的迴圈操作有一定的認識了，但沒學過遞迴，或曾經聽過但總覺得一頭霧水，平時寫程式也幾乎沒使用過。
這篇文章就是希望幫助這樣的人們，從最基礎的題目慢慢掌握思考方式，同時也會介紹各種不同的遞迴技巧與他們的實用價值，後續當然也會帶大家學習如何靠他解決面試常見的演算法題目。最終，希望能讓讀者將遞迴的概念內化，讓他從此不再高不可攀。
那我們就開始吧！首先，來聊聊基礎遞迴常見的思維方式之一
- 先將一個大問題，拆解成幾個較小的問題
- 每個較小的問題，又能依照相同方式拆成更小的問題
- 每當小問題解決時，大問題也可以依靠小問題的結果來解決
- 每層的解決方法都是一樣的，除了最小的問題以外
- 根據以上幾點，我們可以不斷套用相同的函數，讓他自己幫自己解決問題
以上就是遞迴的基本核心精神，如何分析看不懂沒關係，我們先來看個最基本的例子
從 1 加到 X
我們想寫一個函數，可以幫我們從 1 加到變數 x。如果用迴圈的寫法，就是
def sum_1_to_n(x):
ans = 0
for i in range(1, x+1):
ans += i
return ans很簡單對吧，但現在我們想改用遞迴的思維來解決這個問題，我們的思考方式會變成如下：
- 我們的大問題是如何從 1 加到 x
- 如果我們知道怎樣處理小一點的問題，例如從 1 加到 x-1
- 那我們只要先處理好小問題，最後再把其答案加上 x 即可
照著上面的思路的話，我們就會寫下如下的程式碼
def sum_1_to_n(x):
return x + sum_1_to_n(x-1)這個思維就是，如果我想算 sum(1~10)，我可以改成算 10 + sum(1~9)。那如何算 sum(1~9) 呢？當然就是 9 + sum(1~8) 依此類推下去。
但最後還有個小問題，如果我們要算 sum(1~1)，該怎麼做？如果寫成 1 + sum(1~0) 似乎有點不合理，所以這就是我們所謂的最小問題，需要額外的處理，很幸運的是我們的最小問題非常容易，因為我們已經知道答案是 1。因此將上面的程式碼稍作修改後，最終答案如下：
def sum_1_to_n(x):
if x == 1:
return 1
return x + sum_1_to_n(x-1)PS：依據題目定義，我們的 x 值輸入必須 ≥ 1，所以不需處理 x<1 的情境。讀者也可以停下來思考一下，如果我硬是要輸入 -1 會發生什麼事？又要如何防範？
到此為止，我們用兩種方法解決了相同的問題
- 迴圈（Iteration）
- 遞迴（Recursion）
迴圈應該對大多工程師來說都非常的直覺了，那我們為何還需要學遞迴的做法呢？以上述例子來說，他雖然讓程式碼簡潔了一點點，不過思考起來稍微難了點，似乎有利有弊。
但其實這個小小的思維方式的轉換，正是學習遞迴最重要的地方，因為有很多的演算法，靠遞迴的思路來寫可能會非常容易，但用迴圈的寫法反而會很困難。本篇下面，與接下來的系列，就是要慢慢帶大家建立更多種遞迴的思維模式，並介紹許多遞迴的經典演算法題目給大家。
先來看一下兩種思維本質上的差異，你會發現一件有趣的事：
- 當用迴圈（Iteration）思考時，你則總是得很明確的告訴電腦每一個變數的值要如何改變，所以得想清楚這些值的所有變化過程。
- 當用遞迴（Recursion）思考時，我們並不直接思考如何解決問題，而是先思考問題能否被拆小，還有大問題跟小問題間的關聯性。
重新用遞迴思維看一次上面的例子，當我們有了一個空殼的 function 如下
def sum_1_to_n(x):
???我們並不清楚該如何實作他，但我想的是假如這個 function 可以運作，那我如何利用他自己來幫自己解決問題。於是我們想的東西是
- 我發現一個轉移式 sum_1_to_n(x) = x+ sum_1_to_n(x-1)
- 那依此類推，sum_1_to_n(x-1) = x+ sum_1_to_n(x-2) … 這個等式可以繼續無限循環下去。
- 而我也知道最小問題 sum_1_to_n(1) 的答案是 1，所以在最小問題可以停下直接給答案。
若反過來說，也可以想成
- 我知道 sum_1_to_n(1) 的答案是 1
- 那套用轉移式，我可以知道 sum_1_to_n(2) = 2 + sum_1_to_n(1) = 2 + 1 = 3
- 繼續以上，我們可以知道 sum_1_to_n(3) = 3 + sum_1_to_n(2) = 3 + 3 = 6 … 如此循環下去，我就能知道任意的 sum_1_to_n(x) 的值了
以這個例子來說，有點類似高中時學習的數學歸納法，不過有些更複雜的例子就會不太一樣了。接下來就讓我們來看另一個非常經典的問題。
河內塔
河內塔是個經典的益智問題，題目是這樣：
我們有三根柱子，並有 N 個圓盤套在最左邊柱子上面（上圖 N = 4)，現在我們要把它們全部移動到最右邊的柱子上，請問我們最少需要移動幾次？
以下是移動的規則：
- 每次可以選定一根柱子，移動最上方的一個圓盤到任意柱子上
- 大的圓盤不可以疊在小的圓盤上面
如果小時後有玩過這個遊戲，你可能已經開始在腦中一步一步嘗試了，如果你能想到一個最佳策略，那恭喜你，你一定有辦法寫出一個迴圈（Iteration）版本的解法，只要重複你的策略即可。但想出這個策略與用程式描述這個策略都不是這麼的容易，現在，讓我們看看遞迴（Recursion）的思維模式怎樣幫我們更簡易的得到答案。
遞迴思維：大問題沒頭緒的話，先想一下，如果能解決稍微小一點的問題，是不是就能靠他幫忙，來解決大問題了。
- 大問題：移動 4 個圓盤總共需要幾步
- 小一點的問題：移動 3 個圓盤總共需要幾步（相同的問題，但範圍變小）
先假設我們已經知道第 2 個小問題的答案（至於怎麼做的先不用管），再加上一個小小的觀察，由於三根柱子並沒有任何不同，所以把 N 個圓盤，從任何一個柱子，全部移到另一個柱子上，需要的步驟都是一樣的。那我們就可以把原始問題想成下面這樣。
- 從最左邊，先把上面 3 個圓盤移到中間
2. 從最左邊，把最下面的 1 個圓盤移到最右邊
3. 從中間，把剛剛那 3 個圓盤移到最右邊
所以，假如移動 3 個盤子需要的步驟數是 K，那移動 4 個盤子需要的步驟數就是 K（移動三個盤子到中間） + 1（移動最下面盤子） + K（從中間移動三個盤子到最右邊） = 2 * K + 1
因此我們得到了一個寶貴的關係式：（移動 X 個盤子的步驟數）= 2 * (移動 X - 1 個盤子的步驟數) + 1
寫成程式碼的話就是：
def hanoi_tower_step(x):
return 2 * hanoi_tower_step(x-1) + 1當然，一樣不能忘記，我們都會有一個”最小問題”，他不能再繼續遞迴下去，在這邊我們的最小問題，當然就是只有 1 個圓盤的時候該如何處理，而很顯然的，這個答案也是 1。最終我們就會得到非常簡潔的答案如下。
def hanoi_tower_step(x):
if x == 1:
return 1
return 2 * hanoi_tower_step(x-1) + 1動動腦時間：你也可以把最小問題想成 0 個圓盤，那步驟數當然就是 0，稍微想一下，如果是這樣去理解問題，要怎樣修改你的程式碼，讓最終得到的答案是一樣的。
靠著遞迴的思維，我們甚至根本就不知道移動盤子的最佳策略是什麼，或說我們唯一需要知道的策略，只有如何移動 1 個盤子，也就是 1 步，或 0 個盤子也行，就是 0 步，剩下的就只剩找到大小問題之間的關聯性就解決了，是不是很強大。
其他常見的簡單經典例子還有：階乘、費氏數列、輾轉相除法、爬梯子 等等。有興趣的讀者可以自行練習看看，思考的時候我們想三個方向
- 他們的大問題跟小問題分別可以是什麼
- 大小問題的關聯式子怎麼寫
- 最小問題又是什麼
以費氏數列（Fibonacci）為例
- 大問題：找到費氏數列中，第 X 個數的數值
- 小問題1：找到費氏數列中，第 X-1 個數的數值
- 小問題2：找到費氏數列中，第 X-2 個數的數值
- 大小問題的關聯式：fibonacci(x) = fibonacci(x-1) + fibonacci(x-2)
- 最小問題：第 1 個與第 2 個數的數值
PS: 如果直接照著做或許會發現效率有點差，我們後續的系列會再回來解答這個問題，敬請期待
註2: 遞迴還有另一個小缺點是深度限制。簡單來說，就是遞迴的過程中，由於每個 function 都還沒執行完就又 call 了自己，那你就會堆積一堆執行到半路的 function，電腦需要一定的記憶體去記錄這些狀態，所以當你深度太超過就會炸掉（觸發 Stack Overflow），有興趣更深入理解的讀者可以看這邊的解說，常見的處理方式叫做 Tail Recursion。若以刷 Leetcode 題來說，由於題目會設計好，你幾乎是不會遇到這問題的，但實務中則要小心注意。
另外，河內塔問題也有一個進階挑戰，就是如何靠遞迴把最佳移動步驟也都印出來，我也將範例程式碼留在下方，有興趣的讀者可以試著思考看看這個 print_step_detailfunction 是怎麼做到的。
本章就到這邊結束啦，下一篇，我會帶大家介紹遞迴如何使用在非常有名的 Divide And Conquer 思維上，並且用它來處理兩個非常經典的排序問題：Merge Sort 與 Quick Sort。我們下篇見！
