方法的遞歸調(diào)用

1. 基本介紹：

簡(jiǎn)單地說，遞歸就是方法自己調(diào)用自己，每次調(diào)用時(shí)傳入不同的變量，遞歸有助于編程者解決復(fù)雜問題的同時(shí)讓代碼變得簡(jiǎn)潔，化繁為簡(jiǎn)是其核心思想。

2. 遞歸能解決什么問題？

• 各種經(jīng)典數(shù)學(xué)問題，如：八皇后問題，漢諾塔(河內(nèi)塔)，階乘問題，迷宮問題，青蛙跳臺(tái)階，球和籃子的問題(Google編程大賽)；
• 各種算法中也會(huì)使用到遞歸思想，比如快速排序(quick sort)，歸并排序(merge sort)，二分查找(binary search)，分治算法(divide and conquer)等；
• 用棧解決的問題換成遞歸實(shí)現(xiàn) --> 遞歸代碼比較簡(jiǎ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); //嘗試輸出看看
    }
}

代碼截圖：

運(yùn)行結(jié)果：

結(jié)果分析：

為了看起來比較規(guī)范，首先我們先簡(jiǎn)單畫出 JVM內(nèi)存區(qū)域 ，這里只涉及到?？臻g，堆空間和方法區(qū)：

• 首先看到main方法(程序的入口)，有C/C++基礎(chǔ)的小伙伴們應(yīng)該曉得，我們知道在調(diào)用方法時(shí)，在?？臻g中會(huì)創(chuàng)建相應(yīng)的棧幀，main方法也是一個(gè)方法，也會(huì)被其他進(jìn)程調(diào)用（在Linux中main函數(shù)有_start函數(shù)調(diào)用 ，這里不在展開，感興趣的小伙伴自行了解⑧），所以自然也會(huì)形成main棧幀。此時(shí)new了一個(gè)對(duì)象，此對(duì)象會(huì)在堆中創(chuàng)建，在棧中的引用變量會(huì)指向此堆空間，也就是保存了此對(duì)象的地址，如圖。
• 在main方法中調(diào)用了test方法，所以在棧中也會(huì)創(chuàng)建test棧幀，此時(shí)我們傳入的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)時(shí)，此時(shí)判斷n大于2顯然為false，此時(shí)便要執(zhí)行方法的最后一句語(yǔ)句，也就是sout打印語(yǔ)句，此時(shí)便會(huì)先打印2，打印完2之后方法結(jié)束(被操作系統(tǒng)回收/資源銷毀)，返回到前一個(gè)調(diào)用此方法的棧幀中，也是以此類推，直到main方法結(jié)束。
• 具體機(jī)制見下圖。

接上圖~~

到這里，我們大概就能懂為啥是先打印2，再打印3，最后才打印4了。

我們?cè)賮磉M(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); //嘗試輸出看看
    }
}

代碼截圖：

運(yùn)行結(jié)果：

嘗試自己分析一下⑧，簡(jiǎn)單來說就是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);

    }
}

運(yùn)行結(jié)果：

結(jié)果分析：大體上都跟前面的打印例子差不多，都是調(diào)用自身時(shí)在棧上開辟相應(yīng)的棧幀，前面忘說了，棧幀其實(shí)會(huì)二次開辟的，啥意思呢，就是說調(diào)用方法時(shí)先在棧上分配一塊較大的空間，也就是棧幀，而在棧幀內(nèi)部還會(huì)進(jìn)行一次具體的內(nèi)存劃分，具體到每一個(gè)變量。每個(gè)棧幀結(jié)束后將返回值返回給上一個(gè)棧幀，以此類推就能清晰明了的弄清楚遞歸的調(diào)用機(jī)制。

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

• 執(zhí)行一個(gè)方法時(shí)，就創(chuàng)建一個(gè)相應(yīng)的新的受保護(hù)的獨(dú)立空間 (?？臻g/棧幀)；
• 方法的局部變量是獨(dú)立的，不會(huì)相互影響，比如前面多次提到的n變量；
• 如果方法中使用的是引用類型變量，比如數(shù)組或者String類型變量，就會(huì)共享該引用類型的數(shù)據(jù) (指向同一堆空間)；
• 遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸，會(huì)出現(xiàn)棧溢出Stack Overflow Error，也就是死循環(huán)；
• 當(dāng)一個(gè)方法執(zhí)行完畢，或者遇到return時(shí)，就會(huì)返回，返回的規(guī)則遵守誰(shuí)調(diào)用就將結(jié)果返回給誰(shuí)，同時(shí)當(dāng)方法執(zhí)行完畢或者返回時(shí)，該方法也就是執(zhí)行完畢，還給操作系統(tǒng)，具體是啥時(shí)候還給操作系統(tǒng)這要看當(dāng)時(shí)的環(huán)境；

到此這篇關(guān)于Java 關(guān)于遞歸的調(diào)用機(jī)制精細(xì)解讀的文章就介紹到這了,更多相關(guān)Java 遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！