Java基础—递归方法

范栖荣

已于 2023-03-09 07:55:05 修改

阅读量655

点赞数

文章标签： java jvm 算法

于 2023-03-07 03:03:25 首次发布

本文链接： https://blog.csdn.net/m0_46521939/article/details/129353703

版权

什么是递归

一个方法调用自己的方法，方法的递归调用可以重复执行一段代码，看完下面的例子，相信你对递归会有深入的了解：

package Class.Recursion;

public class Demo_Sum {
        public static void main(String[] args) {
            //求1-3的累加和
            int n = sum_recursion(1,3);
            System.out.println(n);
        }

        //实现数据区间的累加和方法
        public static int sum_recursion(int start,int end){
            //出口条件
            if (start == end) {
                return end;
            }
            //递归调用
            return start + sum_recursion(start+1,end);
        }
}

结果：

下边研究一下sum_recursion方法的递归执行流程，见下图：

步骤讲解：
1）main方法调用sum_recursion方法，传入1，3；

2）sum_recursion方法调用sum_recursion方法，传入2,3；

3）sum_recursion方法调用sum_recursion方法，传入3,3；

4）sum_recursion方法判断start等于end，返回3给上个调用者；

5）sum_recursion方法返回2+3给上个调用者；

6）sum_recursion方法返回1+2+3给main方法。

我们发现方法的递归调用和方法之间的调用流程是一样，只不过递归调用是调用自己。

如果sum_recursion方法中没有下边的语句将会有什么结果：
StackOverflowError表示“栈溢出”错误。
为什么递归方法调用会抛出StackOverflowError栈溢出错误呢？下面我们分析这个问题，首先我们来了解一下执行方法的原理：

栈帧

每次执行一个方法会在JVM栈中开辟一块内存，用于存放执行方法所需要的数据，比如方法的局部变量、对象引用等，这块内存叫栈帧。JVM栈是JVM运行时内存的一个区域，JVM运行时内存还包括堆、方法区、程序计数器等区域。

栈：是一种数据结构，具有后进先出的特点，下面引用百度百科的栈的模型图来说明栈的特点：

对栈的操作包括入栈（也叫压栈）和出栈（也叫弹栈）两个。

入栈是将数据压到栈顶，如上图，首先将a1压入栈，再将a2压入栈，直到将an压入栈，最上边位置叫栈顶，最下边的是栈底，上图an为栈顶元素，a1为栈底元素。

出栈是将数据从栈中弹出，出栈是要弹出的栈顶的元素。

所以，栈的特点是后进先出，先进后出，如上图，an最后入栈，却最先出栈，a1最先入栈却最后出栈。

理解了栈的特点，我们再结合JVM栈和方法执行过程，对应的栈内存结构的变化过程如下：

压栈是每执行一次方法会创建一个栈帧，每一次的递归调用都会压栈。当方法执行完执行出栈。上述列子中从执行main方法开始，当start等于end时方法执行return 1，即执行方法的出口，此时出栈，直到执行完成main，main方法出栈，程序运行结束，见下图：

为什么方法递归调用会抛出StackOverflowError栈溢出错误呢？