递归算法：从概念到实战

递归，这个词我刚开始学的时候，觉得挺玄乎的。说白了，就是函数自己调用自己。嗯，就这么简单。但真正用好它，需要理解它的运行机制。

我在做嵌入式开发时，经常遇到树形结构的遍历、文件系统的目录扫描，这些场景用递归写起来特别顺手。但我也踩过不少坑——比如栈溢出，那真是让人头疼的问题。

递归的核心概念

递归算法有两个关键要素：

• 递归出口（终止条件）：什么时候停止调用自己
• 递归体（递推关系）：如何把大问题拆成小问题

你想想看，如果没有终止条件，函数就会无限调用下去，直到栈空间耗尽。我曾经在调试一个程序时，忘了写终止条件，结果程序直接崩溃，查了半天才发现是递归没出口。

递归的调用过程

递归调用时，系统会为每一层调用分配栈帧。每一层都有自己的局部变量和参数。当最深层的调用返回时，逐层回溯。

来看一个最简单的例子——计算阶乘：

// 计算 n 的阶乘
int factorial(int n) {
    // 递归出口
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递归体：n! = n * (n-1)!
    return n * factorial(n - 1);
}

调用 factorial(4) 时，过程是这样的：

factorial(4) 调用 factorial(3)
  factorial(3) 调用 factorial(2)
    factorial(2) 调用 factorial(1)
      factorial(1) 返回 1
    factorial(2) 返回 2 * 1 = 2
  factorial(3) 返回 3 * 2 = 6
factorial(4) 返回 4 * 6 = 24

每一层调用都在等待下一层返回结果。这就是递归的「递推」和「回归」过程。

递归与非递归的转换

递归代码简洁，但效率不一定高。因为每次函数调用都有开销——压栈、传参、返回。而且递归深度太大时，容易栈溢出。

非递归实现，说白了就是用循环加栈来模拟递归过程。我一般在嵌入式开发中，如果递归深度可控（比如小于100层），就用递归；如果深度不确定，就改用循环。

来看斐波那契数列的例子：

// 递归实现
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

// 非递归实现（循环）
int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

递归版本虽然直观，但重复计算太多。比如 fib_recursive(5) 会计算 fib_recursive(3) 两次。非递归版本就避免了这个问题。

经典递归应用：汉诺塔

汉诺塔问题，是理解递归的绝佳例子。规则很简单：把A柱上的盘子全部移到C柱，每次只能移动一个盘子，大盘子不能压在小盘子上。

思路是这样的：

• 先把 n-1 个盘子从 A 移到 B（借助 C）
• 然后把第 n 个盘子从 A 移到 C
• 最后把 n-1 个盘子从 B 移到 C（借助 A）

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("移动盘子 1 从 %c 到 %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("移动盘子 %d 从 %c 到 %c\n", n, from, to);
    hanoi(n - 1, aux, to, from);
}

调用 hanoi(3, 'A', 'C', 'B') 的输出：

移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C

你看，代码只有几行，但逻辑非常清晰。这就是递归的魅力。

经典递归应用：八皇后

八皇后问题：在 8×8 的棋盘上放 8 个皇后，让它们互不攻击。说白了就是任意两个皇后不能在同一行、同一列或同一对角线上。

我用回溯法来解决，本质上就是递归加剪枝。

#define N 8
int board[N][N] = {0};

// 检查位置是否安全
int is_safe(int row, int col) {
    int i, j;
    // 检查列
    for (i = 0; i < row; i++)
        if (board[i][col]) return 0;
    // 检查左上对角线
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return 0;
    // 检查右上对角线
    for (i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j]) return 0;
    return 1;
}

// 递归放置皇后
int solve(int row) {
    if (row == N) return 1;  // 所有皇后都放好了
    for (int col = 0; col < N; col++) {
        if (is_safe(row, col)) {
            board[row][col] = 1;
            if (solve(row + 1)) return 1;
            board[row][col] = 0;  // 回溯
        }
    }
    return 0;
}

核心思想：逐行放置，每行放一个。如果当前行找不到安全位置，就回溯到上一行，换一列试试。

递归知识体系总览

下面这张图，帮你理清递归的核心脉络：

递归的优缺点

优点	缺点
代码简洁、逻辑清晰	效率较低（函数调用开销）
适合分治、树形结构	深度大时可能栈溢出
易于理解和维护	调试相对困难

递归不是万能的。我个人的经验是：能用循环解决的问题，优先用循环。但遇到树、图、分治这类问题，递归往往是最自然的选择。

递归这东西，刚开始觉得绕，多写几遍就顺了。我建议你从阶乘、斐波那契开始练手，然后挑战汉诺塔和八皇后。写代码时，先在纸上画一画调用过程，慢慢就找到感觉了。