Mdr-C-Tutorial

6.3 递归 ​

递归函数在执行过程中直接或间接调用自身。递归必须同时具备终止条件和使问题趋近终止条件的递归步骤。

1. 最小示例 ​

c
unsigned long long factorial(unsigned int n) {
    if (n < 2) {
        return 1;
    }
    return n * factorial(n - 1);
}

n < 2 是终止条件；factorial(n - 1) 让下一次调用处理更小的问题。

2. 调用栈 ​

每次尚未返回的调用都要保存自己的形参、局部对象和返回位置。递归层数过深会耗尽实现提供的调用栈空间，C 标准不保证能够完成任意深度的递归。

3. 递归与循环 ​

能用递归表达的问题通常也能通过显式状态和循环表达。递归适合描述天然嵌套的结构；循环不需要为每一层调用保存状态，存储开销更容易控制。

4. 习题 ​

4.1 巩固 ​

#10615
⚡1⏳2

下面的函数在递归调用前后各打印一次，用来观察每一层调用何时返回。

c
#include <stdio.h>

void trace(int n) {
    if (n == 0) {
        return;
    }
    printf("%d ", n);
    trace(n - 1);
    printf("%d ", n);
}

int main(void) {
    trace(3);
    putchar('\n');
    return 0;
}
  1. 先写出 trace(3) 的完整输出，再编译运行核对。输出里每个数字各出现几次？前半段和后半段的顺序为什么相反？
  2. 把终止条件改成 if (n == 1) { return; }，重新运行。输出变成什么？trace 被调用的总次数从几次变成几次？
  3. 再写一个只在递归调用之前打印的版本，输出是什么？把打印放到递归调用之后，输出又是什么？用这三种顺序说明「递归调用之前的代码在下降阶段执行，之后的代码在返回阶段执行」。

验收：第 1 步输出 3 2 1 1 2 3，共 4 次调用；第 2 步输出 3 2 2 3，共 3 次调用。

#10616
⚡2⏳3

把三个循环题改成递归实现，再各写一个循环版本对照。

  1. 求 1+2+⋯+n：

    c
    unsigned long long sum_to(unsigned int n);

  2. 求十进制各位数字之和，例如 12345 得 15：

    c
    unsigned int digit_sum(unsigned long long n);

  3. 按二进制输出，高位在前，不带前导零，0 输出 0。只用 putchar 输出字符，不得使用 printf 的 %b 一类扩展：

    c
    void print_binary(unsigned int n);

要求：

  1. 每个递归函数都要有终止条件和使问题变小的递归步骤，并在注释里各写一句说明。
  2. 每个函数再写一个循环版本，函数名加 _iter 后缀。
  3. 在 main 里对同一组输入调用两个版本，逐个比较结果：sum_to 用 n = 0, 1, 10, 10000；digit_sum 用 0、12345、999999999999；print_binary 用 0、1、6、255、1024。不要用更大的 n 测递归版本，栈深度的问题留到 10618。
  4. 输出格式自定，但要能看出两版结果一致。用 gcc -std=c17 -Wall -Wextra 构建，要求没有警告。

验收：sum_to(10) 为 55，sum_to(10000) 为 50005000；digit_sum 三个结果依次为 0、15、108；print_binary 依次输出 0、1、110、11111111、10000000000。第 3 问的循环版本可以用一位掩码从最高位往下扫，也可以把结果先存进一个字符数组。

4.2 编程 ​

#10617
⚡4⏳3

汉诺塔：三根柱子 A、B、C，n 个大小不同的圆盘按小在上、大在下叠在 A 上，要把整叠移到 C，每次只能移动一个盘，且大盘不能压在小盘上。

  1. 写递归函数，按顺序打印每一步：

    c
    void hanoi(int n, char from, char aux, char to);

    每行格式为 序号: 起点 -> 终点，序号从 1 开始，例如 1: A -> C。n == 0 时什么都不做。

  2. 用 hanoi(3, 'A', 'B', 'C') 验证。要求的输出（共 7 行）：

    text
    1: A -> C
2: A -> B
3: C -> B
4: A -> C
5: B -> A
6: B -> C
7: A -> C

  3. 用一个文件作用域的计数器统计总步数，对 n = 1 到 10 各跑一次，输出 n 与步数。观察步数与 n 的关系，并说明递归调用 hanoi(n - 1, ...) 两次与步数增长的关系。

  4. 再统计 hanoi 本身被调用的次数（包括 n == 0 的那次调用），对 n = 1 到 5 输出。比较「步数」与「调用次数」，说明为什么调用次数比步数多一倍左右。

  5. 把递归换成显式栈或循环能否更简单？写出你的判断。提示：先把 n 层的分解过程画成三层调用树。

验收：第 3 步步数为 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023；第 4 步调用次数为 3, 7, 15, 31, 63。

4.3 综合与挑战 ​

#10618
⚡5⏳4选做

下面这个递归求和函数在输入较大时会耗尽调用栈。

c
#include <stdio.h>

unsigned long long sum_to(unsigned int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main(void) {
    unsigned int n;
    if (scanf("%u", &n) != 1) {
        return 2;
    }
    printf("%llu\n", sum_to(n));
    return 0;
}

  1. 编译构建，依次输入 10000、50000、100000，记录每次的输出与退出状态（bash 用 echo $?，PowerShell 用 $LASTEXITCODE）。失败时的状态在本机不是 1 这样的普通返回值：Windows 上是 0xC00000FD，即栈溢出，bash 把它截成 127。记录你实测到的数字。

  2. 每层调用至少要保存返回位置和形参，返回地址与寄存器保存区合起来构成一个栈帧。用二分法在 10000 与 50000 之间找出本机能完成的最大 n 的量级，并说明这个阈值由什么决定、为什么换一台机器就可能不同。不必精确到个位。

  3. 把函数改写成带累加器的形式：

    c
    unsigned long long sum_acc(unsigned int n, unsigned long long acc);

    递归调用位于函数的最后一步。输入 100000，结果如何？换一种编译器或编译选项再试一次，结果可能不同吗？C 标准是否保证编译器一定会把这种尾调用改写成循环？相关背景见番外 5：尾调用与尾递归。

  4. 用循环重写一次，保留原来的 main，输入 1000000。记录结果与耗时。这个版本还需要为每一层保存状态吗？

  5. 另一类递归的代价不在栈深度，而在重复计算。写一个直接按定义展开的 fib，用一个文件作用域的计数器统计调用次数，对 n = 10、20、30 输出结果与调用次数，n 不必再往上加，调用次数按指数增长。

  6. 用第 4 步的循环写法计算同一个数列，比较两版在 n = 30 时的工作量与结果。结合第 7 章要学的数组和以后要学的缓存，说明在什么情况下递归是合适的，什么情况下应当直接写循环。

验收：第 1 步 10000 正常结束，50000 与 100000 崩溃；第 5 步 fib(10) 为 55、调用 177 次，fib(20) 为 6765、调用 21891 次，fib(30) 为 832040、调用 2692537 次；循环版本三个结果相同。第 3 步即使换成可能完成尾调用改写的实现，也必须说明这件事不在标准保证之内。