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程序设计有所帮助。

赞 (0)

相关推荐

  • Java链表（Linked List）基本原理与实现方法入门示例

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

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

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

  • Java方法递归调用实例解析

    Java方法递归调用实例解析

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

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

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

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

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

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

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

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

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

  • java链表应用--基于链表实现队列详解（尾指针操作）

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

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

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

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

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

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

  • 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

随机推荐