【小白學算法】10.遞歸的調用機制、使用時要注意的規則
- 2021 年 4 月 23 日
- 筆記
- 把蘋果咬哭的不規律日常, 數據結構與算法
簡單來說，遞歸就是自己調用自己，在每次調用時傳入不同的變量。遞歸有助於解決複雜的問題，同時讓代碼變得簡潔。
在之前的文章中，對遞歸有過簡單的介紹，現在進一步了解下遞歸的調用機制。
一、遞歸的調用機制
先上一段簡單的遞歸調用的代碼：
package recursion;
public class RecursionTest {
public static void main(String[] args) {
test(4);
}
public static void test(int n) {
if (n > 2) {
test(n - 1);
}
System.out.println("n=" + n);
}
}
可以看到，在main方法里，執行test(4)，當滿足n>2的條件時，test()會繼續調用test()，直到不滿足遞歸條件，打印出n的值。
運行結果其實也很容易想到：
n=2
n=3
n=4
Process finished with exit code 0
運行結果倒不是重點了，現在藉著這段代碼再加張圖，看下遞歸的調用機制。
圖中所示就是在執行代碼的過程中，jvm中發生的一些事情。不過這裡聲明一下，關於jvm的某些描述可能並不是很準確，這裡只是輔助理解記憶。
- 首先，在運行
main方法時，會在棧里開闢一個main方法的棧幀。
當main方法里調用test方法時，又會壓入一個棧幀，也就是入棧。當方法沒運行結束時，是不會出棧的。
所以，運行test(4)，會繼續壓入一個棧幀（紅色箭頭）。 - 在
test(4)里，經過判斷會繼續調用test(3)，於是繼續壓入一個棧幀。 - 在
test(3)里，經過判斷會繼續調用test(2)，於是繼續壓入一個棧幀。 - 在
test(2)里，經過判斷，不再遞歸，於是運行了print代碼，打印出n的值為2。
方法運行完了就會出棧（黃色箭頭），回到test(3)。 test(3)打印出n的值為3，繼續出棧，回到test(4）。test(4)打印出n的值為4，main方法運行結束，退出程序。
所以，代碼運行的結果就是2,3,4。
二、使用遞歸需要知道的點
- 執行一個方法時，會創建一個新的受保護的獨立空間。比如上面的棧幀。
- 方法的局部變量是獨立的，不會相互影響。比如上面每次遞歸時候的變量
n。
但是，如果方法中使用的是引用類型變量，那會共享該引用類型。比如，引用一個數組。 - 重點：遞歸必須向退出遞歸的條件逼近，否則就無限遞歸，最終棧溢出
StackOverflowError。 - 當方法執行完畢，或者遇到
return，就會返回。遵守誰調用，就將結果返回給誰。
比如上圖中最上面的棧幀test(2)運行結束後，就返回到調用它的test(3)。
