4.3递归运行的机制:递归的微观解读

前言:在4.1节和4.2节中我们分别通过数组以及链表对递归进行了应用,那时我们只是对递归进行了宏观理解--递归是将问题化为更小问题的子过程。这一节我们对在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

 

 到此递归调用得以结束,完成过程如下:

 

递归的调用是由代价的:函数调用(时间开销)+系统栈空间,但是使用递归书写逻辑是更为简单的。

 

 关于本小节,若您觉得还行、还过得去,记得给个推荐哦~,谢谢!!

人已赞赏
随笔日记

为什么我们要做单元测试?(二)

2020-11-9 4:14:47

随笔日记

CentOS7.0小随笔——指令基本操作(Part.B)

2020-11-9 4:14:49

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索