【Java方法】--递归的正确使用方法，告别栈溢出-深圳市維司達科技有限公司

个人主页

- 前言
- 💡1.什么是递归？
- - 1.1 递归的两个关键要素
  - 1.2 递归结构：
- 2.经典的递归
- - 2.1 案例一：阶乘计算
  - 2.2 案例二：斐波那契数列
  - 2.3 目录遍历
- 3.深入理解递归为什么会栈溢出
- - 3.1 什么是栈？
  - - Java 虚拟机栈
    - 结合之前的阶乘例子看栈的变化
  - 3.2 什么是栈溢出？
  - - 为什么会发生栈溢出？
  - 3.3 如何避免栈溢出？
- 4.结尾

前言

想象一下，你站在一面大镜子前，手里还拿着一个小镜子。你就会发现大镜子里有小镜子，小镜子里又有大镜子，无限循环…这就是递归的直观感受！
递归的本质就是一个方法调用自身来解决问题
本章将快速帮助你掌握Java方法中的递归是什么该怎么用？

💡1.什么是递归？

递归是指一个方法在其定义中直接或间接地调用自身。就是“自己调用自己”。

递归的核心思想是：将一个复杂的大问题分解成一个或者多个与原问题相似，但规模更小的子问题来解决。

就像套娃一样，一个大娃娃里面装着一个一摸一样的小娃娃，小娃娃里面又装着更小的娃娃……直到最小的那个娃娃不能再打开为止。

1.1 递归的两个关键要素

基线要素（Base Case）
- 停止递归的条件
- 相当于套娃里最小的那个娃娃，不能再打开了
递归条件（Recursive Case）
- 继续调用自身的条件
- 还没找到最小娃娃，继续打开下一个

1.2 递归结构：

递归结构包括两个结构：
- 递归头：什么时候不调用自身方法。如果没有头，将陷入死循环。
- 递归体：什么时候需要调用自身方法。

2.经典的递归

2.1 案例一：阶乘计算

**问题：**计算5!= 5 x 4 x 3 x 2 x 1

递归思路：

5! = 5 × 4! 4! = 4 × 3! 3! = 3 × 2! 2! = 2 × 1! 1! = 1 (这就是基线条件！)

实战：

publicclassFactorial{publicstaticintfactorial(intn){// 基线条件：1的阶乘是1if(n==1){return1;}// 递归条件：n的阶乘 = n × (n-1)的阶乘returnn*factorial(n-1);}publicstaticvoidmain(String[]args){System.out.println("5的阶乘是："+factorial(5));// 输出：120}}

执行过程：

factorial(5) → 5 × factorial(4) factorial(4) → 4 × factorial(3) factorial(3) → 3 × factorial(2) factorial(2) → 2 × factorial(1) factorial(1) → 1 (基线条件，开始返回) 然后逐层返回：2×1=2, 3×2=6, 4×6=24, 5×24=120

2.2 案例二：斐波那契数列

**问题：**1，1，2，3，5，8，13…每个数是前两个数之和

递归思路：

fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) fib(3) = fib(2) + fib(1) fib(2) = 1 (基线条件) fib(1) = 1 (基线条件)

实战：

publicclassFibonacci{publicstaticintfib(intn){// 基线条件：前两项都是1if(n==1||n==2){return1;}// 递归条件：当前项 = 前两项之和returnfib(n-1)+fib(n-2);}publicstaticvoidmain(String[]args){for(inti=1;i<=10;i++){System.out.print(fib(i)+" ");// 输出：1 1 2 3 5 8 13 21 34 55}}}

2.3 目录遍历

**问题：**计算一个文件夹及其所有子文件夹中的文件总数

实战：

importjava.io.File;publicclassDirectoryCounter{publicstaticintcountFiles(Filedirectory){// 基线条件：如果是文件，返回1if(directory.isFile()){return1;}// 递归条件：如果是文件夹，遍历其内容intcount=0;File[]files=directory.listFiles();if(files!=null){for(Filefile:files){count+=countFiles(file);// 递归调用}}returncount;}publicstaticvoidmain(String[]args){Filedir=newFile("C:\\Users\\QuienFun\\Documents");System.out.println("文件总数："+countFiles(dir));}}

3.深入理解递归为什么会栈溢出

3.1 什么是栈？

在计算机中，栈是一种遵循LIFO原则的数据结构，即后进先出。

想象一个堆叠的盘子：你只能从最顶部拿走或放入一个盘子。最后放上去的盘子，会最先被拿走。
或者说一堆叠放的书：你只能从最上面取书或放书。

在 Java（或者说大多数编程语言）的程序运行时环境中，有一个非常重要的内存区域叫做“调用栈”。

Java 虚拟机栈

每当一个线程开始运行时，JVM 都会为它分配一块私有的内存空间，其中就包括Java 虚拟机栈。这个栈用于跟踪每个方法的调用。

工作原理：

方法调用：当一个方法（比如main方法）被执行时，JVM 会在栈顶为这个方法创建一个新的内存块，称为“栈帧”。
栈帧内容：这个栈帧里存储了关于这次方法调用的所有信息：
- 局部变量：方法内部声明的变量。
- 操作数栈：用于执行字节码指令时的临时数据存储。
- 动态链接：指向运行时常量池中该方法的引用。
- 方法返回地址：方法执行完毕后，应该回到哪里继续执行。
方法结束：当方法执行完毕（遇到return语句或执行到最后），它的栈帧就会被销毁，从栈顶弹出。程序的控制权会返回到调用它的地方（即上一个栈帧中记录的返回地址）。

这个过程就像一个栈的操作：

push：调用方法，压入一个新的栈帧。
pop：方法结束，弹出栈帧。

结合之前的阶乘例子看栈的变化

让我们用factorial(3)来可视化栈的变化过程：

步骤	栈状态 (栈底 -> 栈顶)	说明
1	`[main]`	程序开始，`main`方法入栈。
2	`[main, factorial(3)]`	`main`调用`factorial(3)`，`factorial(3)`的栈帧被压入。
3	`[main, factorial(3), factorial(2)]`	`factorial(3)`调用`factorial(2)`，`factorial(2)`入栈。
4	`[main, factorial(3), factorial(2), factorial(1)]`	`factorial(2)`调用`factorial(1)`，`factorial(1)`入栈。
5	`[main, factorial(3), factorial(2)]`	`factorial(1)`达到基准情况，返回`1`。它的栈帧被弹出销毁。
6	`[main, factorial(3)]`	`factorial(2)`得到结果`2*1=2`，返回`2`。它的栈帧被弹出销毁。
7	`[main]`	`factorial(3)`得到结果`3*2=6`，返回`6`。它的栈帧被弹出销毁。
8	`[main]`	`main`方法继续执行，最终结束。

3.2 什么是栈溢出？

栈溢出是指程序运行过程中，调用栈的大小超过了系统所分配给它的内存限制。

当发生栈溢出时，JVM 会抛出一个错误：java.lang.StackOverflowError。

为什么会发生栈溢出？

最主要的原因就是无限递归或递归深度过大。

无限递归：如果一个递归函数缺少了正确的基准情况，或者基准情况永远无法达到，那么它就会无休止地调用自己。每一次调用都会在栈上创建一个新的栈帧，栈空间会被迅速耗尽，最终导致StackOverflowError。
```
// 栈溢出publicstaticvoidinfiniteRecursion(){infiniteRecursion();// 没有基准情况，永远在调用自己}
```
递归深度过大：即使有正确的基准情况，但如果要解决的问题规模非常大，递归的深度也会非常深。例如，计算factorial(100000)。虽然逻辑上正确，但100,000个栈帧会轻易超过默认的栈大小限制。

3.3 如何避免栈溢出？

确保基准情况正确并且可以到达
使用循环（迭代）代替递归
使用尾递归优化：这是一种特殊的递归形式，不过，标准的 Java 编译器（javac）目前并不支持尾递归优化，所以这里不过多讲解（学习它的思路）。
什么是尾递归？
尾递归是指递归调用是函数体中最后执行的语句，并且返回值不被修改。这样，编译器就可以重用当前的栈帧，而不是创建一个新的。
普通递归（非尾递归）：
```
// 在 return 之后还有一个乘法操作 n * ...returnn*factorial(n-1);
```
这里，在计算factorial(n-1)之前，必须先知道n的值，所以必须保留当前栈帧来等待结果。
尾递归版本：
```
publicstaticlongfactorialTailRecursive(intn){returnfactorialHelper(n,1);}// 辅助方法，accumulator 是累积器，用于存储中间结果privatestaticlongfactorialHelper(intn,longaccumulator){// 基准情况if(n==0){returnaccumulator;}// 尾递归调用：它是最后一步操作，并且把结果直接返回else{returnfactorialHelper(n-1,n*accumulator);}}
```
在这串代码中，factorialHelper(n-1, n * accumulator)是最后一步，JVM 理论上可以优化它，不创建新栈帧。但由于 Java 标准编译器不支持，它仍然会栈溢出。但在支持的语言中，这就避免了栈溢出的问题。
增加栈大小：作为最后的手段，可以通过 JVM 参数-Xss来增加每个线程的栈大小。例如，-Xss2m将栈大小设置为 2MB。但这只是延迟了问题，并没有从根本上解决无限递归或大深度递归的效率问题。