递归（recursion）指的是：一个函数在自己的函数体里调用了自己。递归能写出非常简洁、读起来很顺的代码，但要是没写好，也会把内存吃光。

什么时候会用到递归

现实中递归最常见的舞台：

  • 遍历递归型的数据结构，链表、二叉树这类由自己组成自己的玩意儿。
  • 游戏里探索所有可能走法（比如棋类）时自然形成树形递归。

递归的两个部分

任何能正确结束的递归，都必然由两块拼成：

  • 终止条件（terminating case），递归停下来、直接返回的出口。
  • 递归调用（recursive step），调用自己，且必须朝着终止条件推进。

缺了终止条件，或者递归不朝终止条件走，就会无限套娃，直到把栈耗尽崩溃。

例子：用递归实现乘法

下面这个函数用"递归地把 y 累加 x 次"实现乘法，先看这个递归示例：

#include <stdio.h>

unsigned int multiply(unsigned int x, unsigned int y) {
    if (x == 1) {
        /* 终止条件：x 已经减到 1，直接返回 y */
        return y;
    } else if (x > 1) {
        /* 递归步：y + 再把 x-1 和 y 相乘 */
        return y + multiply(x - 1, y);
    }
    /* 兜住 x 为 0 的情况 */
    return 0;
}

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

脑内推演一遍 multiply(3, 5)：

multiply(3, 5)
= 5 + multiply(2, 5)
= 5 + (5 + multiply(1, 5))
= 5 + (5 + 5)          ← 触到终止条件 multiply(1,5)=5
= 15

注意每一步的 x - 1，它在朝终止条件 x == 1 一步步接近。要是写成 multiply(x, y) 就永远刹不住车了。

经典练习：递归求阶乘

阶乘定义为 n! = n × (n-1) × … × 2 × 1，规定 0! = 1。用递归写特别顺手：

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

/* 声明 */
unsigned int factorial(unsigned int n);

int main() {
    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);   /* 递归步：n! = n × (n-1)! */
}

输出：

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

每一步都在计算 n × factorial(n-1)，让问题规模小一号，直到 n <= 1 上岸。

递归的代价：栈会变深

递归优雅，但有代价，每次调用都占一个栈帧。层数较深时内存疯涨，极端情况下直接把栈耗光（栈溢出）。和循环相比：

  • 能干一样的事，代码通常更短、更好读（尤其对树、链表这类结构）。
  • 但效率常不如循环，且深度有上限。能用迭代就迭代，遇到天然递归结构再用递归。

判断递归是否写对，就问自己三个问题：终止条件在哪？递归调用朝不朝终止条件走？每一步问题规模有没有变小？