摘要：簡而言之，遞歸就是自己調(diào)用自己，但是這個(gè)調(diào)用它是有一定條件的，比如子問題須與原始問題為同樣的事，且更為簡單。當(dāng)時(shí)，這層遞歸返回，也就是返回到的這層遞歸。這時(shí)，至此，遞歸結(jié)束，返回結(jié)果給調(diào)用方。

維基百科給出了如下定義：

程序調(diào)用自身的編程技巧稱為遞歸.遞歸作為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用。

上面的說法略顯官方。簡而言之，遞歸就是自己調(diào)用自己，但是這個(gè)調(diào)用它是有一定條件的，比如：

子問題須與原始問題為同樣的事，且更為簡單。

調(diào)用自身的次數(shù)不能太多，否則會(huì)造成程序堆棧溢出。

必須設(shè)置遞歸邊界，也就是遞歸的結(jié)束條件，否則遞歸會(huì)無限循環(huán)直到程序堆棧溢出。

遞歸

優(yōu)點(diǎn)：代碼簡潔、清晰（需要你理解算法，否則會(huì)更暈）
缺點(diǎn)：調(diào)用次數(shù)控制不好，容易造成堆棧溢出，此外，它的每次傳遞參數(shù)都是相當(dāng)于在壓棧，每次返回結(jié)果都相當(dāng)于出棧，這個(gè)過程是非常影響執(zhí)行效率的。

循環(huán)

優(yōu)點(diǎn)：邏輯簡單，速度快
缺點(diǎn)：不能解決所有的問題，有些問題必須用遞歸實(shí)現(xiàn)。比如，著名的漢若塔問題，如果有誰可以用其他方式寫出來我服。

關(guān)于使用場景，我總結(jié)了一句話：調(diào)用次數(shù)較少且用循環(huán)實(shí)現(xiàn)極為惡心的時(shí)候，可以嘗試使用遞歸。

計(jì)算 int 形數(shù)組的總和

public class Main {

    private static int sum(int[] arr, int z) {

        if (z == arr.length) {
            return 0;
        }

        int x = sum(arr, z + 1);

        int res = arr[z] + x;

        return res;
    }


    public static void main(String[] args) {
        int arr[] = {1, 2};
        sum(arr, 0);
    }
}

這個(gè)示例最簡單，當(dāng)然這里是為了方便說明問題，實(shí)際上用循環(huán)實(shí)現(xiàn)才是最好的。目的就是計(jì)算 arr 數(shù)組各元素的總和，看輸入?yún)?shù)，大家可以猜到返回結(jié)果是 3 。下面我說下看這類程序的小技巧。

首先，我們要找到程序的遞歸邊界，也就是遞歸結(jié)束的條件（這樣說也不準(zhǔn)確，看具體的代碼實(shí)現(xiàn)，有時(shí)遞歸邊界確實(shí)是遞歸結(jié)束的條件，返回最終結(jié)果，但有時(shí)又是遞歸最后一層返回結(jié)果的條件，比如以下程序）。

當(dāng) z = 2 時(shí)，這層遞歸返回 0 ，也就是 x = 0、返回到 z = 1 的這層遞歸。

此時(shí)，res = arr[1] + 0 ，返回 res = 2 也就是 x = 2 給到 z = 0 的這層遞歸。

這時(shí)，res = arr[0] + 2 = 3 至此，遞歸結(jié)束，返回結(jié)果給調(diào)用方。

沒看懂的，請復(fù)制代碼 debug 一步一步的運(yùn)行。一開始看反正我是被繞暈的。

計(jì)算 1 到 100 的總和

public class Main {

    static int i = 1;

    public static void show(int sum) {
        sum = sum + i; //業(yè)務(wù)代碼1
        //遞歸頭
        if (i == 10) {
            System.out.println(sum);
            return;
        }
        i++;   //業(yè)務(wù)代碼2
        show(sum); //遞歸體
    }

    public static void main(String[] args) {
        int sum = 0;
        show(sum);
    }
}

以上寫法的遞歸邊界，就屬于我上面說的，它就是遞歸結(jié)束的條件。它的返回結(jié)果就是遞歸的最終結(jié)果，而不是上一層的結(jié)果。

斐波那契數(shù)列

public class Main {
 
? ? public static int f(int n) throws Exception {
? ? ? ? if(n==0){
? ? ? ? ? ?throw new Exception("參數(shù)錯(cuò)誤！");
? ? ? ? }
? ? ? ? if (n == 1 || n == 2) {
? ? ? ? ? ? return 1;
? ? ? ? } else {
? ? ? ? ? ? return f(n-1)+f(n-2); //自己調(diào)用自己
? ? ? ? }
?}
 
 
? ? public static void main(String[] args) throws Exception {
? ? ? ? for (int i = 1; i <=10; i++) {
? ? ? ? ? ? System.out.print(f(i)+" ");
? ? ? ? }
? ? } ?
}

計(jì)算文件夾大小

由于 File 類下length() (返回值類型為 long 型) 方法只能統(tǒng)計(jì)文件的大小，沒有方法直接統(tǒng)計(jì)文件夾的大小，需要使用遞歸的方法遍歷到所有的文件，并累加，最終計(jì)算出文件夾大小。

public class Main {

    public static void main(String[] args) {
        File dir = getDir();
        System.out.println(getFileLength(dir));
        System.out.println("統(tǒng)計(jì)完成!");
    }
    
    public static File getDir() {
        //1,創(chuàng)建鍵盤錄入對(duì)象
        Scanner sc = new Scanner(System.in);
        System.out.println("請輸入一個(gè)文件夾路徑:");
        //2,定義一個(gè)無限循環(huán)
        while(true) {
            //3,將鍵盤錄入的結(jié)果存儲(chǔ)并封裝成File對(duì)象
            String line = sc.nextLine();
            File dir = new File(line);
            //4,對(duì)File對(duì)象判斷
            if(!dir.exists()) {
                System.out.println("您錄入的文件夾路徑不存在,請重新錄入:");
            }else if(dir.isFile()) {
                System.out.println("您錄入的是文件路徑,請重新錄入:");
            }else {
                //5,將文件夾路徑對(duì)象返回
                return dir;
            }
        }        
    }

    public static long getFileLength(File dir) {
        //1,定義一個(gè)求和變量
        long len = 0;
        //2,獲取該文件夾下所有的文件和文件夾listFiles();
        File[] subFiles = dir.listFiles();
        //3,遍歷數(shù)組
        if(subFiles != null) {
            for (File subFile : subFiles) {
                //4,判斷是文件就計(jì)算大小并累加
                if(subFile.isFile()) {
                    len = len + subFile.length();
                    //5,判斷是文件夾,遞歸調(diào)用
                }else {
                    len = len + getFileLength(subFile);
                }
            }
        }
        return len;
    }
}

總結(jié)：這篇主要是介紹下遞歸的定義、與循環(huán)的區(qū)別以及它的使用場景，最后提供了幾個(gè)代碼示例給大家研究，看不懂的請復(fù)制代碼，debug 一步一步運(yùn)行理解。

參考鏈接：https://www.jianshu.com/p/edfc4e35f383

推薦閱讀：

1、java | 什么是動(dòng)態(tài)代理

2、SpringBoot?| 啟動(dòng)原理

3、SpringBoot | 自動(dòng)配置原理