递归

概述

递归(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