Java递归运行的机制:递归的微观解读图文分析

本文讲述了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算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

时间:2020-03-19

Java链表中元素删除的实现方法详解【只删除一个元素情况】

本文实例讲述了Java链表中元素删除的实现方法.分享给大家供大家参考,具体如下: 该部分与上一节是息息相关的,关于如何在链表中删除元素,我们一步一步来分析: 一.图示删除逻辑 假设我们需要在链表中删除索引为2位置的元素,此时链表结构为: 若要删除索引为2位置的元素,需要获取索引为2位置的元素之前的前置节点(此时为索引为1的位置的元素),因此我们需要设计一个变量prev来记录前置节点. 1.初始时变量prev指向虚拟头结点dummyHead: 2.寻找到前置节点位置,(对于该例子前置节点为索引为1

java链表应用–基于链表实现队列详解(尾指针操作)

本文实例讲述了java基于链表实现队列.分享给大家供大家参考,具体如下: 在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1). 一.链表改进分析 对于队列这种数据结构,需要在线性结构的一端插入元素,另外一端删除元素.因此此时基于链表来实现队列,则有一端的时间复杂度为O(n).因此我们不能使用之前已经实现的链表结构,我们需要改进我们的链表.思路如下: 1.参考在链表头部删除.增加元素的时间复杂度为O(1)的思路,我们在链表的尾部设立一个Node型的

Java基于链表实现栈的方法详解

本文实例讲述了Java基于链表实现栈的方法.分享给大家供大家参考,具体如下: 在上几小节中我们实现了基本的链表结构,并在上一节的底部给出了有关链表的源码,此处在贴一次吧,猛戳 在开始栈的实现之前,我们再来看看关于链表的只在头部进行的增加.删除.查找操作,时间复杂度均为O(1),基于链表的这几个优势,我们在此基础上实现栈. 前言,在写本小节之前,我们已经实现了一个基于静态数组的栈,转到查看.此处我们实现基于链表的栈. 1.链表类拷贝到Stack 包下: 在实现基于静态数组的栈的时候,我们已经新建了

Java实现链表中元素的获取、查询和修改方法详解

本文实例讲述了Java实现链表中元素的获取.查询和修改方法.分享给大家供大家参考,具体如下: 本节是在上一小节Java链表中添加元素的基础上继续完善我们的链表相关方法的编写,在本节中我们着重对如何获取链表中元素.查询元素以及修改元素进行学习. 一.获取元素 1.关于获取链表中元素的方法的分析 由于我们使用了虚拟头结点,而我们每次都需要从第一个真实节点开始,因此需要首先得到虚拟头结点的下一个节点是谁,然后在此基础上进行遍历工作,相关代码如下: //获取链表的第index(0-based)个位置的元

Java递归基础与递归的宏观语意实例分析

本文实例讲述了Java递归基础与递归的宏观语意.分享给大家供大家参考,具体如下: 1.什么是递归 本质上,将原来的问题,转化为更小的同一问题 2.例子分析 假设我们需要对数组进行求和操作(只是为了更好理解递归程序) 要求如下:求解从索引为0到n-1的数组元素和. 分析: 为了能求解从索引为0到n-1的数组元素和,可以分解为第0个数加上索引从1到n-1的数组元素和,如下: 此时求解索引从1到n-1的数组元素和的规模比求解从索引为0到n-1的数组元素和要少一个数以此类推,如下: ……. 最基

Java链表中添加元素的原理与实现方法详解

本文实例讲述了Java链表中添加元素的原理与实现方法.分享给大家供大家参考,具体如下: 1.链表中头节点的引入 1.1基本的链表结构: 1.2对于链表来说,若想访问链表中每个节点则需要把链表的头存起来,假如链表的头节点为head,指向链表中第一个节点,如图: 1.3使用代码表示此时的链表 //定义头节点 private Node head; //节点个数 private int size; //无参数构造函数 public LinkedList() { head = null; size = 0

java递归算法的实例详解

递归三要素: 1.明确递归终止条件: 2.给出递归终止时的处理办法: 3.提取重复的逻辑,缩小问题规模. 1.1+2+3+-+n import java.util.Scanner; public class Recursion { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(sum(n)); } publ

Java链表的天然递归结构性质图文与实例分析

本文实例分析了Java链表的天然递归结构性质.分享给大家供大家参考,具体如下: 有关链表,参考之前的文章学习. 要求:使用递归删除链表中指定的所有元素值. 一.图文分析 假设有这么一个链表,如下图: 分析:基于链表的宏观语意(递归是问题更小的子过程)进行分析 我们可以把上述链表看成是一个头结点后面挂接了一个更小的链表组成,如下图: 此时我们可以把链表概括成如下的链表结构: 1.在一个头结点+更小的链表基础上,从更小的链表中删除指定元素,得到一个全新的链表–图中红丝的方块. 此时我们需要关心如何

Java链表(Linked List)基本原理与实现方法入门示例

本文实例讲述了Java链表(Linked List)基本原理与实现方法.分享给大家供大家参考,具体如下: 在分析链表之前,我们先来对之前的动态数组.栈.队列总结一下: (1)底层依托于静态数组 (2)依靠resize解决固定容量问题 (3)是一种假的的动态数据结构 1.什么是链表 可以从以下两个部分来理解什么是链表 (1)最简单的动态数据结构,是一种真正的动态数据结构: (2)是一种数据的存储方式,数据存储在"节点"(Node)中 1.1结构基本代码: class Node{ E e;

如何实现java递归 处理权限管理菜单树或分类

这篇文章主要介绍了如何实现java递归 处理权限管理菜单树或分类,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.数据库表设计 2.实体类设计 package com.ieou.capsule.dto.SystemPermissions; import java.util.List; /** * 功能菜单类 */ public class SystemPermissionsTree { private String functionCode;

Java方法递归调用实例解析

这篇文章主要介绍了Java方法递归调用实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 /* 关于方法的递归调用 1.什么是递归? -方法自身调用自身 a(){ a(){ } } 2.递归是很耗费栈内存的,递归算法可以不用的时候尽量不用 3.一下程序运行的时候发生了这样一个错误[不是异常,是错误Error]: java.lang.StackOverflowErroe 栈内存溢出错误. 错误放生无法挽回,只有一个结果,就是JVM停止工作 4

Java Web开发入门书籍实例解析(总结一)

Java递归运行的机制:递归的微观解读图文分析

从事Java Web开发这一段时间来,对Java 面向对象的思想和MVC开发模式可以说已经熟悉了.我当前参与的项目使用的框架是Spring.SpringMVC.Hibernate.下面我们小编给大家整理一篇教程帮助大家学习javaweb相关知识,感兴趣的朋友可以参考下. 一.基本概念 1.1.WEB开发的相关知识 WEB,在英语中web即表示网页的意思,它用于表示Internet主机上供外界访问的资源. Internet上供外界访问的Web资源分为: 1.静态web资源(如html 页面):指w

Java数组越界问题实例解析

Java中数组初始化和OC其实是一样的,分为动态初始化和静态初始化, 动态初始化:指定长度,由系统给出初始化值 静态初始化:给出初始化值,由系统给出长度 在我们使用数组时最容易出现的就是数组越界问题,好了,这里有个简单的例子 int [][] array = {{1,2,3},{1,4}}; System.out.println(array[1][2]); 这是一个二维数组,很明显,数组越界了,控制台中会打印如下信息: Exception in thread "main" java.l

java ThreadPoolExecutor 并发调用实例详解

java ThreadPoolExecutor 并发调用实例详解 概述 通常为了提供任务的处理速度,会使用一些并发模型,ThreadPoolExecutor中的invokeAll便是一种. 代码 package test.current; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.concurrent.Callable; import java.util

Java中递归原理实例分析

Java递归运行的机制:递归的微观解读图文分析

本文实例分析了Java中递归原理.分享给大家供大家参考.具体分析如下: 解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合.   递归的三

DWR中各种java方法的调用

DWR是一个框架,简单的说就是能够在javascript直接调用java方法,而不必去写一大堆的javascript代码.它的实现是基于ajax的,可以实现无刷新效果. 网上有不少DWR的例子,但大都只是某种方法的调用,本文只在使用层面上介绍DWR,并不涉更多的技术与设计,其目的是让初学者能够很快的学会各种java方法在javascript中是如何调用的. 一.dwr配置篇之web.xml 1.最小配 <servlet> <servlet-name>dwr-invoker</

JAVA实现异步调用实例代码

在JAVA平台,实现异步调用的角色有如下三个角色: 调用者 取货凭证   真实数据 一个调用者在调用耗时操作,不能立即返回数据时,先返回一个取货凭证.然后在过一断时间后凭取货凭证来获取真正的数据. 在调用一个方法的时候,程序会进入被调用方法体内,执行完这个被调用方法后,才返回执行下一条语句.怎么做到像ajax异步请求一样,发送请求后,没等请求响应就执行下一条语句呢?对于java的异步请求,找了许多教材都没有找到,如thinking in java.core java2 ……等等.受多线程

Java多线程中关于join方法的使用实例解析

先上代码 新建一个Thread,代码如下: package com.thread.test; public class MyThread extends Thread { private String name; public MyThread(String name) { this.name = name; } @Override public void run() { for (int i = 0; i < 100; i++) { System.out.println(name+"[&

Java连接Oracle数据库实例解析

Java递归运行的机制:递归的微观解读图文分析

数据库的操作是当前系统开发必不可少的开发部分之一,尤其是在现在的大数据时代,数据库尤为重要.但是你真的懂得Java与数据库是怎么连接的么? 先给大家一个数据库连接的简单实例: package com.java.dbtest; import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatement; import java.sql.ResultSet; import java.sql.

JS 操作Array数组的方法及属性实例解析

本文总结了Array数组的3个属性,length 属性.prototype 属性.constructor 属性使用,并附注数组对象的8个分类及多个方法使用,具体如下: 对象的3个属性1.length 属性 length 属性Length属性表示数组的长度,即其中元素的个数.因为数组的索引总是由0开始,所以一个数组的上下限分别是:0和length-1.和其他大多数不同的是,JavaScript数组的length属性是可变的,这一点需要特别注意.当length属性被设置得更大时,整个数组的状态事实上

java中利用反射调用另一类的private方法的简单实例

我们知道,Java应用程序不能访问持久化类的private方法,但Hibernate没有这个限制,它能够访问各种级别的方法,如private, default, protected, public. Hibernate是如何实现该功能的呢?答案是利用JAVA的反射机制,如下: import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; public class ReflectDemo {

原文 

https://www.zhangshengrong.com/p/Mr1WJxRQXG/

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java递归运行的机制:递归的微观解读图文分析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址