遞迴 — Recursion Interactive（C++）

📌 本頁使用方式（cppds Ch.5｜講義 06）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 06 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻關鍵詞彙卡（7 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「講義補充」的節是課堂沒細講的延伸，第一輪可略過。

📑 講義 06 PDF 🖥 講義 06 HTML 📖 cppds 原文（Recursion）📘 Hello 演算法（迭代與遞迴）🏠 章節總覽

CONTENTS · 內容目錄

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

PROLOGUE · 開場

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

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

速度

虛擬碼 CODE

int listSumFrom(const vector<int>& a, size_t i) {
    if (i == a.size()) return 0; // 空尾段
    return a[i] + listSumFrom(a, i + 1);
}
int listSum(const vector<int>& a) {
    return listSumFrom(a, 0);
}

遞迴 vs 迴圈

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

PART 01 · 三法則

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

法則 1

必須有 base case
小到能直接回答的情況（listSum：索引到達尾端，空尾段總和為 0）。

法則 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) {
    string digits = "0123456789ABCDEF";
    if (n < base) {             // base case：一位數
        return string(1, digits[n]);
    }
    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.size() <= 1) {
        return s;             // 空字串或一個字元
    }
    return reverse(s.substr(1)) + s[0];
}                                // 「剩下的反轉」接上「第一個字」
 
assert(reverse("") == "");
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 容量有限，但上限取決於作業系統、執行環境與設定。 base case 寫錯 → frame 持續堆積 → 最終出錯。深度可能很大的線性遞迴通常應改寫成迴圈。

尾遞迴

若遞迴呼叫是函式的最後一步，編譯器可能做尾呼叫最佳化並重用 frame；C++ 標準不保證一定會做，因此程式正確性不能依賴它。

講義完整範例：用 stack 模擬遞迴、用 depth 看見遞迴

講義 06 · 遞迴拿掉、換成自己管理的 stack

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
string toStr(int n, int base) {
    stack<char> rStack;
    string convertString = "0123456789ABCDEF";
    while (n > 0) {
        rStack.push(convertString[n % base]);
        n = n / base;
    }
    string res = "";
    while (!rStack.empty()) {
        res = res + rStack.top();
        rStack.pop();
    }
    return res;
}
 
int main() { cout << toStr(1453, 16) << endl; }
 

預期輸出

5AD

這版沒有遞迴：自己開一個 stack 存餘數字元、最後倒出來。它證明了一件事：遞迴版其實是把同一個 stack 藏進了「呼叫堆疊」，每一層呼叫的區域變數就是一格 stack frame。

講義 06 · 印出深度，親眼看呼叫堆疊長高

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
 
int depth = 0;   // 明著追蹤遞迴深度

string toStr(int n, int base) {
    depth++;
    printf("  depth=%d, n=%d\n", depth, n);
    string convertString = "0123456789ABCDEF";
    if (n < base) {
        return string(1, convertString[n]);
    }
    return toStr(n / base, base) + convertString[n % base];
}
 
int main() {
    cout << toStr(10, 2) << endl;
    return 0;
}
 

預期輸出

  depth=1, n=10
  depth=2, n=5
  depth=3, n=2
  depth=4, n=1
1010

深度一路長到 4：n 每除一次 2 就多一層 frame。最深那層（n=1）先回傳「1」，然後一路「回程」把餘數黏在後面，1010 是回程時由左往右組出來的。

PART 04 · 視覺化

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

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

遞迴難學，常常是因為腦中缺一張圖。cppds 的 C++ 範例使用 CTurtle.hpp；這裡用 canvas 重現同一套遞迴視覺，不需要額外安裝圖形函式庫。

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

樹的深度

螺旋 CODE

void spiral(ct::Turtle& t, int len) {
    if (len > 0) {       // base case：長度歸零
        t.forward(len);
        t.right(90);
        spiral(t, len - 5);
    }}

碎形樹 CODE

void tree(int len, ct::Turtle& t) {
    if (len > 5) {
        t.forward(len); t.right(20);
        tree(len - 15, t);   // 右子樹
        t.left(40);         // 退掉 20 再左轉 20
        tree(len - 15, t);   // 左子樹
        t.right(20); t.backward(len);
    }}

碎形是什麼？

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

PART 05 · 三路遞迴

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

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

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

degree 3

三路遞迴 CODE

void sierpinski(ct::Point a, ct::Point b, ct::Point c, int degree, ct::Turtle& t) {
    const string colors[] = { "blue", "red", "green", "white",
                              "yellow", "violet", "orange" };
    drawTriangle(a, b, c, {colors[degree]}, t);
    if (degree > 0) {
        sierpinski(a, ct::middle(a,b), ct::middle(a,c), degree-1, t);
        sierpinski(b, ct::middle(a,b), ct::middle(b,c), degree-1, t);
        sierpinski(c, ct::middle(c,b), ct::middle(a,c), degree-1, t);
    }}

畫的順序

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

QUIZ · 數三角形

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

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

(B) 3 × 3 = 9 次

PART 06 · 河內塔

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

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

速度

虛擬碼 CODE

void moveTower(int height, string from, string to, string via) {
    if (height < 1) return;   // base case
    moveTower(height-1, from, via, to);  // ① 搬 n-1 個
    moveDisk(from, to);               // ② 搬最大盤
    moveTower(height-1, via, to, from);  // ③ 搬回 n-1 個
}

移動次數

3 盤7

5 盤31

n 盤2ⁿ − 1

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

講義 06 · moveTower 完整程式與 3 層塔的輸出

#include <iostream>
#include <string>
using namespace std;
 
void moveDisk(string fromP, string toP) {
    cout << "moving disk from " << fromP << " to " << toP << endl;
}
void moveTower(int height, string fromPole, string toPole, string withPole) {
    if (height >= 1) {
        moveTower(height - 1, fromPole, withPole, toPole);
        moveDisk(fromPole, toPole);
        moveTower(height - 1, withPole, toPole, fromPole);
    }
}
 
int main() { moveTower(3, "A", "B", "C"); }
 

預期輸出

moving disk from A to B
moving disk from A to C
moving disk from B to C
moving disk from A to B
moving disk from C to A
moving disk from C to B
moving disk from A to B

7 行輸出 = 2³ − 1 步，跟理論下限一模一樣。注意基底情況是「height < 1 什麼都不做」：它藏在 if 的反面，這種「隱形 base case」是遞迴的常見寫法。拿上面的互動動畫對照，每一行輸出對應一次圓盤移動。

PART 07 · 走迷宮

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

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

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

速度

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

虛擬碼 CODE

bool searchFrom(Maze& maze, int row, int col) {
    if (maze.get(row,col) == OBSTACLE) return false;
    if (maze.get(row,col) == TRIED || maze.get(row,col) == DEAD_END) return false;
    if (maze.isExit(row,col)) return true;
    maze.updatePosition(row,col,TRIED);
    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;
}

Maze 類別 CODE

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

searchFrom 的短路技巧

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

講義 06 · 迷宮主程式與輸出圖

#include <iostream>
#include "pythonds3/cppds/maze.hpp"   // Maze 類別 + searchFrom（上面的完整列表）
using namespace std;
 
int main() {
    Maze myMaze("maze2.txt");
    searchFrom(myMaze, myMaze.startRow, myMaze.startCol);
    myMaze.print();   // O = 成功路徑，- = 死路
    return 0;
}
 

實際輸出（依 maze2.txt）

++++++++++++++++++++++
+-OO+OOO++ ++        +
OOOOOO+OOO  ++++++++++
+-+-OO ++O ++++ +++ ++
+-+-OO+ +O++ OO +++  +
+---OO   OO++OO++  + +
+++++-+ +-OOOOO++  + +
+++++-+++--+-+OO++   +
+----------+-+ O+ +  +
+++++-+--+-+-+     + +
++++++++++++++++++++++

O 是最後成功的那條路，− 是「試過但退回」的死路格子：遞迴回溯的痕跡全印在圖上。四個方向的 || 短路串接讓「找到一條就收工」，找不到才會把整片區域踩成 −。

PART 08 · 動態規劃

找零錢：從貪婪、天真遞迴，一路走到 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）。貪婪法死在「當下最好」不等於「整體最好」。

為了比較計算量，cppds 接下來三個版本固定使用四種硬幣 {1,5,10,25}，目標為 63 分。 63 分的最少硬幣數，是「拿一枚 1 分之後 62 分的最少」「拿一枚 5 分之後 58 分的最少」…… 之中最小的那個加一。這個定義完全正確，卻慢得離譜：天真遞迴要 67,716,925 次呼叫，因為同樣的子問題（例如 15 分）被翻來覆去重算了幾十次。講義給了三帖藥，一帖比一帖徹底：

版本	策略	63 分的呼叫數
makeChange1	天真遞迴；coins={1,5,10,25}	67,716,925
makeChange2	memoization；同一組四硬幣	221（cppds 此版）
makeChange3	bottom-up DP；同一組四硬幣	至多 63 × 4 次硬幣檢查

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

速度

makeChange3（DP 本體）CODE

int dpMakeChange(const vector<int>& coins, int change) {
    vector<int> minCoins(change + 1, 0);
    for (int cents=1; cents<=change; ++cents) {
        int best = cents;          // 全用 1 分硬幣
        for (int 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(const vector<int>& coinsUsed, int 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,772 萬次呼叫；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	索引到 vector 尾端	索引加 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 CTurtle 圖）。

CARDS · 關鍵詞彙卡