資結/演算法

遞迴 (Recursion)

遞迴 (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( ),
這時得

  1. 程式會建立一個 被稱為 活動紀錄 (activation record)堆疊框 (stack frame) 的結構,
    保存 Function A ( ) 目前的執行狀態,並將其資訊 push 到 系統堆疊 (System Stack) 頂端,
    包含 參數、區域變數、返回位置 (return address)
  2. 控制權轉移,且做參數傳遞 (譬如 上圖的 x 與 y)。
  3. 執行 Function B( ) 。
  4. 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: JavaPython)
 
曾有人拿 維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)

 

F0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16F17F18F19F20
011235813213455891442333776109871597258441816765

 
 

使用 遞迴 (二元 非尾端)

時間複雜度 — 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 空間:
fib(5)
 
 

使用 迭代

使用 非遞迴,時間複雜度 — 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,還能進一步將費氏數列轉移成矩陣乘法問題:
 
fib-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
  • 搬移過程中,小盤不可在大盤之下

 
圖示:

 
 

解法邏輯 (尋找中繼塔):

  1. 先將 塔A 上面的 n-1 個 盤子,移動到塔B (中繼為 c)
  2. 將最大的盤子,搬至目的地 塔C
  3. 將 塔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 則留言

  1. 溫習Tail Recusion時搜尋到這篇,寫的真的很淺顯易懂,非常感謝!

發表迴響