理解递归 | 山岳库博

函数的调用

现在我们假定一个场景：老师在给学生讲课，不妨设老师是主函数，学生为其它函数。现在老师要点名提问一个问题，可能会说：“探姬，5的阶乘等于几？”，那么这个老师就是调用了一个名字为“探姬”的函数，并输入了对应的参数，而探姬的回答则是函数的返回值。

递归

思想

递归是一种编程技巧，也是一种编程思想。递归其实就是函数的自调用，现在，探姬需要解决5的阶乘问题。探姬决定先计算4的阶乘，然后乘以5就是5的阶乘了。于是探姬开始询问自己的真心，4的阶乘是多少？同样，她选择先计算3的阶乘，一直往复，直到需要计算1（或2）的阶乘时不在继续往下，因为1（或2）的阶乘是它本身。这个自己询问自己（函数调用自身）的编码方式便称为递归。

这个求阶乘的方法写成代码就是：

int factorial(int n) {
    if (n == 1 || n == 2) return n;
    return factorial(n - 1) * n;
}

独立性

需要注意的是，函数调用自身之后，所有的变量（除了static变量）都不会与调用函数中的相影响，比如下面的代码：

void task(int k);

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

void task(int k) {
    int n = k * 2;
    task(n);
    printf("%d\n", n);
}

//结果：
// 40
// 20
//

我们尚且不讨论无限递归的问题，在这个代码中task(int)调用了自身，但是被调用的task(int)中的int n = k * 2这个语句并不会影响上层task(int)中的变量n的值，同时两者的k值也是相互独立的。

递归的优劣

优势

代码简洁易懂
逻辑简单，容易书写

劣势

时间和空间的消耗比循环大
可能存在部分重复运算
有调用栈溢出的风险

无限递归

上文我们提到了“无限递归”一词，这个词用于指明一个递归函数因某些原因导致递归没有尽头（另类的死循环），会永远执行下去。但是实际上并不会永远执行，为了解释这个问题，我们需要知道“函数的调用链”和“栈”的部分概念。

函数调用链

顾名思义，函数调用链就是函数调用过程中构建出来的一个链表（实际上可能不是，C/C++的内存我没有专门看过，如果有问题还望指正）。程序开始执行的时候，表头为main()，当main调用另一个函数的时候（比如说task(int)），就会在链表头添加一个元素task(int)（注意是添加而不是替换掉原本的表头）。如果task也调用了其它函数，则继续该操作。如果task执行完毕，则将task从表头移除，并返回到调用处继续执行剩下的代码。

调用栈

调用栈是用来存储调用链的栈，容量是有限的。

调用栈溢出

我们现在回过头来看上面的代码，假设栈最大存储的调用链长度为5，那么就是下面的情况：

调用演示

很显然，在运行4次task后栈便没有更多的空间来存储下一个需要存入的task，这时候就会导致程序崩溃，我们称为“调用栈溢出”。可以看出，就算task不是无限运行，只要递归次数够多，也有可能导致溢出，所以在设计递归算法时必须要控制递归的深度，以防溢出。同样，就算不是递归，调用函数的时候也可能会导致溢出，不过索性的是栈可存储的调用链实际上很长，不涉及递归很难遇到因为调用链过长导致的溢出问题。