java 遞歸的方法（java方法的遞歸講解）

2023-04-15 14:02:50

提到方法的遞歸調用，需要先說一下棧的存儲概念。

　　棧是一個先進後出的壓入(push)和彈出(pop)式數據存儲結構。若想獲取到棧底的對象，就必須先將這個對象上面的所有的對象全部從棧中移除，否則無法獲取棧底的對象。

　　我們來看看程序中棧是如何工作的，當一個方法(調用者)調用另一個方法(被調用者)時，將會將調用者的參數和返回值一起壓入到棧中，此時調用者方法處於棧頂的位置，當調用者執行到調用方法的語句時，此時調用者方法將不會繼續執行，即將執行被調用者方法，那麼被調用者就會與參數返回值一起壓入到棧中，此時被調用者處於棧頂的位置，所以此時先執行被調用者方法。直到被調用者方法執行結束，所有的參數以及局部變量會隨著方法的執行結束一起彈出棧空間，此時被調用者方法的返回值將會被帶出方法，數據不會隨著方法的出棧而消失，而是會落入到此時棧頂的方法中，所以方法的返回值是返回到方法的調用處

　　下圖是以上代碼執行過程中，棧空間中存儲的變化：

　　方法的遞歸調用

　　遞歸調用是一種特殊的嵌套調用，是某個方法直接或間接的調用自己，實際上相當於是循環執行功能代碼。換句話說，就是可以使用方法遞歸調用完成的功能，同樣也可以使用循環完成。

　　方法遞歸調用的分類

　　直接遞歸：現有fun方法，在fun方法中調用fun方法，這種調用方式稱為直接遞歸調用。

　　間接遞歸：現有fun1方法和fun2方法，在fun1方法中調用fun2方法，在fun2方法中調用fun1方法，實際並沒有在fun1方法中直接調用自己，而是調用了fun2方法，間接的調用了fun1方法，這種調用方式稱為間接遞歸調用。

　　遞歸調用的案例

　　案例：設計一個方法，使用循環計算一個整數的階乘結果。

　　當然，這個案例也可以使用方法的遞歸調用來完成，關於這個問題使用遞歸調用完成時，與數學中的一類題目類似：

　　上圖的數學問題，若想計算解集的話，需要將x的值帶入到表達式中，但是對於x的不同取值範圍，需要使用不同的表達式計算結果。對於這個數學問題的計算過程，再次我們就不在演示。

　　若使用遞歸調用的方法計算一個整數的階乘結果時，我們已知n的階乘計算方法是從1開始乘一直乘到n為止，所以1的階乘結果是1。那麼計算n的階乘，當n>1時，n的階乘等於n乘n-1的階乘;當n=1時，n的階乘等於1。通過分析，請我們可以使用分支結果完成分析過程中的：當...則...，當...則...

　　我們可以將遞歸調用寫成一下格式的分段函數：

　　遞歸調用中的返回值

　　由於方法的返回值返回到方法的調用處，所以方法遞歸調用返回時是一層一層的向外返回。

　　我們都玩過歡樂球，歡樂球中灌了水，再將歡樂球放進一個盛水的小玻璃缸中，小玻璃缸放進一個大玻璃缸中，將歡樂球中捅破時，歡樂球中的水一定是進入到小玻璃缸中，而不是直接進入大玻璃缸中。

　　下圖是遞歸調用計算階乘的返回值的圖，返回值一定是一層一層向外返回，而不是最內層的返回整個方法結束。

　　方法壓棧與方法遞歸

　　以上敘述我們說過，一個方法在執行時，會壓入棧中，而遞歸調用相當於多次調用同一個方法，那麼遞歸幾次，就會在棧中開闢幾個相同大小的空間，所以使用遞歸調用時，比較好性能，我們可以通過循環來完成遞歸完成的功能。