递归 | JavaSE

递归

一、学习目标

学完本章，你应该能够：

能够用自己的语言解释什么是递归（Recursion）。
能够区分直接递归与间接递归。
能够说出一个正确递归必须具备的核心要素：递归关系、终止条件、向终止条件推进。
能够通过调用栈解释递归为什么会“先不断深入，再逐层返回”。
能够独立使用递归计算 1 ~ n 的和与 n!。
能够判断一段递归代码是否存在无限递归或无法到达终止条件的问题。
能够解释为什么递归可能导致 StackOverflowError。
能够初步判断递归和循环各自适合的场景，为下一章递归遍历目录树做好准备。

二、核心知识

2.1 什么是递归

递归（Recursion）是一种非常重要的算法思想。

从程序形式上看：

一个方法在执行过程中再次调用自身，称为方法递归。

最简单的形式：

public static void method() {

    method();
}

这就是：

method()
  ↓
method()
  ↓
method()
  ↓
method()
  ↓
...

但注意：

上面只是“递归的形式”，不是一个正确的递归算法。

因为它永远不会结束。

2.2 直接递归

如果一个方法：

直接调用自己

称为：

直接递归（Direct Recursion）

例如：

public static void methodA() {

    methodA();
}

调用结构：

methodA
   ↓
methodA
   ↓
methodA

2.3 间接递归

如果：

A 调用 B
B 又调用 A

也形成递归。

例如：

public static void methodA() {

    methodB();
}

public static void methodB() {

    methodA();
}

调用结构：

methodA
   ↓
methodB
   ↓
methodA
   ↓
methodB
   ↓
...

这称为：

间接递归（Indirect Recursion）

初学阶段重点仍然是：

直接递归

2.4 为什么递归不是简单的“自己调用自己”

如果只是：

f();

内部再：

f();

其实没有任何算法价值。

真正有意义的递归是：

大问题
    ↓
转化成
规模更小的同类问题
    ↓
继续转化
    ↓
直到出现最简单情况
    ↓
直接得到答案

例如求：

5!

数学定义：

5!
=
5 × 4 × 3 × 2 × 1

可以写成：

5!
=
5 × 4!

而：

4!
=
4 × 3!

继续：

3!
=
3 × 2!

继续：

2!
=
2 × 1!

最后：

1!
=
1

于是：

5!
↓
5 × 4!
↓
5 × 4 × 3!
↓
5 × 4 × 3 × 2!
↓
5 × 4 × 3 × 2 × 1!
↓
得到答案

这就是递归真正的核心：

把规模为 n 的问题，转化为规模更小的同类问题。

2.5 递归三要素

原课程将递归三要素总结为：

1. 递归公式

2. 递归终结点

3. 递归方向必须走向终结点

这是非常好的基本框架。

2.6 第一要素：递归关系

例如阶乘：

f(n)
=
n × f(n - 1)

也就是：

求 n!，可以转化成求 (n - 1)!。

代码思想：

return n * factorial(n - 1);

这就是：

递归关系

2.7 第二要素：终止条件

如果永远：

f(n)
→
f(n-1)
→
f(n-2)
→
...

仍然会无限递归。

因此必须存在：

最简单、可以直接得到答案的情况。

例如：

1! = 1

代码：

if (n == 1) {
    return 1;
}

这个条件叫：

递归出口

或者：

终止条件

2.8 第三要素：必须不断接近终止条件

只写一个终止条件还不够。

例如：

public static int f(int n) {

    if (n == 1) {
        return 1;
    }

    return n * f(n + 1);
}

看起来：

有出口

但是如果开始：

n = 5

递归方向是：

5
↓
6
↓
7
↓
8
↓
...

它离：

n == 1

越来越远。

所以仍然不会结束。

因此：

有出口

只是必要条件。

还必须：

每一次递归调用，都让问题规模向出口靠近。

正确：

f(n - 1)

而不是：

f(n + 1)

2.9 一个正确递归的标准模板

可以抽象成：

public static Result recursion(State state) {

    if (满足终止条件) {

        return 最简单问题的答案;
    }

    return 使用(
            recursion(
                    更接近终止条件的新状态
            )
    );
}

思维结构：

当前问题
   │
   ├── 已经最简单？
   │       │
   │       └── 是 → 直接返回
   │
   └── 否
           │
           ▼
      缩小问题规模
           │
           ▼
        再调用自己

三、使用方法

3.1 使用递归计算 1 到 n 的和

问题：

1 + 2 + 3 + ... + n

假设：

sum(5)

我们可以发现：

sum(5)
=
5 + sum(4)

继续：

sum(4)
=
4 + sum(3)

所以递归公式：

sum(n)
=
n + sum(n - 1)

终止条件：

sum(1)
=
1

代码：

public class RecursionSumDemo {

    public static void main(String[] args) {

        System.out.println(
                sum(5)
        );
    }

    public static int sum(int n) {

        if (n == 1) {
            return 1;
        }

        return n + sum(n - 1);
    }
}

结果：

3.2 不要先想着“代码怎么写”

面对递归题时，推荐先写数学关系。

例如：

问题：
1 + 2 + ... + n

第一步：

递归关系：

f(n)
=
n + f(n-1)

第二步：

出口：

f(1)
=
1

第三步：

方向：

n
→
n-1
→
n-2
→
...
→
1

最后再翻译成：

if (n == 1) {
    return 1;
}

return n + f(n - 1);

这比：

一上来盯着 Java 代码硬憋

有效得多。

3.3 使用递归计算阶乘

阶乘：

n!
=
n × (n-1) × ... × 1

例如：

5!
=
5 × 4 × 3 × 2 × 1
=
120

递归关系：

f(n)
=
n × f(n-1)

出口：

f(1)
=
1

代码：

public class FactorialDemo {

    public static void main(String[] args) {

        System.out.println(
                factorial(5)
        );
    }

    public static long factorial(int n) {

        if (n == 1) {
            return 1;
        }

        return n * factorial(n - 1);
    }
}

这里使用：

long

只是比 int 能表示更大的整数范围。

但注意：

long 也不是无限大。

阶乘增长非常快。

3.4 递归展开

真正理解递归，一定要会手工展开。

例如：

factorial(5)

首先进入：

factorial(5)

由于：

5 != 1

所以：

return
5 × factorial(4)

但是：

factorial(4)

结果还不知道。

于是必须先去计算：

factorial(4)

继续：

factorial(4)
=
4 × factorial(3)

继续：

factorial(3)
=
3 × factorial(2)

继续：

factorial(2)
=
2 × factorial(1)

最后：

factorial(1)
=
1

至此：

递归终于停止向下深入

3.5 然后开始逐层返回

达到：

factorial(1)
=
1

之后：

factorial(2)
=
2 × 1
=
2

然后：

factorial(3)
=
3 × 2
=
6

然后：

factorial(4)
=
4 × 6
=
24

最后：

factorial(5)
=
5 × 24
=
120

整个过程：

递归阶段（深入）

f(5)
↓
f(4)
↓
f(3)
↓
f(2)
↓
f(1)

────────────

返回阶段（回溯）

f(1) = 1
↑
f(2) = 2
↑
f(3) = 6
↑
f(4) = 24
↑
f(5) = 120

所以递归不是：

一直向下

而是：

先深入
再返回

四、原理与进阶

4.1 方法调用需要栈帧

以前学习普通方法时：

main();

调用：

test();

JVM 必须知道：

test 的局部变量是什么
参数是什么
执行到哪里
结束以后返回哪里

因此每一次方法调用都需要保存对应的调用状态。

可以简化理解成：

栈帧（Stack Frame）

4.2 普通方法的调用栈

例如：

main()
↓
a()
↓
b()

调用栈大致：

┌──────────┐
│ b()      │
├──────────┤
│ a()      │
├──────────┤
│ main()   │
└──────────┘

当：

b()

结束：

弹出 b

然后回到：

之后：

结束：

弹出 a

最后返回：

main

4.3 递归只是方法调用的特殊情况

例如：

factorial(5)

会形成：

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)

每一层都是：

一次新的方法调用。

因此调用栈可以简化表示：

┌────────────────┐
│ factorial(1)   │
├────────────────┤
│ factorial(2)   │
├────────────────┤
│ factorial(3)   │
├────────────────┤
│ factorial(4)   │
├────────────────┤
│ factorial(5)   │
├────────────────┤
│ main()         │
└────────────────┘

注意：

factorial(5)

和：

factorial(4)

虽然执行的是同一个方法代码，

但它们不是：

同一次调用

而是：

不同的调用栈帧

每一层都有自己的：

参数 n
执行位置
局部状态
返回位置

4.4 为什么递归可以保存每层不同的 n

很多初学者会困惑：

明明变量都叫 n，
为什么不会互相覆盖？

因为：

factorial(5)

中的 n 属于：

factorial(5) 这一层栈帧

而：

factorial(4)

中的 n 属于：

factorial(4) 这一层栈帧

可以想象：

┌───────────────┐
│ f(1) n = 1   │
├───────────────┤
│ f(2) n = 2   │
├───────────────┤
│ f(3) n = 3   │
├───────────────┤
│ f(4) n = 4   │
├───────────────┤
│ f(5) n = 5   │
└───────────────┘

这正是递归能够工作的基础之一。

4.5 什么是无限递归

例如：

public static void test() {

    test();
}

执行：

test
↓
test
↓
test
↓
test
↓
...

每一次调用：

都需要新的栈帧

于是：

栈空间不断消耗

最终：

无法继续建立新的栈帧

于是可能出现：

StackOverflowError

即：

栈溢出错误。

4.6 有出口也可能栈溢出

例如：

public static void test(int n) {

    if (n == 1) {
        return;
    }

    test(n + 1);
}

它有：

n == 1

这个出口。

但是：

5
→
6
→
7
→
8

永远到不了：

最终还是可能：

StackOverflowError

所以必须牢记：

出口
+
方向

缺一不可。

4.7 即使递归正确，也不能无限深

例如理论上：

sum(1_000_000)

你写出了完全正确的：

终止条件
递归关系
递归方向

但是递归深度：

100 万层

很可能远远超过 JVM 栈能够承受的范围。

因此：

逻辑正确的递归，也不代表在任意规模数据上都安全。

这是递归的重要工程边界。

4.8 递归的时间复杂度与空间复杂度

例如：

sum(n)

每一层只调用一次：

sum(n-1)

总调用次数大约：

所以时间复杂度：

O(n)

由于递归调用栈深度也是：

因此额外空间复杂度：

O(n)

而循环：

int sum = 0;

for (int i = 1; i <= n; i++) {
    sum += i;
}

时间复杂度也是：

O(n)

但额外空间通常：

O(1)

因此不能因为递归“看起来高级”就强行使用递归。

4.9 递归和循环不是谁取代谁

对于：

1 + 2 + ... + n

循环通常更加直接：

for (...)

而对于：

目录树
二叉树
树形菜单
组织结构
DFS

数据本身就是：

一个节点
└── 若干子节点
    └── 若干子节点
        └── ...

这种结构天然具有：

自相似性。

因此递归往往非常自然。

4.10 什么叫自相似问题

例如一个文件夹：

folder
├── file
├── file
└── folder

而里面的子文件夹：

folder
├── file
└── folder

结构仍然是：

文件
+
文件夹

也就是说：

子问题和原问题拥有相同结构。

这正是递归最喜欢的问题。

因此下一章：

文件搜索

为什么适合递归，其根本原因就在这里。

五、实践应用

5.1 用递归思维理解目录树

假设：

project
├── README.md
├── src
│   ├── Main.java
│   └── service
│       └── UserService.java
└── docs
    └── api.md

如果我们定义：

处理一个目录

要做的事情是：

遍历它的一级成员

如果遇到：

文件

直接处理。

如果遇到：

目录

怎么办？

答案：

再执行一次
“处理一个目录”

也就是：

处理目录(project)
       │
       ├── README.md → 文件
       │
       ├── src → 处理目录(src)
       │             │
       │             ├── Main.java
       │             └── service
       │                    ↓
       │               处理目录(service)
       │
       └── docs → 处理目录(docs)

这就是：

递归遍历目录树

本章只理解这个模型。

完整代码将在：

07-04 文件搜索与递归综合案例

正式实现。

5.2 递归解决问题的标准分析流程

以后碰到递归题，不要直接写代码。

推荐按照：

第一步：定义方法到底解决什么问题
        ↓
第二步：找出规模更小的同类问题
        ↓
第三步：写递归关系
        ↓
第四步：找最简单情况
        ↓
第五步：写终止条件
        ↓
第六步：确认每次递归都向出口靠近
        ↓
第七步：手工展开 3～5 层
        ↓
第八步：再写 Java

例如：

factorial(n)

定义：

计算 n!

子问题：

factorial(n - 1)

关系：

factorial(n)
=
n × factorial(n - 1)

出口：

factorial(1)
=
1

方向：

n → n-1

最后再写代码。

六、常见问题

6.1 递归是不是方法“重复执行”？

不准确。

每一次：

f(n - 1)

都是：

一次新的方法调用。

因此有新的：

栈帧
参数
局部变量
执行状态

6.2 为什么必须有递归出口？

没有出口：

调用永远不会停止
↓
栈帧不断增加
↓
最终栈空间耗尽

可能导致：

StackOverflowError

6.3 有出口为什么还会死递归？

因为：

递归方向

没有向出口靠近。

例如：

出口 n == 1

但调用 n + 1

从：

出发永远无法到：

6.4 `StackOverflowError` 是 Exception 吗？

不是普通的：

Exception

它属于：

Error

因此在概念上应准确称为：

StackOverflowError，栈溢出错误。

不要把递归写坏以后理解成：

“捕获一下异常就好了”。

真正解决办法应该是：

修正递归逻辑
控制递归深度
或者改用其他算法

6.5 所有循环都可以改成递归吗？

很多迭代问题从理论上可以设计成递归形式，但：

能写，不代表应该写。

例如：

1 到 100 求和

循环：

for

更直接。

递归真正有优势的通常是：

树
目录
DFS
分治
回溯

等天然递归结构。

6.6 递归一定比循环慢吗？

不能机械地说：

递归一定慢
循环一定快

但递归通常具有：

额外方法调用
+
调用栈空间

因此在简单线性任务上：

循环

往往更节省栈空间。

选择算法应该看：

问题结构
可读性
数据规模
性能要求
栈深度

6.7 Java 会自动把尾递归优化掉吗？

在本课程阶段不要依赖这种假设。

即使递归调用写在最后：

return f(n - 1);

Java 程序也不应该建立在：

JVM 一定会自动消除递归栈帧

这一前提上。

因此对可能非常深的递归：

依然要警惕 StackOverflowError

七、练习与验收

7.1 知识问答

闭卷回答：

什么是递归？
什么是直接递归？
什么是间接递归？
递归与普通方法调用在调用栈层面有什么关系？
一个正确递归需要哪几个核心条件？
什么是递归出口？
为什么“有出口”仍然可能无限递归？
为什么递归可能导致 StackOverflowError？
StackOverflowError 属于 Exception 还是 Error？
递归调用时为什么每一层的局部变量不会直接覆盖上一层？
阶乘的递归关系是什么？
1 ~ n 求和的递归关系是什么？
为什么目录树天然适合递归？
递归与循环在栈空间方面通常有什么差异？
什么情况下应该优先考虑循环而不是递归？

7.2 代码阅读

不要运行：

public class RecursionRead {

    public static void main(String[] args) {

        System.out.println(
                f(4)
        );
    }

    public static int f(int n) {

        if (n == 1) {
            return 1;
        }

        return n + f(n - 1);
    }
}

要求：

写出 f(4) 的完整调用展开过程。
写出调用栈最深时有哪些方法调用。
写出逐层返回过程。
最终结果是多少？
如果：

f(n - 1)

改成：

f(n + 1)

会发生什么？

7.3 手写代码

任务一：1 到 n 求和

从零实现：

sum(int n)

要求：

禁止循环

完成后说明：

递归公式
递归出口
递归方向

任务二：阶乘

实现：

factorial(int n)

要求：

不看示例；
使用递归；
手工展开 factorial(5)；
写出调用顺序；
写出返回顺序。

任务三：倒序打印

设计递归方法：

print(int n)

调用：

print(5);

输出：

先写递归关系，再写代码。

任务四：正序打印

要求调用：

print(5);

输出：

思考：

System.out.println() 应该放在递归调用前还是递归调用后？

这个任务非常适合理解：

递归深入
+
递归返回

的区别。

7.4 Debug

Bug 一

public static int sum(int n) {

    return n + sum(n - 1);
}

分析：

缺少什么？
最终会发生什么？

Bug 二

public static int sum(int n) {

    if (n == 1) {
        return 1;
    }

    return n + sum(n + 1);
}

分析：

有出口为什么仍然错误？

Bug 三

public static int sum(int n) {

    if (n == 1) {
        return 1;
    }

    return n + sum(n - 2);
}

思考：

如果传入：

可能：

5 → 3 → 1

正常。

但如果传入：

会发生什么？

这个题用来理解：

出口必须覆盖递归过程真正可能到达的状态。

7.5 综合训练

请分析下面三个问题：

A. 计算 1~100 的和

B. 遍历一个未知深度的目录树

C. 对数组顺序打印所有元素

分别回答：

更推荐循环还是递归？

为什么？

递归是否更清晰？

递归深度可能是多少？

是否存在栈溢出风险？

重点不是：

所有问题都写成递归。

而是训练：

什么时候应该使用递归。

7.6 本章验收

你应该能够闭卷画出：

递归问题

     ┌───────────────┐
     │ 当前是否是出口？ │
     └───────┬───────┘
             │
        ┌────┴────┐
        │         │
       是         否
        │         │
        ▼         ▼
    直接返回   缩小问题规模
                  │
                  ▼
               调用自己
                  │
                  ▼
           必须向出口靠近

并能够完整解释：

递归调用阶段：

大问题
↓
小问题
↓
更小问题
↓
最简单问题

────────────

递归返回阶段：

最简单问题的答案
↑
组合上一层结果
↑
继续组合
↑
得到最终答案

最终验收：

[ ] 能闭卷定义递归。
[ ] 能区分直接递归和间接递归。
[ ] 能说出递归三要素。
[ ] 能独立写 sum(n)。
[ ] 能独立写 factorial(n)。
[ ] 能手画递归调用栈。
[ ] 能解释递归“深入 → 返回”。
[ ] 能 Debug 没有出口的递归。
[ ] 能 Debug 方向错误的递归。
[ ] 能解释 StackOverflowError。
[ ] 能判断简单问题是否更适合循环。
[ ] 已经理解为什么目录树适合递归。

一、学习目标

二、核心知识

2.1 什么是递归

2.2 直接递归

2.3 间接递归

2.4 为什么递归不是简单的“自己调用自己”

2.5 递归三要素

2.6 第一要素：递归关系

2.7 第二要素：终止条件

2.8 第三要素：必须不断接近终止条件

2.9 一个正确递归的标准模板

三、使用方法

3.1 使用递归计算 1 到 n 的和

3.2 不要先想着“代码怎么写”

3.3 使用递归计算阶乘

3.4 递归展开

3.5 然后开始逐层返回

四、原理与进阶

4.1 方法调用需要栈帧

4.2 普通方法的调用栈

4.3 递归只是方法调用的特殊情况

4.4 为什么递归可以保存每层不同的 n

4.5 什么是无限递归

4.6 有出口也可能栈溢出

4.7 即使递归正确，也不能无限深

4.8 递归的时间复杂度与空间复杂度

4.9 递归和循环不是谁取代谁

4.10 什么叫自相似问题

五、实践应用

5.1 用递归思维理解目录树

5.2 递归解决问题的标准分析流程

六、常见问题

6.1 递归是不是方法“重复执行”？

6.2 为什么必须有递归出口？

6.3 有出口为什么还会死递归？

6.4 StackOverflowError 是 Exception 吗？

6.5 所有循环都可以改成递归吗？

6.6 递归一定比循环慢吗？

6.7 Java 会自动把尾递归优化掉吗？

七、练习与验收

7.1 知识问答

7.2 代码阅读

7.3 手写代码

任务一：1 到 n 求和

任务二：阶乘

任务三：倒序打印

任务四：正序打印

7.4 Debug

Bug 一

Bug 二

Bug 三

7.5 综合训练

7.6 本章验收

6.4 `StackOverflowError` 是 Exception 吗？