本文講述了Java遞歸運(yùn)行的機(jī)制：遞歸的微觀解。分享給大家供大家參考，具體如下：

前言：在java遞歸基礎(chǔ)與遞歸的宏觀語意和java鏈表的天然遞歸結(jié)構(gòu)性質(zhì)中我們分別通過數(shù)組以及鏈表對(duì)遞歸進(jìn)行了應(yīng)用，那時(shí)我們只是對(duì)遞歸進(jìn)行了宏觀理解--遞歸是將問題化為更小問題的子過程。這一節(jié)我們對(duì)在4.1節(jié)中遞歸在數(shù)組中的應(yīng)用和4.2節(jié)中遞歸在鏈表中的應(yīng)用進(jìn)行微觀解讀：

一.關(guān)于4.1節(jié)中遞歸在數(shù)組中的應(yīng)用

1） 我們先來看看4.1節(jié)中的代碼實(shí)現(xiàn)，如下圖：

為了更好的進(jìn)行分析，我們將上述代碼的最后一句進(jìn)行拆分，拆分結(jié)果如下：

此時(shí) n=arr.length=2：

2）現(xiàn)在我們對(duì)已經(jīng)拆分的代碼進(jìn)行分析為此來說明：遞歸函數(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）方法，如下：

第二次調(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)用過程如下：

 當(dāng)調(diào)用sum(arr,2)時(shí)，由于此時(shí)已經(jīng)滿足了遞歸的基本條件，結(jié)果直接返回0，回到上一次中斷的位置，也就是下圖中調(diào)用sum(arr,1) 方法中的sum（arr,l+1）處，如下圖：

代碼從中斷處繼續(xù)向下執(zhí)行，返回arr[1]=10, x=0因此res=10,此時(shí)返回值為res=10;

此時(shí)代碼也將回到sum(arr,1)父親的調(diào)用中，也就是sum(arr,0)中。

代碼從中斷處繼續(xù)向下執(zhí)行，返回arr[0]=6, x=10因此res=16,此時(shí)返回值為res=16;

通過遞歸得到了我們最終的結(jié)果為16。

從上述的過程中印證了：遞歸函數(shù)的調(diào)用，本質(zhì)就是函數(shù)調(diào)用（自身函數(shù)）---也就是使用不同的參數(shù)，執(zhí)行相同的邏輯。

二、關(guān)于4.2節(jié)中遞歸在鏈表中的應(yīng)用（刪除鏈表中指定的所有元素值）

 1）我們先來看看4.2節(jié)中的代碼實(shí)現(xiàn)，如下圖：

為了分析的方便，我們對(duì)方法體中的代碼做一個(gè)簡(jiǎn)單的標(biāo)識(shí)1,2,3，結(jié)果如下圖：

 2）為了分析的簡(jiǎn)便，我們來進(jìn)行模擬調(diào)用，對(duì)6--->7--->8--->null 刪除元素為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的鏈表：

第二次調(diào)用：

此時(shí)鏈表的頭結(jié)點(diǎn)變?yōu)?，由于不滿足遞歸的基本結(jié)束條件，再一次觸發(fā)第三次調(diào)用，此時(shí)鏈表變?yōu)轭^結(jié)點(diǎn)為8的鏈表：

第三次調(diào)用：

 此時(shí)鏈表的頭結(jié)點(diǎn)變?yōu)?，由于不滿足遞歸的基本結(jié)束條件，再一次觸發(fā)第四次調(diào)用，此時(shí)鏈表變?yōu)榭真湵恚?/p>

第四次調(diào)用中，由于此時(shí)已經(jīng)滿足了遞歸的基本條件，回到上一次中斷的位置也就是2的位置，返回值為null，如下：

此時(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的鏈表。

然后繼續(xù)執(zhí)行第三步，此時(shí)鏈表7-->8-->null滿足刪除條件，也就是head.val=val=7,將執(zhí)行head.next,返回最終結(jié)果為8-->null，如下：

回到父級(jí)調(diào)用的中斷位置，得到的結(jié)果為6-->8--->null，然后執(zhí)行第三步代碼,判斷此時(shí)的鏈表的head.val是否等于val=7,此時(shí)的鏈表不滿足，直接返回head，也就是6--8-->null

 到此遞歸調(diào)用得以結(jié)束，完成過程如下：

遞歸的調(diào)用是由代價(jià)的：函數(shù)調(diào)用（時(shí)間開銷）+系統(tǒng)棧空間,但是使用遞歸書寫邏輯是更為簡(jiǎn)單的。

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

最新評(píng)論