递归

第 10 课，共 30 课 · 第 2 部分 · 函数和数组 · 约 15 分钟

函数可以调用别的函数，也可以调用它自己，这叫递归。一个问题里面要是藏着一个更小的同样的问题，用递归来解就很自然。比如从 3 开始倒数，就是「说 3，再从 2 开始倒数」：

main.c

1#include <stdio.h>2 3void countdown(int n) {4    if (n == 0) {5        printf("出发！\n");6        return;7    }8    printf("%d\n", n);9    countdown(n - 1);10}11 12int main(void) {13    countdown(3);14    return 0;15}

输出

3
2
1
出发！

每个递归函数都有两部分：

部分	做什么	在 `countdown` 里
终止条件	简单到可以直接做完，不再调用自己	`n == 0`：显示「出发！」，返回
递归的一步	做一点事，再拿一个更小的问题调用自己	显示 `n`，再 `countdown(n - 1)`

每调用一次，n 就小 1，早晚会到 0，调用就停下来了。

阶乘

5 的阶乘写作 5!，是 5 × 4 × 3 × 2 × 1 = 120。换个角度看：5! 是 5 × 4!，4! 是 4 × 3!……一直到 1! 就是 1。照着这句话写，就是一个递归函数：

main.c

1#include <stdio.h>2 3int factorial(int n) {4    if (n <= 1) {5        return 1;6    }7    return n * factorial(n - 1);8}9 10int main(void) {11    printf("%d\n", factorial(4));12    printf("%d\n", factorial(5));13    return 0;14}

输出

24
120

factorial(4) 不能马上算完：它要等 factorial(3)，factorial(3) 等 factorial(2)，factorial(2) 等 factorial(1)。factorial(1) 返回 1 以后，等着的几层再倒着一层一层算完：2 × 1、3 × 2、4 × 6。

小技巧： 点单步看看。每调用一次，内存里就多一个栈帧，摞在上一个上面，每个栈帧里都有自己的 n。到 n 是 1 时摞得最高，然后每 return 一次，最上面的栈帧就拿掉一个，把值交给下面那一层。

一层一层叠起来

想在输出里也看清这些层，可以给函数多加一个参数 depth，记住现在是第几层，显示的时候按层数缩进：

main.c

1#include <stdio.h>2 3void indent(int depth) {4    for (int i = 0; i < depth; i++) {5        printf("    ");6    }7}8 9int factorial(int n, int depth) {10    indent(depth);11    printf("factorial(%d)\n", n);12    if (n <= 1) {13        indent(depth);14        printf("返回 1\n");15        return 1;16    }17    int result = n * factorial(n - 1, depth + 1);18    indent(depth);19    printf("返回 %d\n", result);20    return result;21}22 23int main(void) {24    factorial(3, 0);25    return 0;26}

输出

factorial(3)
    factorial(2)
        factorial(1)
        返回 1
    返回 2
返回 6

往右缩进的是还在等的调用；最里面的 factorial(1) 先返回，外面的再一层层返回。没结束的调用像一摞盘子：新的调用放在最上面，return 时从最上面拿走。所以内存里放这些栈帧的地方叫栈。

先调用，再显示

递归调用前后都能做事。做在调用之前的，一层层往里走的时候就做了；做在调用之后的，要等里面的调用都返回了才做：

先猜一猜

这段程序显示什么？

1#include <stdio.h>2 3void show(int n) {4    if (n == 0) {5        return;6    }7    show(n - 1);8    printf("%d\n", n);9}10 11int main(void) {12    show(3);13    return 0;14}

show(3) 先调用 show(2)，还没显示；show(2) 先调用 show(1)；show(1) 先调用 show(0)，show(0) 直接返回。这时 show(1) 才显示 1，返回后 show(2) 显示 2，最后 show(3) 显示 3。

输出

斐波那契数列

斐波那契数列是 0、1、1、2、3、5、8、13……从第三个开始，每个数是前两个数的和。第 n 个是第 n - 1 个加第 n - 2 个，这里有两个更小的问题，所以函数调用自己两次：

main.c

1#include <stdio.h>2 3int fib(int n) {4    if (n < 2) {5        return n;6    }7    return fib(n - 1) + fib(n - 2);8}9 10int main(void) {11    for (int i = 0; i <= 10; i++) {12        printf("%d ", fib(i));13    }14    printf("\n");15    return 0;16}

输出

0 1 1 2 3 5 8 13 21 34 55

写起来很短，算起来却很慢：fib(5) 要算 fib(4) 和 fib(3)，fib(4) 里又要算一次 fib(3)……同样的数被算了一遍又一遍。用一个全局变量（上一课讲过）数一数调用了多少次：

main.c

1#include <stdio.h>2 3int calls = 0;4 5int fib(int n) {6    calls++;7    if (n < 2) {8        return n;9    }10    return fib(n - 1) + fib(n - 2);11}12 13int main(void) {14    int a = fib(10);15    printf("fib(10) = %d，调用了 %d 次\n", a, calls);16    calls = 0;17    int b = fib(20);18    printf("fib(20) = %d，调用了 %d 次\n", b, calls);19    return 0;20}

输出

fib(10) = 55，调用了 177 次
fib(20) = 6765，调用了 21891 次

n 每大 1，调用次数差不多变成 1.6 倍。fib(40) 要调用三亿多次。

忘了终止条件

没有终止条件，或者终止条件永远到不了，函数就会一直调用自己，栈帧越摞越高。真正的程序里，栈的空间用完，程序就崩溃了（常说「栈溢出」）。在这里不会真的崩溃：页面停在出事的那一行，告诉你栈用完了：

main.c

1#include <stdio.h>2 3int sum_to(int n) {4    return n + sum_to(n - 1);5}6 7int main(void) {8    printf("%d\n", sum_to(5));9    return 0;10}

输出

stack overflow

发生了什么： 停在第 4 行：递归太深了（或者局部数组太大），栈（8 MB）用完了。

sum_to 忘了在 n 是 0 时停下，n 一直减下去：5、4、3……0、-1、-2，永远停不下来。点单步，能看到栈帧一个接一个地往上摞。补上 if (n == 0) { return 0; } 就好了。

小技巧： 写递归函数，先写终止条件，再写递归的一步，并确认每一步都离终止条件更近了。

递归还是循环

能用递归写的，常常也能用循环写。下面两个函数都求一个数各位数字的和：

main.c

1#include <stdio.h>2 3int digit_sum(int n) {4    if (n < 10) {5        return n;6    }7    return n % 10 + digit_sum(n / 10);8}9 10int digit_sum_loop(int n) {11    int sum = 0;12    while (n > 0) {13        sum += n % 10;14        n /= 10;15    }16    return sum;17}18 19int main(void) {20    printf("%d %d\n", digit_sum(2048), digit_sum_loop(2048));21    return 0;22}

输出

14 14

在 C 里，简单的「数一数、加一加」用循环更直接，也更快，不用为每一层都建一个栈帧。问题本身一层套一层的时候（比如以后会见到的树、文件夹里套文件夹），递归写出来短得多，也清楚得多。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

从 1 加到 n

用递归写 sum_to：返回 1 + 2 + … + n。n 是 0 时返回 0。程序要显示 15 和 5050。

要显示

15
5050

exercise1.c

1#include <stdio.h>2 3int sum_to(int n) {4 5}6 7int main(void) {8    printf("%d\n", sum_to(5));9    printf("%d\n", sum_to(100));10    return 0;11}

输出

点「运行」或按 Ctrl+Enter

练习 2

乘方

用递归写 power(base, exp)：返回 base 的 exp 次方。任何数的 0 次方都是 1。程序要显示 1024 和 81。

要显示

1024
81

exercise2.c

1#include <stdio.h>2 3int power(int base, int exp) {4 5}6 7int main(void) {8    printf("%d\n", power(2, 10));9    printf("%d\n", power(3, 4));10    return 0;11}

输出

点「运行」或按 Ctrl+Enter

练习 3

几位数

count_digits 想数出一个正整数有几位，可它停不下来。补上终止条件，让程序显示 4 和 1。

要显示

4
1

exercise3.c

1#include <stdio.h>2 3int count_digits(int n) {4    return 1 + count_digits(n / 10);5}6 7int main(void) {8    printf("%d\n", count_digits(2048));9    printf("%d\n", count_digits(7));10    return 0;11}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

递归就是函数调用自己；它要有终止条件和更小的递归的一步。
每次调用都有自己的栈帧和自己的变量；调用一层层摞起来，return 时一层层退回去。
写在递归调用后面的语句，要等里面的调用都返回了才跑。
斐波那契这样一次调用两次自己的递归，同样的数会算很多遍，很慢。
没有终止条件，递归停不下来，栈会用完。
简单的累加和计数用循环；问题一层套一层时，递归更清楚。