方法的遞回呼叫
目錄:
- 方法的遞回呼叫
- 1. 基本介紹：
- 2. 遞回能解決什么問題？
- 3. 遞回舉例分析：
- 3.1 列印問題：
- 3.2 階乘問題：
- 遞回的重要規則：
1. 基本介紹：
簡單地說，遞回就是方法自己呼叫自己，每次呼叫時傳入不同的變數，遞回有助于編程者解決復雜問題的同時讓代碼變得簡潔，化繁為簡是其核心思想，
2. 遞回能解決什么問題？
- 各種經典數學問題，如：八皇后問題，漢諾塔(河內塔)，階乘問題，迷宮問題，青蛙跳臺階，球和籃子的問題(Google編程大賽)；
- 各種演算法中也會使用到遞回思想，比如快速排序(
quick sort)，歸并排序(merge sort)，二分查找(binary search)，分治演算法(divide and conquer)等； - 用堆疊解決的問題換成遞回實作 --> 遞回代碼比較簡潔；
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); //嘗試輸出看看
}
}
代碼截圖：
運行結果：
結果分析：
為了看起來比較規范，首先我們先簡單畫出 JVM記憶體區域 ，這里只涉及到堆疊空間，堆空間和方法區：
- 首先看到
main方法(程式的入口)，有C/C++基礎的小伙伴們應該曉得，我們知道在呼叫方法時，在堆疊空間中會創建相應的堆疊幀，main方法也是一個方法，也會被其他行程呼叫（在Linux中main函式有_start函式呼叫，這里不在展開，感興趣的小伙伴自行了解⑧），所以自然也會形成main堆疊幀，此時new了一個物件，此物件會在堆中創建，在堆疊中的參考變數會指向此堆空間，也就是保存了此物件的地址，如圖， - 在
main方法中呼叫了test方法，所以在堆疊中也會創建test堆疊幀，此時我們傳入的n為4，接下來判斷n大于4嗎？很明顯大于4，所以在test堆疊中又要呼叫test(n-1)，也就是呼叫test(3)，既然呼叫了方法，那便又要在堆疊中創建相應的堆疊幀，以此類推， - 當呼叫的方法為
test(2)時，此時判斷n大于2顯然為false，此時便要執行方法的最后一句陳述句，也就是sout列印陳述句，此時便會先列印2，列印完2之后方法結束(被作業系統回收/資源銷毀)，回傳到前一個呼叫此方法的堆疊幀中，也是以此類推，直到main方法結束， - 具體機制見下圖，
接上圖~~
到這里，我們大概就能懂為啥是先列印2，再列印3，最后才列印4了，
我們再來進一步拓展一下上述問題：
源代碼：
package com.recursion;
class Test{
public void test(int n) {
if (n > 2) {
test(n - 1);
} else { //唯一區別就是加了else
System.out.println("n=" + n);
}
}
}
public class Recursion {
public static void main(String[] args) {
Test t1 = new Test();
t1.test(4); //嘗試輸出看看
}
}
代碼截圖：
運行結果：
嘗試自己分析一下⑧，簡單來說就是if執行了else就不執行，else執行了說明if也沒執行，
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);
}
}
運行結果：
結果分析：
大體上都跟前面的列印例子差不多，都是呼叫自身時在堆疊上開辟相應的堆疊幀，前面忘說了，堆疊幀其實會二次開辟的，啥意思呢，就是說呼叫方法時先在堆疊上分配一塊較大的空間，也就是堆疊幀，而在堆疊幀內部還會進行一次具體的記憶體劃分，具體到每一個變數，每個堆疊幀結束后將回傳值回傳給上一個堆疊幀，以此類推就能清晰明了的弄清楚遞回的呼叫機制，
遞回的重要規則：
- 執行一個方法時，就創建一個相應的新的受保護的獨立空間 (堆疊空間/堆疊幀)；
- 方法的區域變數是獨立的，不會相互影響，比如前面多次提到的n變數；
- 如果方法中使用的是參考型別變數，比如陣列或者
String型別變數，就會共享該參考型別的資料 (指向同一堆空間)； - 遞回必須向退出遞回的條件逼近，否則就是無限遞回，會出現堆疊溢位
Stack Overflow Error，也就是死回圈； - 當一個方法執行完畢，或者遇到
return時，就會回傳，回傳的規則遵守誰呼叫就將結果回傳給誰，同時當方法執行完畢或者回傳時，該方法也就是執行完畢，還給作業系統，具體是啥時候還給作業系統這要看當時的環境；
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/306222.html
標籤：java
上一篇：單例模式的6大種類，如何保證執行緒安全、反射安全以及序列化安全，這次終于通透了
下一篇：4道經典指標筆試題講解 ~