快捷導(dǎo)航

Java遞歸運(yùn)行的機(jī)制：遞歸的微觀解讀圖文分析

更新時(shí)間：2020年03月19日 08:22:06 作者：WFaceBoss

這篇文章主要介紹了Java遞歸運(yùn)行的機(jī)制：遞歸的微觀解讀,結(jié)合圖文形式詳細(xì)分析了java遞歸運(yùn)行的原理、機(jī)制與相關(guān)注意事項(xiàng),需要的朋友可以參考下

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

前言：在java遞歸基礎(chǔ)與遞歸的宏觀語(yǔ)意和java鏈表的天然遞歸結(jié)構(gòu)性質(zhì)中我們分別通過(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)，如下圖：

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

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

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)入方法體之后，由于不滿(mǎn)足遞歸的基本條件，進(jìn)而繼續(xù)調(diào)用sum（arr,1）方法，如下：

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

使用sun(arr,1)進(jìn)行調(diào)用，進(jìn)入方法體之后，由于不滿(mǎn)足遞歸的基本條件，進(jìn)而繼續(xù)調(diào)用sum（arr,2）方法，此時(shí)調(diào)用過(guò)程如下：

當(dāng)調(diào)用sum(arr,2)時(shí)，由于此時(shí)已經(jīng)滿(mǎn)足了遞歸的基本條件，結(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;

通過(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)，如下圖：

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

2）為了分析的簡(jiǎn)便，我們來(lái)進(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的鏈表，由于不滿(mǎn)足遞歸的基本結(jié)束條件，再一次觸發(fā)第二次調(diào)用，此時(shí)鏈表變?yōu)轭^結(jié)點(diǎn)為7的鏈表：

第二次調(diào)用：

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

第三次調(diào)用：

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

第四次調(diào)用中，由于此時(shí)已經(jīng)滿(mǎn)足了遞歸的基本條件，回到上一次中斷的位置也就是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的鏈表。