方法的遞歸調(diào)用
1. 基本介紹：
簡單地說，遞歸就是方法自己調(diào)用自己，每次調(diào)用時傳入不同的變量，遞歸有助于編程者解決復(fù)雜問題的同時讓代碼變得簡潔，化繁為簡是其核心思想。
2. 遞歸能解決什么問題？
- 各種經(jīng)典數(shù)學(xué)問題，如：八皇后問題，漢諾塔(河內(nèi)塔)，階乘問題，迷宮問題，青蛙跳臺階，球和籃子的問題(Google編程大賽)；
-
各種算法中也會使用到遞歸思想，比如快速排序(
quick sort)，歸并排序(merge sort)，二分查找(binary search)，分治算法(divide and conquer)等； - 用棧解決的問題換成遞歸實現(xiàn) --> 遞歸代碼比較簡潔；
3. 遞歸舉例分析：
3.1 打印問題：
我們來看一哈這一段代碼：
package com.recursion;
class Test{
public void test(int n) {
if (n > 2) {
test(n - 1);
}
System.out.println("n=" + n);
}
}
public class Recursion {
public static void main(String[] args) {
Test t1 = new Test();
t1.test(4); //嘗試輸出看看
}
}
代碼截圖：
運行結(jié)果：
結(jié)果分析：
為了看起來比較規(guī)范，首先我們先簡單畫出 JVM內(nèi)存區(qū)域 ，這里只涉及到棧空間，堆空間和方法區(qū)：
-
首先看到
main方法(程序的入口)，有C/C++基礎(chǔ)的小伙伴們應(yīng)該曉得，我們知道在調(diào)用方法時，在棧空間中會創(chuàng)建相應(yīng)的棧幀，main方法也是一個方法，也會被其他進(jìn)程調(diào)用（在Linux中main函數(shù)有_start函數(shù)調(diào)用，這里不在展開，感興趣的小伙伴自行了解⑧），所以自然也會形成main棧幀。此時new了一個對象，此對象會在堆中創(chuàng)建，在棧中的引用變量會指向此堆空間，也就是保存了此對象的地址，如圖。 -
在
main方法中調(diào)用了test方法，所以在棧中也會創(chuàng)建test棧幀，此時我們傳入的n為4，接下來判斷n大于4嗎？很明顯大于4，所以在test棧中又要調(diào)用test(n-1)，也就是調(diào)用test(3)，既然調(diào)用了方法，那便又要在棧中創(chuàng)建相應(yīng)的棧幀，以此類推。 -
當(dāng)調(diào)用的方法為
test(2)時，此時判斷n大于2顯然為false，此時便要執(zhí)行方法的最后一句語句，也就是sout打印語句，此時便會先打印2，打印完2之后方法結(jié)束(被操作系統(tǒng)回收/資源銷毀)，返回到前一個調(diào)用此方法的棧幀中，也是以此類推，直到main方法結(jié)束。 - 具體機(jī)制見下圖。
接上圖~~
到這里，我們大概就能懂為啥是先打印2，再打印3，最后才打印4了。
我們再來進(jìn)一步拓展一下上述問題：
源代碼：
package com.recursion;
class Test{
public void test(int n) {
if (n > 2) {
test(n - 1);
} else { //唯一區(qū)別就是加了else
System.out.println("n=" + n);
}
}
}
public class Recursion {
public static void main(String[] args) {
Test t1 = new Test();
t1.test(4); //嘗試輸出看看
}
}
代碼截圖：
運行結(jié)果：
嘗試自己分析一下⑧，簡單來說就是if執(zhí)行了else就不執(zhí)行，else執(zhí)行了說明if也沒執(zhí)行。
3.2 階乘問題：
源代碼：
package com.recursion;
class Test01 {
public int factorial(int n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1) * n;
}
}
}
public class Factorial {
public static void main(String[] args) {
Test01 test = new Test01();
int ret = test.factorial(5);
System.out.println("ret=" + ret);
}
}
運行結(jié)果：
結(jié)果分析：大體上都跟前面的打印例子差不多，都是調(diào)用自身時在棧上開辟相應(yīng)的棧幀，前面忘說了，棧幀其實會二次開辟的，啥意思呢，就是說調(diào)用方法時先在棧上分配一塊較大的空間，也就是棧幀，而在棧幀內(nèi)部還會進(jìn)行一次具體的內(nèi)存劃分，具體到每一個變量。每個棧幀結(jié)束后將返回值返回給上一個棧幀，以此類推就能清晰明了的弄清楚遞歸的調(diào)用機(jī)制。
遞歸的重要規(guī)則：
- 執(zhí)行一個方法時，就創(chuàng)建一個相應(yīng)的新的受保護(hù)的獨立空間 (棧空間/棧幀)；
- 方法的局部變量是獨立的，不會相互影響，比如前面多次提到的n變量；
-
如果方法中使用的是引用類型變量，比如數(shù)組或者
String類型變量，就會共享該引用類型的數(shù)據(jù) (指向同一堆空間)； -
遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸，會出現(xiàn)棧溢出
Stack Overflow Error，也就是死循環(huán)； -
當(dāng)一個方法執(zhí)行完畢，或者遇到
return時，就會返回，返回的規(guī)則遵守誰調(diào)用就將結(jié)果返回給誰，同時當(dāng)方法執(zhí)行完畢或者返回時，該方法也就是執(zhí)行完畢，還給操作系統(tǒng)，具體是啥時候還給操作系統(tǒng)這要看當(dāng)時的環(huán)境；
到此這篇關(guān)于Java 關(guān)于遞歸的調(diào)用機(jī)制精細(xì)解讀的文章就介紹到這了,更多相關(guān)Java 遞歸內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/b_ingram/article/details/120638507
