遞回的概念

什么是遞回？
程式呼叫自身的編程技巧稱為遞回（ recursion）， 遞回做為一種演算法在程式設計語言中廣泛應用， 一個程序或函式在其定義或說明中有直接或間接呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量， 遞回的主要思考方式在于：把大事化小
遞回的兩個必要條件：

• 存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
• 每次遞回呼叫之后越來越接近這個限制條件，

遞回執行程序的詳細分析

代碼示例: 遞回求 N 的階乘：

 public static void main(String[] args) {
        int n = 3;
        int ret = factor(n);
        System.out.println("ret = " + ret);
    }
    public static int factor(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factor(n - 1); // factor 呼叫函式自身
    }

**假設我們用求3的階乘來舉例，要求3的階乘，可以轉換為3乘2的階乘，可以先求2的階乘，要求2的階乘可以先求1的階乘，再乘2，1的階乘求完后，不滿足遞回條件，就把值一步一步的回退到呼叫函式內部求積，這樣如果是一個復雜的問題就可以簡化的很簡單的問題了，**簡化了一些重復的步驟；比如要求n的階乘，就先求（n-1）的階乘，之后再乘上n,要求（n-1）的階乘，就先求（n-2）的階乘在乘個（n-1）即可，一直求出1的階乘為止，這里可能這個階乘這個簡單的問題你沒有體會到遞回的簡便性，但是我們先從簡單問題把遞回看懂，在看難的問題，
圖示分析代碼執行程序：

上面是求3的階乘的代碼執行流程，其實遞回遞回，就是“遞”向問題的小的一方面走下去，“歸”回歸，程式執行到某一條件時，回歸到起始的遞位置，
大致程序如下圖：

函式呼叫時，函式在堆疊上開辟空間，函式的引數，區域變數，回傳資料，回傳地址等也是在堆疊上開辟的，堆疊的特點先進后出，理解這一點可以幫助我們理解函式遞回的“歸”的程序，你細細品就行，

經典遞回問題分析與解答

對于遞回本身有點抽象有點難想，多找找規律和畫圖理解一下，遞回重點是找遞回公式，如果你找的到遞回的公式那很簡單的照的公式寫代碼行，對于有些問題如遞回非遞回都能做還是最好不使用遞回，非遞回的效率更高，

斐波那契數列問題

斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
代碼實作斐波那契數列

 public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int a=scanner.nextInt();
        System.out.println(fib(a));
    }

從斐波那契數列的形式可以輕松地看出，它的規律，得到它的遞推公式，從第三個斐波那契數開始，斐波那契數都是前兩個數字的和，第一二兩個數字都是1.假設要求第一百個斐波那契數數列，要先求地99和第98個，要求第99個又要求第第98,97個…，以此類推，可知求斐波那契數列也是遵循大事化小的，也是一個遞回問題,當然用遞回的方式求菲波那切數列固然簡單，但在求值程序中做了許多重復的計算效率太低，（畫個樹形圖簡單看一下秒懂）求該數列也可以使用非遞回的方式，回圈更加高效 ，

非遞回的斐波那契數列：

public static int fib(int n) {
    int a=1;
    int b=1;
    int c=1;
    while (n>2) {
        c=a+b;
        a=b;
        b=c;
        n--;
    }
    return c;

}
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n= scanner.nextInt();
        System.out.println(fib(n));
    }

青蛙跳臺階問題

題目連接
一只青蛙一次可以跳上 1 級臺階，也可以跳上2 級，求該青蛙跳上一個n 級的臺階總共有多少種跳法?
對于一個問題，我們拿到首先是思考下，該計算計算，該畫圖畫圖，找到規律，關鍵點之后再寫代碼，
情況一,只有一階臺階，一次跳一個臺階只有1種跳法

情況二，有兩階臺階，可以一步一步的跳，也可以一步跳兩個臺階，有兩種跳法

情況三，有三階臺階，由于題目說，小青蛙每次只能跳一階或者兩階臺階**，所以有兩種情況，如果跳一階臺階，之后后面有兩階臺階，跳法和情況二相似；如果青蛙跳兩階臺階，之后后面只有了一階臺階，這和情況一的跳法一樣**，這樣一來我們大概就明白了，情況三有三階臺階，兩種情況，總的跳法就是前兩種臺階跳法加起來為3種，

那么我們大致來想一想如果有4階臺階呢，更多的臺階呢？
小青蛙每次跳一階或者兩階臺階，如果跳一階臺階后面有三階臺階，之后的跳法不是和三階臺階的跳法一樣嗎？如果跳兩階臺階，后面剩的兩階臺階，和兩階臺階的跳法是一樣的，這樣由數學歸納法就可以得出，如果有n階臺階，小青蛙的跳法就為，（n-1階）的跳法，加上（n-2）階的跳法，這樣我們發現這個問題也是一個遞回問題，要求n階的跳法太復雜了，我們把它分解為小問題后倒著求來求值，把這個求n階的問題，分解為以一階二階為基礎的求法，青蛙跳臺階的歸納公式為F(1)=1，F(2)=2, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），我們可以看出其實這個青蛙跳臺階就是從那個斐波那契數列演變而來的，
代碼實作：

  public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);

        int n = scanner.nextInt(); //臺階數
        System.out.println(jumpFloor(n));
    }

        public static  int jumpFloor(int floor) {
            if (floor == 1) { //情況一
                return 1;
            }
            if (floor == 2) { //情況二
                return 2;
            }
            return jumpFloor(floor - 1) + jumpFloor(floor - 2); //函式遞回
        }

變種青蛙跳臺階

題目描述
題目連接
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級，求該青蛙跳上一個n級的臺階(n為正整數)總共有多少種跳法，
分析：
變種青蛙跳臺階沒有規定青蛙跳的步數，所以青蛙跳的肯更情況也增多了，比如一步跳的情況，任何臺階，從地面上直接跳到最高階，勇敢的青蛙都能跳了，還有前面所有跳的情況，現在的青蛙都能跳出來了，假設直接從地面跳的跳法為f(0)=1,我們由圖推匯出遞回的公式，那如果有n階臺階的跳法為f(n) = f(n-1) + f(n-2) +....+f(0)，（f(0),f(1)都為1），遞回的時間復雜度：O(N^N)，空間復雜度：O(N)，

那么遞回代碼如下：

public class Test {


    public static int jumpFloorII(int number) {
        int sum = 1;
        for(int i = 1; i<number;i++)
            sum += jumpFloorII(number-i);  //計算f(number-1)
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int a=scanner.nextInt();
        System.out.println(jumpFloorII(a));

    }

與遞回思路一樣，但是普通的遞回進行了多次無用計算， 比如在上述遞回中，f(1),f(2)…被多次計算，我們可以進行優化，方法有很多種，我選擇了最好理解的簡單的，數學的方式來解答，f[n] = f[n-1] + f[n-2] + … + f[0]，那么f[n-1] = f[n-2] + f[n-3] + … + f[0]
所以一合并，f[n] = 2*f[n-1]，f[n]/f[n-1]=2初始條件f[0] = f[1] = 1,為一個等比數列，之后求出等比數列的通項公式為f[n]=2^(n-1)，時間復雜度：O(n)，空間復雜度：O(1)

代碼實作：

public class Test {
        public static  int jumpFloorII(int number) {
            if(number==1||number==0) return 1;
            return 1<<number-1; //口訣：左移乘2，右移除2
        }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int a=scanner.nextInt();
        System.out.println(jumpFloorII(a));

    }
}

漢諾塔問題

題目連接
漢諾塔問題是一個經典的問題，漢諾塔（Hanoi Tower），又稱河內塔，源于印度一個古老傳說，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，任何時候，在小圓盤上都不能放到大圓盤上，取放圓盤必須在柱子上，不能把圓盤放在其他位置，且在三根柱子之間一次只能移動一個圓盤，問應該如何操作？
三根柱子分別命名為A，B，C，把任意個圓盤從第一根柱子A上移動到最后一根柱子C的基本思路：

1.當n=1的時候，直接把圓盤從A盤移動到C盤
當n>1的時候
1. 將A柱上的n-1個盤子借助C柱移動到B柱上
2. 將A柱上面的第n個盤子移動到到C 柱上面，
3. 將B柱上面的n-1個盤子移動到C柱上面
簡單分析：
首先遞回隨著遞回的層次深入，問題越來越復雜，很抽象，到達一定的規模是人腦無法思考的，我們只能通過簡單的遞回找到規律，之后書寫代碼，一個兩個三個盤子的情況是非常簡單容易想象的，假設有三個盤子，我們首先把上面的2個盤子移經過C移動到B（有多個盤子的時候一定要借助其他的盤子移動，這樣才能保證大的盤子在下面），**之后把第三個盤子移動到C柱，把A上面的2個盤子移動到B柱上面又是一次遞回操作和原來的問題是不是一個問題呢？只是盤子變少了，每次遞回的傳過來的實際引數也變了，**傳過來的實際引數就是每次遞回時帶進來的，那么如果移動n個盤子的思路是不是和上面的說的一樣呢，這是不是體現了遞回的的思想，“大事化小”，每次遞回時都更加接近遞回結束的條件，學習遞回時慢慢來，首先從簡單到復雜，理解簡單的再到復雜的程序，復雜的程序不必太死扣，就是那樣像簡單的那樣執行思路，如果你較真去死扣每一步，我想是很難理解遞回的，
一個盤子A->C,1=2^1-1
兩個盤子的情況： A->B A->C B->C ，移動三次， 3= 2^2 -1

三個盤子的移動：
A->C A->B C->B A->C B->A B->C A->C ， 7 =2^3 -1

有三個盤子，我們首先把上面的2個盤子移經過C移動到B就是藍色那一坨是一次遞回，使用第一個遞回函式，之后把第三個盤子移動到C柱后，把A上面的2個盤子移動到B柱上面又是那一坨又是一次遞回，

由上面的一個兩個三個盤子的移動次數，我們可以歸納出，移動n個盤子的次數為2^n-1次，，回到最初的這個問題，當金剛石柱上有64個黃金圓盤時，如果移動需要移動的次數為2 ^ 64-1,如果一秒鐘移動一次的化，那么需要2 ^64-1=1.845*10 ^19,約為5849億年！可以想象問題的有多復雜了，

代碼示例：

public class TestDemo {
    public static void move(char pos1,char pos2) {
        System.out.print(pos1+"->"+pos2+"  ");
    }


    /**
     *
     * @param n 當前的盤子個數
     * @param pos1 起始位置
     * @param pos2 中轉位置
     * @param pos3 目的位置
     */
    public static void hanoiTower(int n,char pos1,char pos2,char pos3) {//傳入的實參會發生變化
        if(n == 1) {
            move(pos1,pos3);
        }else {
            hanoiTower(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            hanoiTower(n-1,pos2,pos1,pos3);
        }
    }

    public static void main(String[] args) {
        hanoiTower(1,'A','B','C');
        System.out.println();
        hanoiTower(2,'A','B','C');
        System.out.println();
        hanoiTower(3,'A','B','C');
        System.out.println();

    }
}

🛣?過🉐小🧑🏽?🤝?🧑🏼如果9??🉐🉑以🉐話記🉐點👍🏻🍹持👇🏻，🦀🦀