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

前言：在4.1节和4.2节中我们分别通过数组以及链表对递归进行了应用，那时我们只是对递归进行了宏观理解--递归是将问题化为更小问题的子过程。这一节我们对在4.1节中递归在数组中的应用和4.2节中递归在链表中的应用进行微观解读：

一.关于4.1节中递归在数组中的应用

1） 我们先来看看4.1节中的代码实现，如下图：

image.png
为了更好的进行分析，我们将上述代码的最后一句进行拆分，拆分结果如下：
image.png
此时 n=arr.length=2：
image.png
2）现在我们对已经拆分的代码进行分析为此来说明：递归函数的调用，本质就是函数调用。
为了分析简单，我们使用只有两个元素的数组 arr=[6,10]
第一次调用：sum(arr,0)
使用sun(arr,0)进行调用，进入方法体之后，由于不满足递归的基本条件，进而继续调用sum（arr,1）方法，如下：
image.png
第二次调用：sum(arr,1)
使用sun(arr,1)进行调用，进入方法体之后，由于不满足递归的基本条件，进而继续调用sum（arr,2）方法，此时调用过程如下：
image.png
当调用sum(arr,2)时，由于此时已经满足了递归的基本条件，结果直接返回0，回到上一次中断的位置，也就是下图中调用sum(arr,1)方法中的sum（arr,l+1）处，如下图：
image.png

代码从中断处继续向下执行，返回arr[1]=10, x=0因此res=10,此时返回值为res=10;

image.png
此时代码也将回到sum(arr,1)父亲的调用中，也就是sum(arr,0)中。
image.png
代码从中断处继续向下执行，返回arr[0]=6, x=10因此res=16,此时返回值为res=16;
image.png
通过递归得到了我们最终的结果为16。
从上述的过程中印证了：递归函数的调用，本质就是函数调用（自身函数）---也就是使用不同的参数，执行相同的逻辑。

二、关于4.2节中递归在链表中的应用（删除链表中指定的所有元素值）

1）我们先来看看4.2节中的代码实现，如下图：

image.png
为了分析的方便，我们对方法体中的代码做一个简单的标识1,2,3，结果如下图：
image.png
2）为了分析的简便，我们来进行模拟调用，对6--->7--->8--->null 删除元素为val=7的节点。
注意：下面的分析中我们使用1,2,3这样的编号，表示代码执行到的位置
第一次调用：
首先传入头结点为6的链表，由于不满足递归的基本结束条件，再一次触发第二次调用，此时链表变为头结点为7的链表：
image.png
第二次调用：
此时链表的头结点变为7，由于不满足递归的基本结束条件，再一次触发第三次调用，此时链表变为头结点为8的链表：
image.png
第三次调用：
此时链表的头结点变为8，由于不满足递归的基本结束条件，再一次触发第四次调用，此时链表变为空链表：
image.png
第四次调用中，由于此时已经满足了递归的基本条件，回到上一次中断的位置，返回值为null，如下：
image.png
此时的链表为头结点为8的链表，如上图黄色区域，执行第三步代码之后，返回的结果为为头结点为8的链表，即为8-->null，并将该结果返回到上一步调用，也就是标号为2的地方，得到结果为7-->8-->null的链表。
image.png
然后继续执行第三步，此时链表7-->8-->null满足删除条件，也就是head.val=val=7,将执行head.next,返回最终结果为8-->null，如下：
image.png
回到父级调用的中断位置，得到的结果为6-->8--->null，然后执行第三步代码,判断此时的链表的head.val是否等于val=7,此时的链表不满足，直接返回head，也就是6--8-->null
image.png
到此递归调用得以结束，完成过程如下：
image.png
递归的调用是由代价的：函数调用（时间开销）+系统栈空间,但是使用递归书写逻辑是更为简单的。