遞迴 (Recursion),是指 一個函式 (或操作、方法、數列、演算法),
會 直接 或 間接 地 呼叫自己本身。
也就是:
使用相同的方法,解決重複性的問題 (Recurrent Problems)。
不同於 非遞迴的 (Non-Recursive) 做法,
[e.g., 使用 迴圈 (loop)、判斷式 (decision)、賦值/指派 (assignment) ]
遞迴 (Recursive) 往往可用簡單、優雅的方式解決複雜的問題。
目錄
範例 —— int 陣列加總
int a[] = {15, 37, 26, 9}; // 欲計算的陣列
將陣列元素加總,直覺可能是:
以 迴圈尋訪 並且加總
int sum(int[] a, int n) {
int result = 0; // 欲傳回之結果
if (n < 1)
throw new IllegalArgumentException("n should be >= 1");
else {
for (int i = 0; i < n; i++) // 用 for 迴圈 尋訪陣列
result = result + a[i]; // 將陣列值一一加總
}
return result; // 回傳結果
}
直接線性式遞迴 int 陣列加總
若換成 遞迴 的思維方式:
將具有 相同性質 的問題,拆成 多個 子問題。
程式範例如下:
int sum(int[] a, int n) {
if (n < 1) // 陣列索引數不得小於 1
throw new IllegalArgumentException("n should be >= 1");
else if (n == 1) // 陣列索引數等於 1,返回陣列的 第 "1" 個元素
return a[0];
else // 否則,將問題拆解成 sum(a, n - 1) + a[n - 1]
return sum(a, n - 1) + a[n - 1];
}
計算 四個數的總和,
可以拆成是 sum(a, 3) + a[3]
(三個數的總和 + a[3])。
計算 三個數的總和,
可以拆成是 sum(a, 2) + a[2]
(兩個數的總和 + a[2])。
計算 兩個數的總和,
則是拆成 sum(a, 1) + a[1]
(陣列首項 a[0] + a[1])。
相當於: a[0] + a[1] + a[2] + a[3] = 87!
種類 —— 依 呼叫方式
如開頭定義所述, 遞迴 有兩種呼叫方式:
- 直接遞迴 (direct recursion)
- 間接遞迴 (indirect recursion)
直接遞迴 (direct recursion)
指的是 函式 呼叫自己本身。
圖示:
間接遞迴 (indirect recursion)
指的是 函式引用 其他函式,其再 呼叫原函示。
由於形成了 calling cycle,使用上需格外小心。
圖示:
種類 —— 依 呼叫次數
分為
- 線性遞迴 (linear recursion)
- 二元遞迴 (binary recursion)
- 多元遞迴 (multiple recursion)
線性遞迴 (linear recursion)
當函示,只呼叫一次遞迴,稱之,
最簡單的遞迴形式。
圖示:
二元遞迴 (binary recursion)
當函式,呼叫兩次遞迴,稱之。
圖示:
想當然爾,多元遞迴 (multiple recursion),就是呼叫 兩次以上囉!
種類 —— 尾端遞迴 (tail recursion)
這是實務上一種重要的遞迴種類,指的是具備:
- 直接遞迴 (direct recursion)
- 線性遞迴 (linear recursion)
- 且該 函式執行的最後一件事 為遞迴呼叫,且 只能是遞迴呼叫
其中,第三點尤其重要:
最後執行的內容,一定要豪乾淨的,
只有呼叫遞迴,不能做其他事!
譬如 上方的 陣列加總範例 ,
即使最後的敘述包含了一個遞迴呼叫,它還必須與 a[n-1] 加總,
也就是說,他最後執行的是 加法,而非遞迴。
他是 直接線性式遞迴,但是 並非 尾端遞迴!
尾端遞迴之重要性
那麼,尾端遞迴 跟 其他遞迴 到底有什麼差異呢?
函式呼叫
首先得知道函式呼叫的簡易流程:
執行 Function A( ) 時,若需呼叫 Function B( ),
這時得
- 程式會建立一個 被稱為 活動紀錄 (activation record) 或 堆疊框 (stack frame) 的結構,
保存 Function A ( ) 目前的執行狀態,並將其資訊 push 到 系統堆疊 (System Stack) 頂端,
包含 參數、區域變數、返回位置 (return address)。 - 控制權轉移,且做參數傳遞 (譬如 上圖的 x 與 y)。
- 執行 Function B( ) 。
- Function B( ) 執行完成,做判斷:
if (Stack != empty) {
pop stack; // 取出參數、區域變數、返回位置 (return address)
依 返回位置 返回 並執行;
}
因此,遞迴的每次呼叫:
需要額外的記憶體 (系統堆疊),來記錄每個遞迴的呼叫狀態!
需要額外的記憶體 (系統堆疊),來記錄每個遞迴的呼叫狀態!
需要額外的記憶體 (系統堆疊),來記錄每個遞迴的呼叫狀態!
—– 覺得很重要 o.o
若遞迴呼叫過量使堆疊爆了,就會造成 Stack Overflow Error 。
這時,若去網路搜尋 尾端遞迴 (tail recursion),你就知道它為何重要了。
大部分都會告訴你:
尾端遞迴,不增加 新的系統堆疊,
而是用每次執行的結果,直接更新函示內容,這樣的做法稱為:
尾端呼叫消除 (Tail Call Elimination, TCE) 或 尾端呼叫最佳化 (Tail Call Optimization, TCO)。
殘念… 我要告訴你… 這不完全是真的!
許多語言編譯器 並 不(想)支援 尾端呼叫最佳化 ! (ex: Java、Python)
曾有人拿 維X百科 的範例:『他明明就拿 python 示範 尾端遞迴 !?』
我想他是沒把範例看完 😂 詳請點這。
遞迴/迭代轉換
儘管許多語言,並不支援 尾端呼叫優化,
尾端遞迴 還是很重要的!
這裡用個著名的例子「小於 n 的自然數總和」:
1 + 2 + 3 + 4 + 5 + ... + (n-1) + n
使用 迭代
int sum(int n) {
int result = 0;
for (int i = 1; i <= n; i++)
result = result + i;
return result;
}
邏輯相當簡單,設一個區域變數 result 來儲存累計總和,
並透過迴圈尋訪,由 1 + 2 + 3 慢慢加到 n 。
使用 遞迴 (線性 非尾端)
int sum(int n) {
if (n < 0)
throw new IllegalArgumentException("n should be >= 0");
else if (n == 0)
return 0;
else
return sum(n - 1) + n;
}
傳入 sum(100) 想計算 1 + 2 + 3 + … + 99 + 100 的值,
則會被拆成 sum(99) + 100;sum(99) 再被拆成 sum(98) + 99 …,
原理跟 陣列加總範例 一模一樣。
使用 遞迴 (尾端)
若以 尾端遞迴 改寫:
public int sum(int n, int total) {
if (n == 0)
return total;
else
return sum(n - 1, total + n);
}
n 是 想要加總的數, total 就像是 上方非遞迴中的 區域變數一樣 (初始值 = 0),用來儲存累計總和,
因此 想要累計 1 + 2 + 3 + … + 9 + 10 的話,就呼叫 sum(10, 0); 。
sum(10, 0) 問題會依序被分解為:
sum(9, 10);
sum(8, 19);
sum(7, 27);
…
最後 return 55;
可以發現:
sum(n - 1, total + n);
n – 1,不就是每次 迴圈 的 變化量嗎?
total + n 不就是 區域變數 的 累加 ?
尾端遞迴其實只是把:
迭代的 迴圈變化 與 區域變數,放在方法的參數中傳遞 罷了。
要改寫成 非遞迴 就是 piece of a cake 了 🍰。
一個函式,理論上必定存在兩種形式解法: 遞迴 與 非遞迴。
而 尾端遞迴 則能 無痛轉換 為非遞迴!
但千萬別忘記…最佳解是小學生都會的:
「上底加下底乘以高除以二」,勿捨本著墨 !
遞迴 vs. 非遞迴
既然一個函式,存在者兩種形式解法,那就得知道何時該使用誰啦。
儘管上方表格,似乎顯得遞迴一文不值,
若能保證函式有 較佳的收斂程度 且 效能良好,
還是很推薦使用的 (像我這懶人就很愛用 😂)。
另外,以上的情況僅適用於相同邏輯之演算法,
若 遞迴用得好效能可不輸給迭代 !接下來就來看個遞迴優化的範例吧。
遞迴 經典範例 —— (I)
費式數列 (Fibonacci Number)
Def:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n >= 2)
F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15 | F16 | F17 | F18 | F19 | F20 |
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 | 6765 |
使用 遞迴 (二元 非尾端)
時間複雜度 — O(2n):
int fib(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n - 1) + fib(n - 2);
}
由於 費氏數列 本身即由遞迴定義,寫成遞迴相當容易!
然而,此種二元遞迴產生了許多冗余計算,耗時又耗 Stack 空間:
使用 迭代
使用 非遞迴,時間複雜度 — O(n):
int fib(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else {
// a: F(n-2)
// b: F(n-1)
int a = 0, b = 1, result = 0;
for (int i = 2; i <= n; i++) {
result = a + b;
a = b;
b = result;
}
return result;
}
}
相比基本遞迴函式效率提升許多!
然而,這 不代表遞迴比迭代差,大多時候可能是遞迴 用得不夠好!
使用 遞迴 (尾端)
尾端遞迴 一節提及過,它能無痛轉換為非遞迴,
既然如此,我們如法炮製地將 非遞迴 改寫為 尾端遞迴,時間複雜度 — O(n)!
public int fib(int n) {
return fib(n, 0, 1);
}
private int fib(int n, int a, int b) {
if (n == 0) return a;
return fib(n - 1, b, a + b);
}
其實只是:
把迭代的 迴圈變化 與 區域變數,放在參數中傳遞罷了。
使用 迭代 (Fast Doubling)
透過 Q-Matrix,還能進一步將費氏數列轉移成矩陣乘法問題:
乘入後便可以導出兩個方便的公式:
F(2n) = F(n) [2F(n + 1) − F(n)]
F(2n + 1) = F(n + 1)2 + F(n)2
藉由快速冪的技巧即可得:
int fib(int n) {
int a = 0; // F(k)
int b = 1; // F(k + 1)
for (int bit = Integer.highestOneBit(n); bit != 0; bit >>>= 1) {
// Double it
int c = a * ((b << 1) - (a)); // F(2k)
int d = (a * a) + (b * b); // F(2k + 1)
if ((n & bit) != 0) {
int e = c + d; // F(2k + 2)
a = d; // k = 2k + 1
b = e;
} else {
a = c; // k = 2k
b = d;
}
}
// current k == n
return a;
}
時間複雜度 — O(log n)!
使用 遞迴 (尾端 + Fast Doubling)
有了前幾節的經驗,相信您已能輕鬆轉換迭代為 尾端遞迴 了!
public int fib(int n) {
return fib(n, 0, 1, Integer.highestOneBit(n));
}
/*
* k start with 0
* @param a -- F(k)
* @param b -- F(k + 1)
*/
private int fib(int n, int a, int b, int bit) {
if (bit == 0) return a;
// F(2k) = F(k) * [2 * F(k + 1) - F(k)]
int c = a * ((b << 1) - (a));
// F(2k + 1) = F(k)^2 + F(k + 1)^2
int d = (a * a) + (b * b);
if ((n & bit) != 0) {
int e = c + d; // F(2k + 2)
a = d; // k = 2k + 1
b = e;
} else {
a = c; // k = 2k
b = d;
}
bit >>>= 1;
return fib(n, a, b, bit);
}
誰說費式遞迴很慢? — 時間複雜度 O(log n)!
遞迴 經典範例 —— (II)
河內塔 (Hanoi Tower)
Def:
有 塔A、塔B、塔C,塔A 放著 n 個盤子,
欲將 n 個 盤子 (disks),由 塔 A 搬移到 塔C。
且必須遵守:
- 一次只能搬移一個 disk
- 搬移過程中,小盤不可在大盤之下
圖示:
解法邏輯 (尋找中繼塔):
- 先將 塔A 上面的 n-1 個 盤子,移動到塔B (中繼為 c)
- 將最大的盤子,搬至目的地 塔C
- 將 塔B 剩下的盤子,搬移至目的地 塔C (中繼為 a)
大概是這樣的感覺:
Q: 『尛,不對啊,第二第三點聽起來很有道理,
可是 要怎麼把 n-1 個盤子,移動到中繼站??』
答案是:
- 先將 塔A 上面的 n-2 個 盤子,移動到塔B (中繼為 c)
- 將最大的盤子,搬至目的地 塔C
- 將 塔B 剩下的盤子,搬移至目的地 塔C (中繼為 a)
聽起來,又好像在講廢話…
不過,這就是寫遞迴的訣竅 — 拆解問題。
範例:
/**
* 計算河內塔
*
* @param n 搬移的盤子數目
* @param a 來源地 (source)
* @param b 中繼站 (bridge)
* @param c 目的地 (destination)
* @return
*/
void hanoi(int n, String a, String b, String c) {
if (n == 1) { // 只有一個盤子
System.out.println("將盤子從" + a + " 搬到" + c);
} else {
hanoi(n - 1, a, c, b); // 先搬 n-1 個盤子 到 b (將 c 當中繼)
hanoi(1, a, b, c); // 將剩下的一個盤子 由 a 搬到 c
hanoi(n - 1, b, a, c); // 將剛剛 塔b 的 n-1 個盤子 再由 b 搬到 c (a 當中繼)
}
}
接著,執行 hanoi(3, a, b, c) 將 3 個盤子,從 A 搬到 B!
Result: 將盤子從 塔A 搬到 塔C 將盤子從 塔A 搬到 塔B 將盤子從 塔C 搬到 塔B 將盤子從 塔A 搬到 塔C 將盤子從 塔B 搬到 塔A 將盤子從 塔B 搬到 塔C 將盤子從 塔A 搬到 塔C
當要搬動 n 個盤子時,總共要搬動 2n – 1 次,時間複雜度為 O(2n)
撰寫遞迴
簡單說就是,遇到問題就不斷地 拆解 成相同 子問題,
直到拆到不能拆為止,並定義 最簡情況 的做法。
千萬別忘了:
建立終止遞迴呼叫的 臨界/終止條件
例如,上述的河內塔問題,終止條件便是只有一個盤子時…,
二元樹的走訪、翻轉,則是 當樹為空。
(為大神 Max Howel 默哀 3 秒)
範例原始檔 在此
在《遞迴 (Recursion)》中有 8 則留言
間接遞迴標題那邊英文應該是indirect recursion. 寫得非常好!!
已修正!!
非常感謝 😭 世界就是需要您這種人
受益匪淺
感謝吳同學 😁
溫習Tail Recusion時搜尋到這篇,寫的真的很淺顯易懂,非常感謝!
謝謝您! 之後將再升級內容喔 😆
受用無窮