学习任务:

视频学习方法栈

动手测试程序理解方法栈

是用递归还是用循环?

前边使用递归实现了求一个数据区间的累加和,代码如下:

import java.util.Scanner;

/**
 * 	面向过程编程-递归-入门
 * @author 攀博课堂(www.pbteach.com)
 *
 */
public class RecursionDemo1 {

	
    public static void main(String[] args) {
    	//求1到3累加和
    	int x = sum_recursion(1, 3);
    	System.out.println(x);
    }
    
    //求几个数的累加和,使用递归
    public static int sum_recursion(int start,int end) {
    	if(start == end) {
    		//返回具体的值
    		return end;
    	}
    	//仍然递归调用
    	return start+sum_recursion(start+1, end);
    }
    //使用循环实现累加和
    public static int sum(int start,int end) {
    	int sum = 0;
		for(int i = start;i<=end;i++) {
			sum +=i;
		}
		return sum;
	}
}

if(start == end) 代码是递归方法的出口,当释掉这段代码运行程序,报错如下:

Exception in thread "main" java.lang.StackOverflowError
	at RecursionDemo1.sum_recursion(RecursionDemo1.java:21)

为什么方法递归调用会抛出StackOverflowError栈溢出错误呢?下面我们分析这个问题。

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

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

image-20200807163545479

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

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

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

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

理解了栈的特点,我们再结合JVM栈,看一下方法执行过程。

下图是sum_recursion(int start,int end)方法的递归调用过程:

image-20210118105347237

对应的栈内存结构的变化过程如下:

压栈是每执行一次方法会创建一个栈帧,每一次的递归调用都会压栈,从执行main方法开始,见下图:

image-20210118145500480

方法执行完执行出栈,当start等于end时方法执行return 1,即执行方法的出口,此时出栈,直到执行完成main,main方法出栈,程序运行结束,见下图:

image-20210118145524371

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

当我们把方法的出口代码注释,递归调用将不停的在栈中创建栈帧,整个栈的深度会很大,如果超过了虚拟机要求的深度则报StackOverflowError错误。

所以对递归方法的定义一定要注意递归方法必须有出口。

一般情况下使用循环结构可以实现递归所实现的功能,只是有时候用递归写代码更明了,递归和循环结构有优劣分析如下:

递归:

优势:

1、代码结构简洁。

劣势:

1、耗费内存,每次调用需要开辟新的栈空间。

2、递归深度大会导致StackOverflowError。

循环结构:

优势:

1、速度快。

劣势:

1、有些场景单纯用循环结构不适合,比如:遍历磁盘中的所有目录及子目录中的所有文件,因为目录结构的复杂性用循环没有递归去遍历目录及子目录方便。

建议:能用循环解决的问题用循环解决,适合递归的场景要用递归解决。

提问-攀博课堂
我要提问 不会就问,有效沟通
关注公众号,加入微信群交流提问。 攀博课堂官方公众号
问答列表,查看本知识点所有问题