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

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

一.關于4.1節(jié)中遞歸在數(shù)組中的應用

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

為了更好的進行分析，我們將上述代碼的最后一句進行拆分，拆分結果如下：

此時 n=arr.length=2：

2）現(xiàn)在我們對已經拆分的代碼進行分析為此來說明：遞歸函數(shù)的調用，本質就是函數(shù)調用。

 為了分析簡單，我們使用只有兩個元素的數(shù)組 arr=[6,10]

第一次調用：sum(arr,0)

使用sun(arr,0)進行調用，進入方法體之后，由于不滿足遞歸的基本條件，進而繼續(xù)調用sum（arr,1）方法，如下：

第二次調用：sum(arr,1)

 使用sun(arr,1)進行調用，進入方法體之后，由于不滿足遞歸的基本條件，進而繼續(xù)調用sum（arr,2）方法，此時調用過程如下：

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

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

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

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

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

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

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

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

為了分析的方便，我們對方法體中的代碼做一個簡單的標識1,2,3，結果如下圖：

 2）為了分析的簡便，我們來進行模擬調用，對6--->7--->8--->null 刪除元素為7的節(jié)點。

注意：下面的分析中我們使用1,2,3這樣的編號，表示代碼執(zhí)行到的位置

第一次調用：

首先傳入頭結點為6的鏈表，由于不滿足遞歸的基本結束條件，再一次觸發(fā)第二次調用，此時鏈表變?yōu)轭^結點為7的鏈表：

第二次調用：

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

第三次調用：

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

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

此時的鏈表為頭結點為8的鏈表，如上圖黃色區(qū)域，執(zhí)行第三步代碼之后，返回的結果為為頭結點為8的鏈表，即為8-->null，并將該結果返回到上一步調用，也就是標號為2的地方，得到結果為7-->8-->null的鏈表。

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

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

 到此遞歸調用得以結束，完成過程如下：

遞歸的調用是由代價的：函數(shù)調用（時間開銷）+系統(tǒng)?？臻g,但是使用遞歸書寫邏輯是更為簡單的。

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

希望本文所述對大家java程序設計有所幫助。

最新評論