在掌握函数的定义与调用之后，可以学习递归（recursion）：在函数体内部再次调用自身的编程方式。递归适合把问题分解为规模更小的同类子问题，在树形结构、分治算法等场景中较为常见；若缺少正确的终止条件，可能导致无限调用并最终发生栈溢出。

递归的典型用途

下列情形常考虑使用递归（具体实现仍须结合问题规模与性能要求）：

  • 处理具有递归定义的数据结构，例如链表的遍历、树形结构的先序或后序访问（相关细节在指针与结构体章节展开）。
  • 在搜索、博弈等需要枚举多层选择的问题中，用递归表达各层决策往往较为直观。

终止条件与递归调用

能够正常结束的递归通常包含两部分：

  • 终止条件（base case）：不再继续调用自身，直接返回结果的分支。
  • 递归调用（recursive step）：调用自身处理规模更小的子问题，且每次调用都应向终止条件靠近。

若缺少终止条件，或递归调用未使问题规模缩小，调用将不断嵌套，直至耗尽栈空间。每次调用都会占用栈帧，机制与函数一节中的栈帧说明一致。

示例：用递归实现乘法

下列函数用“将 y 累加 x 次”的思路实现无符号整数乘法，用于观察终止条件与递归调用的配合（并非最高效的乘法实现）：

#include <stdio.h>

unsigned int multiply(unsigned int x, unsigned int y) {
    if (x == 1) {
        return y;   /* 终止条件：x 为 1 时结果为 y */
    } else if (x > 1) {
        return y + multiply(x - 1, y);   /* 递归：x 减 1，向 x == 1 靠近 */
    }
    return 0;       /* x 为 0 时结果为 0 */
}

int main(void) {
    printf("3 乘 5 等于 %u\n", multiply(3, 5));
    return 0;
}

对 multiply(3, 5) 的展开过程如下：

multiply(3, 5)
= 5 + multiply(2, 5)
= 5 + (5 + multiply(1, 5))
= 5 + (5 + 5)
= 15

每次递归使 x 减 1，直至满足 x == 1。若错误地写成 multiply(x, y) 而不减小 x，终止条件永远无法达到，将导致无限递归。

示例：递归求阶乘

阶乘定义为 n! = n × (n - 1) × … × 2 × 1，并规定 0! = 1。其递推关系 n! = n × (n - 1)! 适合用递归直接表达：

C 语言递归求阶乘示例运行
#include <stdio.h>

unsigned int factorial(unsigned int n);

int main(void) {
    printf("0! = %u\n", factorial(0));
    printf("1! = %u\n", factorial(1));
    printf("3! = %u\n", factorial(3));
    printf("5! = %u\n", factorial(5));
    return 0;
}

unsigned int factorial(unsigned int n) {
    if (n <= 1) {
        return 1;   /* 终止条件：0! 与 1! 均为 1 */
    }
    return n * factorial(n - 1);
}

输出：

0! = 1
1! = 1
3! = 6
5! = 120

每次调用将 n 减 1，直至 n <= 1 时返回 1，再逐层乘回得到结果。

递归的开销与迭代

递归写法往往结构清晰，但每次函数调用都需要栈空间保存返回地址与局部变量。递归深度较大时，总栈占用会明显增加，极端情况下发生栈溢出。与循环（迭代）相比，可概括如下：

  • 在树、链表等具有递归结构的问题上，递归代码通常更贴近问题定义，可读性较好。
  • 对同一问题，迭代实现常具有更小的栈开销或更好的时间、空间效率；在深度可预期且较大时，可优先考虑迭代或显式管理栈结构。

编写或阅读递归函数时，可依次确认：终止条件是否明确？递归调用是否使问题规模严格缩小？是否存在无法到达终止条件的路径？若三者均成立，递归在逻辑上才是完备的。

本节介绍了递归的基本形式、典型示例以及与栈空间、迭代的关系。后续学习指针与复杂数据结构时，还会遇到更多适合递归的场景。