遞迴 — Recursion Interactive（C++）

CONTENTS · 內容目錄

P00什麼是遞迴？ P01遞迴三法則 P02整數轉字串 P03呼叫堆疊 P04視覺化遞迴 P05Sierpinski 三角形 P06河內塔 P07走迷宮 P08動態規劃 EX練習題 REF總覽比較

PROLOGUE · 開場

遞迴：把問題交給「更小的自己」 cppds §5.1–5.3

遞迴（recursion）= 函式呼叫自己，每次都處理更小的同型問題，直到小到可以直接回答（base case）。 sum([1,3,5,7,9]) 其實就是 1 + sum([3,5,7,9]) ：括號一路往內，再一路往外收。

虛擬碼 CODE

int listSum(vector<int> numList):
    if numList.size() == 1:       // base case
        return numList[0]
    else:                          // 縮小問題
        return numList[0] + listSum(numList 去掉第一個)

遞迴 vs 迴圈

凡是遞迴能算的，迴圈都能算（反之亦然）。遞迴的價值是讓程式長得像問題的定義：樹、分治、回溯問題上特別優雅。

PART 01 · 三法則

遞迴三法則：寫對遞迴的檢查清單 cppds §5.4

法則 1

必須有 base case
小到能直接回答的情況（listSum：長度 1）。

法則 2

必須朝 base case 前進
每次呼叫都要改變狀態、縮小問題（串列變短、n 變小）。

法則 3

必須呼叫自己
用「相信小問題已解決」的心法組合出大問題的答案。

QUIZ · 抓出壞遞迴

int f(int n) {{ return n + f(n - 1); }} 違反了哪條法則？執行會怎樣？

(A) 缺 base case → stack overflow

(B) 沒有呼叫自己

PART 02 · 進位轉換（遞迴版）

整數轉任意進位字串：遞迴自帶「反轉」 cppds §5.5

第 3 章用 stack 反轉餘數順序；遞迴版連 stack 都不用自己管：「先遞迴處理商、回來再接上自己的餘數」的順序天然就是高位在前。因為 call stack 就是那個 stack。

虛擬碼 CODE

string toStr(int n, int base):
    digits = "0123456789ABCDEF"
    if n < base:                // base case：一位數
        return digits[n]
    else:
        return toStr(n / base, base) + digits[n % base]

跟第 3 章比一比

stack 版：自己 push 餘數、自己 pop。
遞迴版：把餘數留在「回來之後」處理：call stack 代勞。

講義練習：用遞迴反轉字串

講義在這裡留了一題填空：寫一個遞迴的 reverse(s)，讓 reverse("hello") 回傳 "olleh"。原題挖掉兩個空，解答是：

reverse：尾巴先反、頭字殿後 CODE

string reverse(string s) {
    if (s.length() == 1) {
        return s;                  // base case：一個字元不用反
    }
    return reverse(s.substr(1)) + s[0];
}                                // 「剩下的反轉」接上「第一個字」
 
assert(reverse("hello") == "olleh");  // Pass

用三法則檢查：base case 是長度 1； s.substr(1) 每次少一個字元，確實朝 base case 前進；而且它呼叫自己。跟 toStr 同一個骨架：把「接字元」延後到遞迴回來之後，順序就自動反了。

QUIZ · 換個接法

把最後一行改成 return s[0] + reverse(s.substr(1));，會得到什麼？

(A) 原字串（一點都沒反）

(B) 一樣是反轉

PART 03 · 呼叫堆疊

Stack frame：遞迴在記憶體裡長什麼樣 cppds §5.6

每次函式呼叫，系統就在 call stack 推入一個 stack frame（區域變數＋返回位址）。遞迴深 n 層 = 同時存在 n 個 frame。return 就是 pop：把值交回上一層 frame 停住的位置。

為什麼會 stack overflow？

call stack 容量有限（預設約 1~8 MB）。 base case 寫錯 → frame 無限堆積 → 爆掉。這也是深遞迴（如 n=10⁶ 的線性遞迴）要改寫成迴圈或加大堆疊的原因。

尾遞迴

若遞迴呼叫是函式的最後一步，編譯器（-O2）常能重用當前 frame（尾呼叫最佳化），把遞迴變成迴圈。

PART 04 · 視覺化

視覺化遞迴：螺旋與碎形樹 cppds §5.7 · 講義補充

課堂投影片跳過本節（RISE skip）：屬自學補充。

遞迴難學，常常是因為腦中缺一張圖。講義用 turtle 畫圖建立直覺（課堂有現場 demo），這裡用 canvas 重現同一套邏輯，原理一個字都沒變。

先看螺旋：每一步往前畫一段線、右轉 90 度，然後用短一點的長度呼叫自己。長度歸零就是 base case。

樹的深度

螺旋 CODE

drawSpiral(t, lineLen):
    if lineLen > 0:      // base case：長度歸零
        t.forward(lineLen)
        t.right(90)
        drawSpiral(t, lineLen - 5)

碎形樹 CODE

tree(branchLen, t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen - 15, t)   // 右子樹
        t.left(40)           // 退掉 20 再左轉 20
        tree(branchLen - 15, t)   // 左子樹
        t.right(20)
        t.backward(branchLen)  // 退回分岔點

碎形是什麼？

不管放大多少倍，長相都跟整體一樣：海岸線、雪花、樹。「一棵樹 = 樹幹 + 右邊一棵小樹 + 左邊一棵小樹」，這句話本身就是遞迴定義。注意畫的順序：先一路往右畫到最細的枝，才回頭補左邊，跟呼叫堆疊的展開順序一致。

PART 05 · 三路遞迴

Sierpinski 三角形：一次生三個自己 cppds §5.8 · 講義補充

課堂投影片跳過本節（RISE skip）：屬自學補充。

手繪流程只有三句話：畫一個大三角形；連接三邊中點，得到四個小三角形；中間那個不管，對三個角落的小三角形重複同樣程序。 base case 是人為設定的degree（碎形深度）：每遞迴一層減 1，減到 0 就停。

degree 3

三路遞迴 CODE

sierpinski(points, degree, t):
    drawTriangle(points, color[degree], t)
    if degree > 0:
        sierpinski(左下角 + 兩個中點, degree-1, t)
        sierpinski(頂角 + 兩個中點, degree-1, t)
        sierpinski(右下角 + 兩個中點, degree-1, t)
getMid(p1, p2): return ((p1.x+p2.x)/2, (p1.y+p2.y)/2)

畫的順序

程式會先鑽到左下角最小的三角形，把左下角整片畫完，再處理頂角、最後右下角。想像函式呼叫圖：越往下三角形越小，一次收完一整支子樹。河內塔、樹的走訪（第 8 章）都是同一種「多路遞迴」的親戚。

QUIZ · 數三角形

degree = 3 時，sierpinski 總共呼叫了幾次（含最外層那一次）？

(A) 1 + 3 + 9 + 27 = 40 次

(B) 3 × 3 = 9 次

PART 04 · 河內塔

河內塔：三行遞迴解千年謎題 cppds §5.10

把 n 個盤子從 A 搬到 C（大盤不能壓小盤）：相信 n−1 盤的搬法已存在，那 n 盤 = 先把 n−1 盤挪到中繼柱、搬最大盤、再把 n−1 盤疊回來。移動次數 $2^n - 1$。

速度

虛擬碼 CODE

void moveTower(int height, from, to, via):
    if height < 1: return        // base case
    moveTower(height-1, from, via, to)   // ① 上面 n-1 個搬到 via
    moveDisk(from, to)                // ② 最大盤直達 to
    moveTower(height-1, via, to, from)   // ③ n-1 個從 via 搬到 to

移動次數

3 盤7

5 盤31

n 盤2ⁿ − 1

64 盤 ≈ 1.8×10¹⁹ 步：傳說中僧侶搬完，世界末日。

PART 05 · 走迷宮

迷宮探索：遞迴回溯（backtracking） cppds §5.11

希臘神話裡忒修斯進迷宮殺牛頭人，靠一團線找到回頭路。我們的演算法用的是另一個道具： 麵包屑。從起點問「往北一步之後，能走出去嗎」，這又是一個一模一樣的迷宮問題，於是遞迴。北邊不行換南邊，再換西邊、東邊。走過的格子撒麵包屑，下次踩到就立刻回頭，不然兩格之間會互相呼叫到天荒地老。回溯（backtrack）在程式裡就一件事：從遞迴呼叫 return。

四個 base case 要背起來：撞牆、踩到麵包屑（走過或死路）、到達邊緣（出口）、四個方向全部失敗。

速度

圖例：● 目前｜＋路徑｜− 死路

虛擬碼 CODE

bool searchFrom(maze, row, col):
    if 是牆:            return false
    if 走過/死路:       return false
    if 到達出口:        return true
    標記「走過」
    found = 往北 || 往南 || 往西 || 往東   // 短路：找到就停
    if found: 標記「路徑」
    else:  標記「死路」
    return found

Maze 類別 CODE

const char OBSTACLE='+', TRIED='.',
           DEAD_END='-', PART_OF_PATH='O';
class Maze {         // dscpp/maze.hpp
    Maze(string filename) {
        ifstream f(filename);  string line;
        while (getline(f, line)) mazeList.push_back(line);
        // 掃每一列找 'S' → startRow / startCol
    }
    bool isExit(r, c) {   // 到達任一邊緣就是出口
        return r==0 || r==rows-1 || c==0 || c==cols-1;
    }
    void updatePosition(r, c, char v) { mazeList[r][c] = v; }
    vector<string> mazeList;  // 逐列讀進來的字串
};

searchFrom 的短路技巧 CODE

bool found = searchFrom(maze, row-1, col)   // 北
          || searchFrom(maze, row+1, col)   // 南
          || searchFrom(maze, row, col-1)   // 西
          || searchFrom(maze, row, col+1);  // 東
maze.updatePosition(row, col, found ? PART_OF_PATH : DEAD_END);
return found;

四個呼叫用 || 串起來：北邊一旦回報 true，剩下三個方向連試都不試（短路求值）。找到路的格子標 O、全敗的標 −，印出來就是完整的探索地圖。課堂版把這個 Maze 跑在 maze2.txt 上（dscpp/maze.hpp）。

PART 06 · 動態規劃

找零錢：從貪婪、天真遞迴，一路走到 DP cppds §5.12 · 講義補充

課堂投影片跳過本節（RISE skip，講義也標 Optional）：屬自學補充，但 DP 是後續演算法課的重要橋段。

自動販賣機要用最少的硬幣找零。37 分怎麼找？兩個 25 太多，一個 25、一個 10、三個 1，共六枚。這種「先拿最大的」叫貪婪法，美國硬幣（1、5、10、25）下它剛好都對。但假設某國多了一種 21 分硬幣：63 分的最佳解是三枚 21，貪婪法卻還是給你六枚（25+25+10+1+1+1）。貪婪法死在「當下最好」不等於「整體最好」。

那就老實遞迴：63 分的最少硬幣數，是「拿一枚 1 分之後 62 分的最少」「拿一枚 5 分之後 58 分的最少」…… 之中最小的那個加一。這個定義完全正確，卻慢得離譜：63 分要 67,716,925 次遞迴呼叫，因為同樣的子問題（例如 15 分）被翻來覆去重算了幾十次。講義給了三帖藥，一帖比一帖徹底：

版本	策略	63 分的呼叫數
makeChange1	天真遞迴：每次都重算	67,716,925
makeChange2	memoization：算過的存進表，先查表再遞迴	221
makeChange3	DP：乾脆從 1 分由小到大把表填滿，不遞迴	迴圈 63 × 4 步

memoization（也叫 caching）已經把爆炸壓下來了，但表裡還有洞、邏輯像補丁。真正的 DP 換一個角度：從 1 分開始，由小到大把每個金額的最佳解填進表格。填到第 c 分時，所有更小的金額都已經有答案，每格只要看「扣掉一枚硬幣後查表」哪個最小。

makeChange3（DP 本體）CODE

dpMakeChange(coins, change):
    minCoins[0..change] 全部初始化
    for cents = 1; cents <= change; cents++:
        best = cents               // 全用 1 元
        for (c : coins) if c <= cents:
            best = min(best, minCoins[cents - c] + 1)
        minCoins[cents] = best     // 只依賴更小的子問題
    return minCoins[change]

makeChange4：把「用了哪些硬幣」也記下來 CODE

// 填表時多記一筆：這格最後拿的是哪枚硬幣
minCoins[cents] = coinCount;
coinsUsed[cents] = newCoin;
 
void printCoins(coinsUsed, change) {
    int coin = change;
    while (coin > 0) {
        cout << coinsUsed[coin] << " ";
        coin = coin - coinsUsed[coin];  // 沿表回溯
    }
}

63 那格記著 21，跳到 42 又是 21，再跳到 21 還是 21：印出「21 21 21」。只多存一個陣列，就能把答案的內容也還原出來。

QUIZ · DP vs 天真遞迴

天真遞迴解 63 分要 6.7 億次呼叫、DP 只要幾千步。DP 快的核心原因是？

(A) 每個子問題只算一次（記住答案）

(B) DP 用了更聰明的硬幣順序

EXERCISES · 練習

動手驗證 cppds §5 綜合

EXERCISE 1 · 追蹤遞迴

toStr(10, 2) 的回傳值是？（動畫可驗證）

(A) "1010"

(B) "0101"

EXERCISE 2 · 河內塔

4 盤河內塔最少要移動幾次？其中「最大盤」移動幾次？

(A) 15 次；最大盤 1 次

(B) 16 次；最大盤 2 次

EXERCISE 3 · 迷宮 base case

迷宮遞迴少寫「走過的格子直接 return false」會怎樣？

(A) 相鄰兩格互相呼叫，無窮遞迴

(B) 答案錯但會停

REFERENCE · 總覽

本章遞迴問題一覽 cppds §5 總覽

問題	base case	縮小方式	複雜度
listSum	長度 1	去掉第一個元素	O(n)
toStr(n, base)	n < base	n / base	O(log n)
河內塔	height < 1	height − 1（兩次）	O(2ⁿ)
迷宮	牆／走過／出口	相鄰格子	O(格子數)
找零錢（DP）	金額 0	金額 − 硬幣面額	O(金額×硬幣種)

關鍵概念複習 ① 三法則：base case、朝它前進、呼叫自己。
② call stack 是隱形的 stack：第 3 章手動管理的，遞迴讓系統代管。
③ 分支遞迴（河內塔 2 支、迷宮 4 支）容易指數爆炸；重疊子問題時用 DP/memoization 收服。
④ Sierpinski 三角形等碎形：圖形的自相似 = 視覺化的遞迴（見講義 §5.8 turtle 圖）。

遞迴：把問題交給更小的自己

遞迴：把問題交給「更小的自己」 cppds §5.1–5.3

遞迴三法則：寫對遞迴的檢查清單 cppds §5.4

整數轉任意進位字串：遞迴自帶「反轉」 cppds §5.5

講義練習：用遞迴反轉字串

Stack frame：遞迴在記憶體裡長什麼樣 cppds §5.6

視覺化遞迴：螺旋與碎形樹 cppds §5.7 · 講義補充

Sierpinski 三角形：一次生三個自己 cppds §5.8 · 講義補充

河內塔：三行遞迴解千年謎題 cppds §5.10

迷宮探索：遞迴回溯（backtracking） cppds §5.11

找零錢：從貪婪、天真遞迴，一路走到 DP cppds §5.12 · 講義補充

動手驗證 cppds §5 綜合

本章遞迴問題一覽 cppds §5 總覽