前言：在4.1節(jié)和4.2節(jié)中我們分別通過(guò)數(shù)組以及鏈表對(duì)遞歸進(jìn)行了應(yīng)用，那時(shí)我們只是對(duì)遞歸進(jìn)行了宏觀理解--遞歸是將問(wèn)題化為更小問(wèn)題的子過(guò)程。這一節(jié)我們對(duì)在4.1節(jié)中遞歸在數(shù)組中的應(yīng)用和4.2節(jié)中遞歸在鏈表中的應(yīng)用進(jìn)行微觀解讀：
一.關(guān)于4.1節(jié)中遞歸在數(shù)組中的應(yīng)用
1） 我們先來(lái)看看4.1節(jié)中的代碼實(shí)現(xiàn)，如下圖：
image.png
為了更好的進(jìn)行分析，我們將上述代碼的最后一句進(jìn)行拆分，拆分結(jié)果如下：
image.png
此時(shí) n=arr.length=2：
image.png
2）現(xiàn)在我們對(duì)已經(jīng)拆分的代碼進(jìn)行分析為此來(lái)說(shuō)明：遞歸函數(shù)的調(diào)用，本質(zhì)就是函數(shù)調(diào)用。
為了分析簡(jiǎn)單，我們使用只有兩個(gè)元素的數(shù)組
arr=[6,10]第一次調(diào)用：
sum(arr,0)使用
sun(arr,0)進(jìn)行調(diào)用，進(jìn)入方法體之后，由于不滿足遞歸的基本條件，進(jìn)而繼續(xù)調(diào)用sum（arr,1）方法，如下：
image.png
第二次調(diào)用：
sum(arr,1)使用
sun(arr,1)進(jìn)行調(diào)用，進(jìn)入方法體之后，由于不滿足遞歸的基本條件，進(jìn)而繼續(xù)調(diào)用sum（arr,2）方法，此時(shí)調(diào)用過(guò)程如下：
image.png
當(dāng)調(diào)用
sum(arr,2)時(shí)，由于此時(shí)已經(jīng)滿足了遞歸的基本條件，結(jié)果直接返回0，回到上一次中斷的位置，也就是下圖中調(diào)用sum(arr,1)方法中的sum（arr,l+1）處，如下圖：
image.png
代碼從中斷處繼續(xù)向下執(zhí)行，返回arr[1]=10, x=0因此res=10,此時(shí)返回值為res=10;
image.png
此時(shí)代碼也將回到
sum(arr,1)父親的調(diào)用中，也就是sum(arr,0)中。
image.png
代碼從中斷處繼續(xù)向下執(zhí)行，返回
arr[0]=6, x=10因此res=16,此時(shí)返回值為res=16;
image.png
通過(guò)遞歸得到了我們最終的結(jié)果為
16。從上述的過(guò)程中印證了：遞歸函數(shù)的調(diào)用，本質(zhì)就是函數(shù)調(diào)用（自身函數(shù)）---也就是使用不同的參數(shù)，執(zhí)行相同的邏輯。
二、關(guān)于4.2節(jié)中遞歸在鏈表中的應(yīng)用（刪除鏈表中指定的所有元素值）
1）我們先來(lái)看看4.2節(jié)中的代碼實(shí)現(xiàn)，如下圖：
image.png
為了分析的方便，我們對(duì)方法體中的代碼做一個(gè)簡(jiǎn)單的標(biāo)識(shí)1,2,3，結(jié)果如下圖：
image.png
2）為了分析的簡(jiǎn)便，我們來(lái)進(jìn)行模擬調(diào)用，對(duì)
6--->7--->8--->null 刪除元素為val=7的節(jié)點(diǎn)。注意：下面的分析中我們使用1,2,3這樣的編號(hào)，表示代碼執(zhí)行到的位置
第一次調(diào)用：
首先傳入頭結(jié)點(diǎn)為
6的鏈表，由于不滿足遞歸的基本結(jié)束條件，再一次觸發(fā)第二次調(diào)用，此時(shí)鏈表變?yōu)轭^結(jié)點(diǎn)為7的鏈表：
image.png
第二次調(diào)用：
此時(shí)鏈表的頭結(jié)點(diǎn)變?yōu)?code>7，由于不滿足遞歸的基本結(jié)束條件，再一次觸發(fā)第三次調(diào)用，此時(shí)鏈表變?yōu)轭^結(jié)點(diǎn)為
8的鏈表：
image.png
第三次調(diào)用：
此時(shí)鏈表的頭結(jié)點(diǎn)變?yōu)?code>8，由于不滿足遞歸的基本結(jié)束條件，再一次觸發(fā)第四次調(diào)用，此時(shí)鏈表變?yōu)榭真湵恚?br>
image.png
第四次調(diào)用中，由于此時(shí)已經(jīng)滿足了遞歸的基本條件，回到上一次中斷的位置，返回值為
null，如下：
image.png
此時(shí)的鏈表為頭結(jié)點(diǎn)為
8的鏈表，如上圖黃色區(qū)域，執(zhí)行第三步代碼之后，返回的結(jié)果為為頭結(jié)點(diǎn)為8的鏈表，即為8-->null，并將該結(jié)果返回到上一步調(diào)用，也就是標(biāo)號(hào)為2的地方，得到結(jié)果為7-->8-->null的鏈表。
image.png
然后繼續(xù)執(zhí)行第三步，此時(shí)鏈表
7-->8-->null滿足刪除條件，也就是head.val=val=7,將執(zhí)行head.next,返回最終結(jié)果為8-->null，如下：
image.png
回到父級(jí)調(diào)用的中斷位置，得到的結(jié)果為
6-->8--->null，然后執(zhí)行第三步代碼,判斷此時(shí)的鏈表的head.val是否等于val=7,此時(shí)的鏈表不滿足，直接返回head，也就是6--8-->null
image.png
到此遞歸調(diào)用得以結(jié)束，完成過(guò)程如下：
image.png
遞歸的調(diào)用是由代價(jià)的：函數(shù)調(diào)用（時(shí)間開(kāi)銷(xiāo)）+系統(tǒng)?？臻g,但是使用遞歸書(shū)寫(xiě)邏輯是更為簡(jiǎn)單的。
