Java递归运行的机制:递归的微观解读图文分析
作者:WFaceBoss 发布时间:2022-09-24 20:04:09
本文讲述了Java递归运行的机制:递归的微观解。分享给大家供大家参考,具体如下:
前言:在java递归基础与递归的宏观语意和java链表的天然递归结构性质中我们分别通过数组以及链表对递归进行了应用,那时我们只是对递归进行了宏观理解--递归是将问题化为更小问题的子过程。这一节我们对在4.1节中递归在数组中的应用和4.2节中递归在链表中的应用进行微观解读:
一.关于4.1节中递归在数组中的应用
1) 我们先来看看4.1节中的代码实现,如下图:
为了更好的进行分析,我们将上述代码的最后一句进行拆分,拆分结果如下:
此时 n=arr.length=2:
2)现在我们对已经拆分的代码进行分析为此来说明:递归函数的调用,本质就是函数调用。
为了分析简单,我们使用只有两个元素的数组 arr=[6,10]
第一次调用:sum(arr,0)
使用sun(arr,0)进行调用,进入方法体之后,由于不满足递归的基本条件,进而继续调用sum(arr,1)方法,如下:
第二次调用:sum(arr,1)
使用sun(arr,1)进行调用,进入方法体之后,由于不满足递归的基本条件,进而继续调用sum(arr,2)方法,此时调用过程如下:
当调用sum(arr,2)时,由于此时已经满足了递归的基本条件,结果直接返回0,回到上一次中断的位置,也就是下图中调用sum(arr,1) 方法中的sum(arr,l+1)处,如下图:
代码从中断处继续向下执行,返回arr[1]=10, x=0因此res=10,此时返回值为res=10;
此时代码也将回到sum(arr,1)父亲的调用中,也就是sum(arr,0)中。
代码从中断处继续向下执行,返回arr[0]=6, x=10因此res=16,此时返回值为res=16;
通过递归得到了我们最终的结果为16。
从上述的过程中印证了:递归函数的调用,本质就是函数调用(自身函数)---也就是使用不同的参数,执行相同的逻辑。
二、关于4.2节中递归在链表中的应用(删除链表中指定的所有元素值)
1)我们先来看看4.2节中的代码实现,如下图:
为了分析的方便,我们对方法体中的代码做一个简单的标识1,2,3,结果如下图:
2)为了分析的简便,我们来进行模拟调用,对6--->7--->8--->null 删除元素为7的节点。
注意:下面的分析中我们使用1,2,3这样的编号,表示代码执行到的位置
第一次调用:
首先传入头结点为6的链表,由于不满足递归的基本结束条件,再一次触发第二次调用,此时链表变为头结点为7的链表:
第二次调用:
此时链表的头结点变为7,由于不满足递归的基本结束条件,再一次触发第三次调用,此时链表变为头结点为8的链表:
第三次调用:
此时链表的头结点变为8,由于不满足递归的基本结束条件,再一次触发第四次调用,此时链表变为空链表:
第四次调用中,由于此时已经满足了递归的基本条件,回到上一次中断的位置也就是2的位置,返回值为null,如下:
此时的链表为头结点为8的链表,如上图黄色区域,执行第三步代码之后,返回的结果为为头结点为8的链表,即为8-->null,并将该结果返回到上一步调用,也就是标号为2的地方,得到结果为7-->8-->null的链表。
然后继续执行第三步,此时链表7-->8-->null满足删除条件,也就是head.val=val=7,将执行head.next,返回最终结果为8-->null,如下:
回到父级调用的中断位置,得到的结果为6-->8--->null,然后执行第三步代码,判断此时的链表的head.val是否等于val=7,此时的链表不满足,直接返回head,也就是6--8-->null
到此递归调用得以结束,完成过程如下:
递归的调用是由代价的:函数调用(时间开销)+系统栈空间,但是使用递归书写逻辑是更为简单的。
希望本文所述对大家java程序设计有所帮助。
来源:https://www.cnblogs.com/wfaceboss/p/10667325.html
猜你喜欢
- 在实际的应用中会经常需要将数据导出成excel,导出的方式除原样导出还有分页导出、分页分sheet导出和大数据量导出。对于excel2003
- 在我们编程过程中如果需要执行一些简单的定时任务,无须做复杂的控制,我们可以考虑使用JDK中的Timer定时任务来实现。下面LZ就其原理、实例
- 以往都是使用反射调用实例方法,那么反射如何调用静态方法呢?看下面的例子Class<?> threadClazz = Class.
- 前面我们完成了与商品类别相关的业务逻辑,接下来我们开始做具体商品部分。1. 数据库建表并映射Model首先我们在数据库中新建一张表,然后使用
- 前言上一篇分析了事务注解的解析过程,本质上是将事务封装为切面加入到AOP的执行链中,因此会调用到MethodInceptor的实现类的inv
- 这篇文章主要介绍了如何通过SpringBoot实现商城秒杀系统,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 前言自从国产之光fastjson频频暴雷,jackson json的使用是越来越广泛了。尤其是spring家族把它搞成了默认的JSON处理包
- 前言最近发现公司的微服务项目中没有统一的批量新增方法,公司用的是MP插件,遇到批量新增都是单独去去编写xml实现,费时费力,而MP自带的批插
- 前言:由于项目需求,短信验证码的接口需要换成阿里大于的,但是尴尬的发现阿里大于的jar包没有maven版本的,于是便开始了一上午的 * 引包之
- 今天在面试时遇到一道算法的题:给定一个字符串,输出每次字符出现的次数;要求按照顺序输出;自己的思路开始是:1.把String转换char数组
- 基本原理:利用URLConnection获取要下载文件的长度、头部等相关信息,并设置响应的头部信息。并且通过URLConnection获取输
- 首先,良好的编码规范非常重要。在 java 程序中,访问速度、资源紧张等问题的大部分原因,都是代码不规范造成的。单例的使用场景单例模式对于减
- 本文实例讲述了Android中断线程的处理方法。分享给大家供大家参考。具体方法如下:我现在对一个用户注册的功能1.用ProgressDial
- 目录前言错误实例演示实现ApplicationContextAware接口lookup methodlookup method签名总结前言看
- Java中提供了大数字(超过16位有效位)的操作类,即 java.math.BinInteger 类和 java.math.BigDecim
- Gradle修改默认的Build配置文件名Gradle默认使用build.gradle作为默认的配置文件文件名。如果我们在build.gra
- 一、需求场景有时候我们需要在项目中使用一些静态资源文件,比如城市信息文件 countries.xml,在项目启动后读取其中的数据并初始化写进
- 对 Debug 的好奇初学 Java 时,我对 IDEA 的 Debug 非常好奇,不止是它能查看断点的上下文环境,更神奇的是我可以在断点处
- 一、什么是外观模式定义:为子系统中的一组接口提供一个一致的界面,用来访问子系统中的一群接口。外观模式组成:Facade:负责子系统的的封装调
- 前言MyBatis-Plus 是基于 MyBatis 进行封装的一套优秀的持久层框架,它提供了丰富的便捷操作方法和强大的代码生成器,大大简化