方法的遞歸調(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ū)域 ，這里只涉及到?？臻g，堆空間和方法區(qū)：

• 首先看到main方法(程序的入口)，有C/C++基礎(chǔ)的小伙伴們應(yīng)該曉得，我們知道在調(diào)用方法時，在?？臻g中會創(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é)束。
• 具體機制見下圖。

接上圖~~

到這里，我們大概就能懂為啥是先打印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)用機制。

遞歸的重要規(guī)則：

• 執(zhí)行一個方法時，就創(chuàng)建一個相應(yīng)的新的受保護(hù)的獨立空間 (?？臻g/棧幀)；
• 方法的局部變量是獨立的，不會相互影響，比如前面多次提到的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)用機制精細(xì)解讀的文章就介紹到這了,更多相關(guān)Java 遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論