Java 递归与经典算法练习

递归是入门系列的第一个”思维门槛”：代码看上去只有几行，执行过程却在方法调用栈里层层深入。本篇作为系列进阶收尾的第一课，从调用栈讲清递归的本质，再用五个经典问题把递归思维练到肌肉记忆。

本篇目标

读完本篇你应该能够：说出递归执行时 JVM 栈上发生了什么；用”递推关系、出口、问题规模”三要素拆解任何递归问题；独立写出阶乘、斐波那契、目录遍历、汉诺塔的递归实现；并掌握约瑟夫环的模拟解与公式解两种打法。

递归的执行本质：方法调用栈

递归不是语法糖，而是栈结构的自然应用。Java 中每次方法调用，JVM 都会在当前线程的虚拟机栈上压入一个栈帧，存放局部变量、操作数栈和返回地址；方法返回时栈帧弹出。递归不过是”方法调用自己”，每调用一次就多压一帧，直到触及出口再逐层弹栈返回。

以 factorial(3) 为例，栈上的过程是：

public static long factorial(int n) {
    if (n == 1) {          // 出口：最小问题直接给答案
        return 1;
    }
    return n * factorial(n - 1);  // 递推：把大问题拆小
}

调用链为 factorial(3) → factorial(2) → factorial(1)，压栈三层；factorial(1) 返回 1 后开始弹栈，依次算出 2*1=2、3*2=6。理解这张图，递归就不再神秘：先一路向下递（分解），再一路向上归（合并结果）。

还有一个细节值得注意：每层栈帧里的局部变量是相互独立的。factorial(3) 里的 n 是 3，factorial(2) 里的 n 是 2，它们同名但活在不同的栈帧中，互不干扰。想明白这一点，就不会再有”递归里变量会不会串”的疑惑。

代价也很直接：每层调用都要占栈空间，方法调用本身也有压栈弹栈的开销。递归深度过大就会 StackOverflowError——默认栈容量下，大约几千到上万层就到头了。递归的深度受限于栈容量，这也是后面斐波那契一节的教训。

递归三要素

写递归前先在纸上回答三个问题，缺一不可：

递推关系：f(n) 与 f(n-1) 是什么关系？这是递归体的来源。
出口：最小可以直接回答的问题是什么？没有出口就是无限递归。
问题规模必须收敛：每次调用必须让参数朝出口靠近，否则出口永远够不着。

新手最常犯的错，一是漏写出口，二是递归调用没有改变参数（如把 n-1 写成 n），两者结局都是栈溢出。

经典练习一：斐波那契数列

兔子繁殖问题抽象出的数列 1 1 2 3 5 8 13 ...，递推关系天然就是 fib(n) = fib(n-1) + fib(n-2)：

public static long fib(int n) {
    if (n <= 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

代码漂亮，但效率堪忧：fib(40) 就要上亿次调用，因为 fib(n-2) 被反复重算，时间复杂度是指数级 O(2^n)。这是递归给人的第一个警示——递归描述问题很优雅，不等于递归执行很高效。工程上的改法有两种：用数组做记忆化（把算过的结果存起来），或干脆改成循环迭代：

public static long fibIter(int n) {
    long a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

顺便提一个阶乘的延伸问题：求 1000! 尾部有多少个零。尾部零来自因子 10 = 2 × 5，而因子 2 远比 5 多，所以只需求 1 到 1000 中因子 5 的总个数：1000/5 + 1000/25 + 1000/125 + 1000/625 = 249。这种问题硬算阶乘必溢出，找规律才是正解。

经典练习二：目录遍历

文件系统天然是树形结构，遍历它是递归最实用的场景。需求：接收一个文件夹路径，按层级打印所有文件和子目录。

public static void listFiles(File dir, int level) {
    for (int i = 0; i < level; i++) {
        System.out.print("\t");
    }
    System.out.println(dir.getName());
    if (dir.isDirectory()) {
        File[] children = dir.listFiles();
        if (children != null) {
            for (File child : children) {
                listFiles(child, level + 1);   // 规模收敛：进入下一层
            }
        }
    }
}

递推关系是”打印自己，再对每个子目录做同样的事”；出口隐含在 isDirectory() 为 false 或目录为空时自然返回；level 参数只负责缩进美观。统计文件夹大小、删除文件夹（先删子项再删自己）、递归拷贝，都是同一个模板的变体：删除和拷贝尤其注意顺序——必须先处理完子文件，父目录才能动。

这里有个实用的防御细节：listFiles() 可能返回 null（目录不可读或 I/O 出错时），不做判空直接遍历会抛 NullPointerException。凡是对文件系统做递归，判空都应该写成习惯。

经典练习三：汉诺塔

三根柱子 A、B、C，把 n 个盘子从 A 借助 B 移到 C，每次只能动一个盘且大盘不能压小盘。递归拆法极漂亮：把上面 n-1 个盘从 A 借 C 移到 B，把第 n 个盘从 A 移到 C，再把 n-1 个盘从 B 借 A 移到 C。

public static void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        System.out.println(from + " -> " + to);
        return;
    }
    hanoi(n - 1, from, to, aux);   // 前 n-1 个移到辅助柱
    System.out.println(from + " -> " + to);
    hanoi(n - 1, aux, from, to);   // 再从辅助柱移到目标柱
}

出口是只有一个盘时直接移动；规模收敛体现在 n 减 1。移动次数是 2^n - 1，n=64 时即是天文数字——递归让你用三行逻辑描述了一个宇宙级的工作量。这道题也演示了递归的典型心法：不要试图在脑子里模拟每一层调用，只要确信”n-1 个盘的问题能被同样的方法解决”，把当前层该做的一步写对，剩下的交给递归。层层脑内展开是人类不擅长也没必要做的事。

经典练习四：约瑟夫环

n 个人围成圈报数，数到 m 的人出局，下一个人重新从 1 报数，求最后幸存者的编号。

解法一：集合模拟。 用 ArrayList 存编号，维护当前索引，每轮 (index + m - 1) % size 定位出局者并移除：

public static int josephusSimulate(int n, int m) {
    List<Integer> list = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        list.add(i);
    }
    int index = 0;
    while (list.size() > 1) {
        index = (index + m - 1) % list.size();
        list.remove(index);
    }
    return list.get(0);
}

模拟法直观、好写，时间 O(n²)（ArrayList 删除要搬移元素），适合验证答案。

解法二：递推公式。 设 f(n, m) 为 n 人时的幸存者下标（从 0 计）。第 k 个人出局后，问题规模缩小为 n-1，且幸存者相对位置平移了 m，得到递推式 f(n) = (f(n-1) + m) % n，边界 f(1) = 0：

public static int josephus(int n, int m) {
    int result = 0;                 // f(1) = 0
    for (int i = 2; i <= n; i++) {
        result = (result + m) % i;  // 逐轮反推
    }
    return result + 1;              // 转成从 1 开始的编号
}

公式解 O(n) 时间、O(1) 空间，是面试中的标准答案。两种解法会一对比，正是”先能跑、再求优”的进阶路径。

小结

递归的本质是方法调用栈的压栈与弹栈：先递后归，每层都有独立的局部变量。
三要素缺一不可：递推关系、出口、规模收敛；缺出口或不收敛就是栈溢出。
斐波那契暴露了递归的效率陷阱，记忆化或迭代是常规解法；汉诺塔展示了递归的表达力。
目录遍历是递归最实用的模板，删除、拷贝、统计大小皆从此出。
约瑟夫环一题两解：模拟解负责”对”，公式解负责”快”。

下一篇进入并发世界，看看多条执行路径如何共享一个程序。