元数据卡

• 前置知识：方法（第5章）、调用栈（第5章）、循环（第4章）
• 预计时间：15 分钟
• 阅读模式： 高度专注
• 完成标志：能写出带有基准情况和递归情况的简单递归

本章分层

• 必读：基准情况与递归情况、递归 vs 循环
• 选读：分治思想的递归表达
• 进阶：无

你的进度

上完方法课，你绕到铁匠铺后院透透气，发现老陈站在那棵歪脖子树下朝你招手。

"爬到树顶，把最上面的那个果子扔下来。"

你仰头一看——树枝一层层分叉，每一层的分叉又生出更多分叉。你找到主树干，爬上第一根树枝，然后是第二根，第三根……到了某一层，你发现前面的路分成了两条。你选了右边那根，爬到顶，拿到果子，扔下来。然后你得退回来，从左边那根再爬上去。

"不对，"老陈说，"你不是在爬树——你是在重复同一个动作：在每根树枝上，先找到所有子树枝，对每个子树枝做同样的事。"

这就是递归。上一章学会了方法调方法，但有一个局面你还没面对：方法能不能调用自己？

第一幕：从阶乘说起

阶乘：5! = 5 × 4 × 3 × 2 × 1 = 120。你先用循环写一遍：

public class Factorial {
    public static void main(String[] args) {
        System.out.println("5! = " + factorialLoop(5));
        System.out.println("10! = " + factorialLoop(10));
    }

    static long factorialLoop(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

预期输出：5! = 120 和 10! = 3628800

观察规律：

n! = n × (n-1)!   （当 n > 1 时）
1! = 1             （基准情况）

数学定义长什么样，代码就长什么样：

static long factorialRecur(int n) {
    if (n <= 1) {
        return 1;                       // 基准情况：递归的终点
    }
    return n * factorialRecur(n - 1);   // 递归情况：n! = n × (n-1)!
}

完整代码对比：

public class Factorial {
    public static void main(String[] args) {
        System.out.println("循环: 5! = " + factorialLoop(5));
        System.out.println("递归: 5! = " + factorialRecur(5));
        System.out.println("递归: 10! = " + factorialRecur(10));
    }

    static long factorialLoop(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) result *= i;
        return result;
    }

    static long factorialRecur(int n) {
        if (n <= 1) return 1;
        return n * factorialRecur(n - 1);
    }
}

预期输出：

循环: 5! = 120
递归: 5! = 120
递归: 10! = 3628800

没有循环变量，没有累加器，没有 i++。递归是在表达"是什么"，不是"怎么做"。

第二幕：两个关键部件

部件	作用	如果忘了写
基准情况（base case）	告诉递归"停在这里"	无限递归 → StackOverflowError
递归情况（recursive case）	让问题变得更小，逼近基准	同样会无限递归

没写基准情况 → 无限递归 = 循环的远房亲戚。

第三幕：递归 vs 循环

能用循环解决的问题，优先用循环。

对比	循环	递归
代码行数	多一些	少（直接表达数学定义）
性能	快	慢（每次递归=一次方法调用）
内存	O(1)	O(n)（压 n 层栈帧）
适用场景	线性遍历	树状结构、分治

实例：遍历文件目录

用循环写目录遍历，你得自己维护显式栈。递归一句话解决：

static void listAllFiles(File dir, int depth) {
    for (File file : dir.listFiles()) {
        System.out.println(file.getName());
        if (file.isDirectory()) listAllFiles(file, depth + 1);
    }
}

读的人一眼就知道："它在递归地遍历目录。"

老陈的经验法则：树状结构用递归，线性序列用循环，想不清楚先用循环。

旅人笔记

递归 = 方法调用自己。基准情况让递归停止，递归情况让问题变小。递归天然适合树状结构，线性问题优先用循环。记住：递归是思维工具，不只是编程技巧。

→ 下一站：递归的调用栈

你已经知道递归是什么了。但递归调用在内存中是怎么工作的？为什么递归太深会栈溢出？尾递归又是什么东西？下一节，递归的调用栈与尾递归带你看清递归的内存面貌。