2026-05-31 递归三论：阶乘、斐波那契与目录遍历

一、递归是什么

用今天自己的话总结——递归就像高中数学的等差等和通项公式：用规律定义自己，具有普适性。

一个递归方法必须包含两部分：

• 基准情况（Base Case）：递归终止条件，不再调用自身，直接返回值
• 递归情况（Recursive Case）：将问题分解为更小的子问题，调用自身

二、阶乘：递归入门

阶乘定义：n! = n × (n-1) × ... × 2 × 1，特别地 0! = 1。

一个常见的错误是把 0! 设为 0——但验证 1! = 1 × 0! = 1 × 0 = 0 就会暴露矛盾。正确的基准情况是 n=0 时返回 1。

public static int factorial(int n) {
    if (n == 0) return 1;        // 基准情况
    return n * factorial(n - 1);  // 递归情况
}

调用 factorial(5) 时，展开顺序是 5 → 4 → 3 → 2 → 1 → 0，到 0 后返回 1，然后逐层收拢：1×1=1, 2×1=2, 3×2=6, 4×6=24, 5×24=120。

三、斐波那契：双递归分支

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, ...，从第三项起每一项是前两项之和。

public static int fib(int n) {
    if (n == 0) return 0;        // 基准情况 1
    else if (n == 1) return 1;   // 基准情况 2
    else return fib(n - 1) + fib(n - 2); // 递归情况：双分叉
}

与阶乘不同，斐波那契的递归呈树形展开——fib(5) 会同时展开 fib(4) 和 fib(3)，每个分支再分别展开。这也是递归的代价：重复计算严重，时间复杂度 O(2^n)，实际项目中可用记忆化搜索或迭代优化。

四、目录遍历：隐式基准

递归最自然的应用场景不是数学公式，而是深度未知的树形结构——比如文件夹嵌套。

public static void listDirectory(File dir) {
    File[] files = dir.listFiles();
    if (files == null) return;   // 防御：路径不存在
    for (File file : files) {
        if (file.isDirectory())
            listDirectory(file);   // 递归：进入子目录
        else
            System.out.println(file.getName()); // 基准：输出文件
    }
}

这里的基准情况是隐式的——文件直接输出不递归，空目录遍历完自然返回。不需要显式写 if (n==0) 这样的终止条件。

五、递归 vs 循环

场景	适用方案	原因
已知次数/边界明确	循环	简单直接，无栈溢出风险
深度未知的树/图遍历	递归	天然匹配嵌套结构，代码简洁
大规模数据	循环/迭代	递归有栈溢出风险

六、递归三大风险

1. 基准情况设定错误——逻辑正确性崩溃（如 0!=0 导致 1!=0）
2. 无限递归——终止条件漏写或写错，调用栈溢出
3. 数据规模过大——频繁入栈不出栈，StackOverflowError

七、今日反思

递归不是”让方法调用自己”的语法技巧，而是一种分治思维——把大问题拆成同结构的小问题，直到小到可以直接解决。目录遍历的例子让我意识到，循环的局限在于它假设你事先知道有几层嵌套；递归不问这个，来一层处理一层，管你套了多少层。

从阶乘到斐波那契到目录遍历，一节课推完三个场景。最大的收获不是代码能跑，是能说清楚什么时候该用递归、什么时候不该用——后者比前者更重要。

---

代码链接

• factorial.java — 阶乘递归实现
• Fib.java — 斐波那契递归实现
• UseFile.java — 目录遍历递归实现