遞迴

概述

遞迴(Recursive)意思是在一個函數內呼叫自己這個函數

void f() {
    f();  // <- recursive
}

如上述所示，遞迴會不斷的走向更深處 $f() \to f'() \to f''() \to \dots$
需要寫一個判斷不再遞迴正常結束的條件

#include <iostream>
using namespace std;

void f(int n) {
    if (n == 0) {
        return;
    }
    cout << n;
    f(n - 1);
}

int main() {
    f(10);
    return 0;
}

這是一個印出10~1的範例，執行過程可以想像成這樣

f(10) -> 印出10 -> 呼叫f(9)
f(9) -> 印出9 -> 呼叫f(8) …
f(1) -> 印出1 -> 呼叫f(0)
f(0) 觸發 if (n == 0) 正常結束函式

或者想像成函數 show_10() 呼叫了另一個函數 show_9() 內容都相同只是數字變了

回程

上面只有遞迴的去程，理解了回程才能明白整個遞迴過程，在後續二元樹章節可能經常用到

如何只新增一行代碼將上述範例印成10到1到10呢？

概念解說

遞迴(recursive)並沒有特殊機制，單純只是函數呼叫自己的行為我們稱之為遞迴，然後藉由變數的改變執行相同的代碼但不同的動作，比如參數被遞減，至於普通的函數呼叫就像這樣

int main() {
    int n = 3;
    cout << n;
    func();
    cout << n;
}

這段代碼只做了

新增變數 n = 3 並印出3
呼叫func()
印出3

現在我們把函數名稱修改一下，這個和上面的差異只有名稱不同

1
void f_3() {
2
    int n = 3;
3
    cout << n;
4
    f_2();
5
    cout << n;
6
}

然後再新增一些完全相同的函數

9
void f_2() {
10
    int n = 2;
11
    cout << n;
12
    f_1();
13
    cout << n;
14
}
15
void f_1() {
16
    int n = 1;
17
    cout << n;
18
    exit();
19
    cout << n;
20
}
21
void exit() {
22
    cout << 0;
23
}

如果我們呼叫f_3()會發生什麼事呢？

程式碼從第2行開始執行，第2~4行，印出3，呼叫f_2()
第10~12行，印出2，呼叫f_1()
第16~18行，印出1，呼叫exit()
第22行，印出0，到結尾正常結束exit()

執行完呼叫exit()的第18行接著執行第19行
第19行，印出1，到結尾正常結束f_1()
執行完呼叫f_1()的第12行接著執行第13行
第13行，印出2，到結尾正常結束f_2()
執行完呼叫f_2()的第4行接著執行第5行
第5行，印出3，到結尾正常結束f_3()

輸出：3210123

實作

可以發現上面三個函數都是同樣的東西，唯一不同的只有cout使用的變數n，將n變成參數就可以改寫成一個函數

void f(int n) {
    cout << n;
    f(n - 1);
    cout << n;
}

在最後呼叫了exit()當 n == 0 的時候 cout << n 而不做原本的函數內容

void f(int n) {
    if(n == 0) {
        cout << n;
        return;
    }
    cout << n;
    f(n - 1);
    cout << n;
}

return 意思是返回，結束函數，就像迴圈搭配 break 一樣的概念

結論

在遞迴函數內部呼叫遞迴前做的內容就是該遞迴的去程，呼叫後做的就是該遞迴的回程

void f(int n) {
    /*
        f(n - 1)的去程
    */
    f(n - 1);
    /*
        f(n - 1)的回程
        可以同時是別的遞迴呼叫的去程
        e.g. f(n - 2)
    */
}

尾遞迴

沒有回程的遞迴可以被編譯器優化成跳躍敘述而不是呼叫函式，因為不用再回到原本的地方執行下一行，但有些情況實際上並不是尾遞迴，比如這兩種：

int f(int n) {
    if (n == 0) return 1;
    return n * f(n - 1);
}

這裡的 f(n - 1) 呼叫後還要回來與 n 相乘

int f(int n) {
    string s = "hello";
    if (n == 0) return 0;
    return f(n - 1);
}

這裡執行完 f(n - 1) 實際上還要回來解構 s

呼叫函數空間成本

遞迴若不是尾遞迴的特殊優化，會一直產生函數呼叫，每次函數呼叫都有一些空間成本，以下將說明如何預估空間大小

編譯時未啟用優化

g++ -O0 或未設定參數的情況大約是這樣

返回地址 8 bytes + 區域變數地址 8 bytes + 區域變數及任何臨時值的空間總和 + 超過五個參數的數量 $\times$ 8 bytes + 可能存在 8 bytes 對齊

說明：-O0 的情況gcc會把所有變數存入stack，並且運算中間產生的值可能也會保存，Windows第5個參數開始放入stack，Linux從第7個參數開始放入stack，最後stack頂部要與 16 bytes 對齊，每次放入 8 bytes 所以可能需要補 8 bytes

-O2

在編譯時使用 -O2（LeetCode、AtCoder），大約會產生這樣的空間成本

返回地址 8 bytes + 該函數內進行函數呼叫後最大同時還需要留存的變數數量 $\times$ 8 bytes + 可能存在 8 bytes 對齊

說明：-O2 會把區域變數放入暫存器操作，所以沒有區域變數成本，但若進行任何函數呼叫後還要用的話就需要用到stack