第38章递归进阶

课程目录第38章递归进阶

第38章：递归进阶——汉诺塔问题与快速排序的递归实现

递归这东西，说实话，很多初学者学到这儿就开始犯怵了。我当年也一样，看到递归调用自己，总觉得脑子要绕成一个死循环。但后来我发现，递归其实就两个核心：递出去，再归回来。你只要把这两个动作想清楚，什么汉诺塔、快速排序，统统不在话下。

这一章，咱们就啃两块硬骨头：汉诺塔问题和快速排序的递归实现。这两个例子，一个是经典的递归思维训练，一个是实际工程中高频使用的算法。搞懂了它们，你对递归的理解会上一个台阶。

38.1 汉诺塔问题：递归思维的经典案例

先说说汉诺塔。这个问题的背景很简单：有三根柱子，A、B、C。A柱上有n个大小不等的圆盘，大的在下，小的在上。目标是把所有圆盘从A移到C，过程中可以借助B。规则就两条：一次只能移动一个盘，大盘不能压在小盘上。

你想想看，如果只有1个盘，直接挪过去就完事了。但如果有3个、5个、甚至64个盘呢？手动模拟会疯掉。这时候递归就派上用场了。

我个人习惯把汉诺塔的递归思路总结成三步：

把上面n-1个盘从A移到B（借助C）
把最底下的第n个盘从A移到C
再把B上的n-1个盘从B移到C（借助A）

你看，问题规模从n变成了n-1，这就是递归的典型特征——问题规模逐步缩小，直到边界条件。

核心要点：汉诺塔的递归本质是——把大问题拆成两个子问题加一个基本操作。子问题和原问题形式相同，只是规模更小。

代码实现其实很简洁：

#include <stdio.h>

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);
}

int main() {
    int n = 3;
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

运行结果会打印出每一步的移动过程。你试试n=3，看看输出，再对照我上面说的三步，就能理解递归是怎么一层层展开又一层层收回的。

小提示：我在项目中遇到过类似的问题——需要把一批任务按依赖关系重新排序。当时我就想到了汉诺塔的递归思想，把依赖链拆解成子任务，逐层处理。递归思维在复杂逻辑拆解中非常实用。

38.2 快速排序：递归在排序中的经典应用

快速排序，简称快排，是实际工程中最常用的排序算法之一。C标准库里的qsort就是基于快排实现的。它的核心思想也是递归——分而治之。

快排的基本思路是这样的：

从数组中选一个元素作为基准（pivot）
把比基准小的元素放左边，比基准大的放右边——这一步叫分区（partition）
对左右两个子数组递归地执行同样的操作

说白了，就是每次选一个基准，把数组分成两半，然后分别处理。直到子数组只剩一个元素，递归结束。

注意：快排的性能高度依赖基准的选择。如果每次选的基准都恰好是中位数，时间复杂度是O(n log n)。但如果选的基准总是最小或最大，就会退化成O(n²)。我曾经在项目中遇到过线上数据分布不均匀导致快排变慢的情况，后来改用三数取中法选基准，问题就解决了。

来看代码实现：

#include <stdio.h>

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选最后一个元素作为基准
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 把基准放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

// 快速排序的递归实现
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);   // 排序左半部分
        quickSort(arr, pi + 1, high);  // 排序右半部分
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

你看，quickSort函数里调用了自己两次——一次处理左边，一次处理右边。这就是递归的典型用法：先分治，再递归。

38.3 递归的避坑指南

说到递归，我得提醒你几个容易踩的坑。这些都是我当年亲手踩过的：

忘记写终止条件——递归会无限调用下去，最终栈溢出。我曾经调试一个bug调了一下午，最后发现就是少了个if (n == 0) return;。
递归层数太深——每层递归都会占用栈空间。如果递归深度达到几千甚至上万，程序很容易崩溃。我建议递归深度超过1000的场景，考虑改用循环或迭代。
重复计算——比如斐波那契数列的朴素递归实现，会有大量重复计算。这时候可以用记忆化递归或动态规划来优化。

经验之谈：递归不是万能的。有些问题用循环更直观，有些问题用递归更优雅。我的原则是——如果递归能让代码更清晰，就用；如果递归让代码更难懂，就别用。

38.4 本章知识体系总览

下面这张图帮你梳理了本章的核心知识点和它们之间的关系：

38.5 写在最后

递归这东西，你光看是看不明白的。我建议你打开编译器，把上面的代码敲一遍，单步调试走一走。看看函数调用栈是怎么一层层压进去，又一层层弹出来的。嗯，等你亲眼看到那个过程，你就真正理解了。

记住一句话：递归不是魔法，是分治思想的自然表达。你只要抓住「递出去」和「归回来」这两个动作，递归就不再神秘。

个人建议：学完这一章，你可以试着用递归实现一个二分查找或归并排序。这两个也是递归的经典应用，练熟了，你的递归功力就真正到家了。

公众号：蓝海资料掘金营，微信 deep3321

📚 课程目录