一次看懂遞迴 (Recursion) 的思維模式（三）

窮舉可能性（Backtracking)

Published in

AppWorks School

8 min readMay 30, 2021

這是系列文的第三篇文章，前兩篇都在聊大問題跟小問題的關聯性，但遞迴還有其他用法，本篇就來和大家聊聊另一種常見的使用方式：窮舉所有可能性，又稱為回溯法（Backtracking）。窮舉顧名思義，就是把所有可能性都一一列舉一遍，有些題目是非常容易的，例如要你印出整張 99 乘法表，那最簡單的做法當然就是用兩個迴圈，窮舉 1*1=1, 1*2=2, … 9*9=81 即可。但有些題目就不那麼容易了，這時我們可以利用遞迴的另一種思維，一層一層的往下走，就像全面啟動一樣，你要知道你走到了第幾層夢境，然後帶著必要的資訊繼續往下層走，直到走到某一層必須停止，然後往上回溯回來，整個過程中你就會找到（人生的？）答案，並小心不要迷失在裡面…。

不囉唆了，直接來看問題吧！

列出所有可能的數字密碼

假如有一天你忘了自己的手機密碼，想寫個程式幫你嘗試所有可能的組合來暴力破解，你該怎麼做呢？

當然，假如密碼只有 4 位數，最簡單的做法是寫個 4 層迴圈，但這樣一來程式碼很醜，二來很不利於修改，假如有一天我想換成 6 位數密碼，你還得再多加兩層迴圈，非常的不方便。這時候讓我們來看看遞迴版本的想法。

爲了更易於理解，我們先將問題再簡化一下，現在考慮只有 3 位數的密碼，且每一位數只有 1～3 三種數字。所以我們所有可能的密碼就是

111, 112, 113, 121, 122, … , 331, 332, 333（共 27 種）

接下來我們將問題分成一層一層來處理。每次呼叫自己（遞迴）時，其實就是往下一層走的意思，而每一層就是多一碼。

最開始只有一個空的東西，孤單的存在世界上（可以假想爲第 0 層）

2. 我們的第零層，會一一對空的 Array 填上所有可能的數字，再往下層傳下去，所以到第一層的時候，每個第一層的人，應該都有一個元素了，如下圖。可以把他想成整個密碼中第一碼的所有可能分支。

3. 第一層則是同樣對每個東西，再後面繼續分別 append 1, 2, 3，再往下層傳下去第二層（遞迴開始了）。所以第二層如下圖。也就密碼前兩碼的所有可能分支

4. 同樣的，在第二層時，一樣對每個 append 1, 2, 3，再傳到第三層。如下圖

到這邊為止，因為已經到了我們預設的最後一層，我們會在這層停下，並成功窮舉了所有可能的三位數密碼。

現在，概念講完了，我來帶大家一步步看遞迴的程式碼要怎樣寫出來！

首先，我們將這個 function 暫且稱作 create，他會需要以下三個參數

現在層數（深度）：depth（一開始等於 0）
最大層數（深度）：max_depth（這個目前等於 3，因為是 3 位數密碼）
到這一層時的密碼：password（一開始是一個空 Array）

def create(depth: int, max_depth: int, password: List[int]):
    print(depth) # 印出層數

往下層走，在程式上代表的就是，遞迴呼叫自己一次，並將層數 + 1（depth + 1），如果執行以下程式碼，你應該就會看到不斷增加的層數（直到 stack overflow…）

def create(depth: int, max_depth: int, password: List[int]):
    print(depth) # 印出層數
    create(depth + 1, max_depth, password) # 往下層走

接下來，要在每一層時，將上層給你的 Array 在後面 append 1～3 ，然後傳到下層去。該怎麼做呢？

def create(depth: int, max_depth: int, password: List[int]):
    for i in range(3):
        new_password = password + [i+1]
        create(depth + 1, max_depth, new_password) # 往下層走

如此一來，你會呼叫自己 3 次，這三個就會走入下一層，他們的深度會 +1，並且 password 分別被增加了 [1], [2] 與 [3]，最核心的部分已經完成！

但上面這個做法有個小小的缺點，他會讓每次往下層走的時候，password 整個被重新複製一份（new_password = password + [i+1] 造成），要解決這個問題，可以採用以下寫法，但須要動一點腦筋想想他在做什麼。

def create(depth: int, max_depth: int, password: List[int]):
    for i in range(3):
        password.append(i + 1)
        create(depth + 1, max_depth, password) # 往下層走
        password.pop()

這次我們從頭到尾都在利用同一個 password Array（註：python 的 Array 是 pass by reference 的），沒有創造任何新的出來，而當我們每次往下層走的時候，都要多塞一個密碼數字給他 password.append(i + 1) ，但是當我們結束了這層下面的所有事情後，回到原本這層，並要進入迴圈的下一輪之前，得將剛剛加進去的新東西給 pop 掉 password.pop() 。下圖以第零層為例，你的迴圈分別會經過這九個步驟，可以對照程式碼看一遍。

如果你到現在還有跟上，恭喜你，你已經理解了用遞迴窮舉可能性的最核心精神了！這也是回溯法（Backtracking）的核心精神，不斷往下層窮舉所有可能性，並在正確的時候結束並回溯，然後繼續走另一條路。而有些更進階的回溯法會有更多可以提早結束的條件，來讓搜索的東西減少，我們稱之爲剪枝（pruning）。如果讀者曾經有學過樹（Tree）與圖（Graph）的深度優先搜尋演算法（Depth First Search），觀念也是相似的。

最後，讓我們把整份程式碼完成，還記得我們前兩篇都會有一個最小問題，讓他終止遞迴，現在也是類似的，只是從最小問題，換成最後問題，也就是當層數抵達我們最終的目標時，即可停止，同時我們也在此處印出答案。寫法如下：

def create(depth: int, max_depth: int, password: List[int]):
    if (depth == max_depth): # 最後一層達到即停止
        print(password) # 印出答案
        return    for i in range(3):
        password.append(i + 1)
        create(depth + 1, max_depth, password) # 往下層走
        password.pop()

最後一樣給大家看一下完整的程式碼

覺得自己有看懂，想挑戰一下的讀者，也可以思考看看以下三個問題：

基本問題：原本的問題（4 位數密碼，數字可以是 0~9）該怎麼做呢？
進階問題：如果想找到所有 digit 的和小於 10 的密碼，又該怎樣改呢？（e.g. [1,3,2,1] 符合條件，因為相加為 7。[4,3,7,2] 不符合條件，因為相加為 16）
相似問題：用上面的概念，寫出遞迴版本的 99 乘法表

PS：另外有個小技巧可以讓程式碼更簡潔一點點，就是我們不在 create function 中傳遞最大層數（max_depth）的資訊，而是將 depth 一開始就傳入最大層數，且往下遞迴時，將層數從 +1 改成 -1，如此只要層數歸零時就知道自己到最後一層了，有興趣的讀者也可以嘗試看看。

本篇就到這邊結束，下一篇，會和大家介紹如何應用 Backtracking 的技巧，來處理兩大面試常見的經典數學概念 — 組合（Combination）與排列（Permutation）。

一次看懂遞迴 (Recursion) 的思維模式（三）

窮舉可能性（Backtracking)

列出所有可能的數字密碼

系列連結

Written by Arthur Lin