遞回演算法總結

概念

遞回演算法遞回演算法是演算法中最基礎，入門級別的演算法，簡單理解：不停直接或間接呼叫自身函式，每次呼叫會改變一個或者多個變數，直到變數到達邊界，結束呼叫，

借用知乎上Memoria的回答：

假設你在一個電影院，你想知道自己坐在哪一排，但是前面人很多，你懶得去數了，于是你問前一排的人「你坐在哪一排？」，這樣前面的人 (代號 A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了，不料 A 比你還懶，他也不想數，于是他也問他前面的人 B「你坐在哪一排？」，這樣 A 可以用和你一模一樣的步驟知道自己所在的排，然后 B 也如法炮制，直到他們這一串人問到了最前面的一排，第一排的人告訴問問題的人「我在第一排」，最后大家就都知道自己在哪一排了，

正規的說法：遞回演算法就是通過不斷呼叫自身將原問題分解為跟原問題相同解決方法的子問題，最后將各子問題的解合并得到原問題的解，遞回的核心思想是分治策略，也就是將一個規模大的問題分解成一些規模小的同類問題，然后通過這些小問題求得大問題的解，

遞回演算法和分治法的區別：遞回是演算法的實作方式，分治是演算法的設計思想， 這跟你吃飯可以用筷子吃，也用手吃一樣，也就是我使用的是分治法的思想，但不一定使用遞回演算法來實作該實作，

遞回演算法和回圈的區別：遞回演算法是將問題規模縮小，最終得到問題的解；而回圈是一種由遠變到近的程序，問題的規模不見得縮小了，但是慢慢在調整接近答案，

遞回演算法的設計

1. 找出遞回的終止條件，
2. 終止后要回傳什么結果，
3. 遞回部分，

比如上面的電影院例子：

1. 當到了第一排就終止；
2. 在第一排回傳 自己是坐哪一排的資訊；
3. 從我開始要知道自己的位置，我需要知道我前一排的位置然后再加一得到我的位置，而我前一排需要他前一排的位置加一得到他的位置，這就是遞回部分，

遞回演算法的優缺點

遞回演算法的時間復雜度是O(n^2)，所以也是比較暴力破解演算法，

優點：只需要幾條代碼就可以解決問題，

缺點：

1. 有時因為太過簡潔而難理解程序，
2. 遞回會保存大量臨時資料和重復的資料，太多的話，會造成堆疊溢位，程式崩潰，
3. 資料規模大時，運行時間會超時，所以做編程題時，注意看資料規模的大小，最好別用遞回，

經典例題

1. 求解Fibonacci數列的第n個位置的值？（斐波納契數列（Fibonacci Sequence），又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、
   ……在數學上，斐波納契數列以如下被以遞回的方法定義：F1=1,F2=1,Fn=F（n-1）+F（n-2）（n>2,n∈N*）），

設計步驟：

1.找出終止條件：當n=1時；當n=2時
2.終止后要回傳什么結果：當n=1時，F1=1；當n=2時，F2=1
3.遞回部分：Fn=F（n-1）+F（n-2）（n>2,n∈N*）），也就是一個數會等于前兩個數相加的結果，

代碼：

public class Fibonacci {
    public static int fib(int n){
        // 1. 終止條件
        if(n == 1 || n == 2){
            // 2.終止完要回傳什么
            return 1;
        }
        // 3.遞回部分
        return fib(n-1) + fib(n-2);
    }
    public static void main(String[] args) {
        System.out.println(fib(10));
    }
}

可以試試你的n很大的話(n=100即可感受到)，這段代碼會運行半天還沒算出結果，這就是遞回演算法的缺點，用動態規劃也可以做而且更好更快計算，不過現在這里是學遞回演算法，后面到動態規劃會拿出來優化，

程序圖：

如圖可以看到，像F(4)和F(3)重復計算了幾次，也就導致要多些運算時間和記憶體空間，

2. 階乘

階乘的公式直接推：n!=n*(n-1)*(n-2)…3*2*1

終止條件就是當n=1時回傳1，

核心代碼：

    public static int factorial(int n){
        if(n == 1){
            return 1;
        }
        return n*factorial(n-1);
    }

程序圖：

3. 漢諾塔問題是一個經典的遞回問題，漢諾塔（Hanoi Tower），又稱河內塔，源于印度一個古老傳說，大梵天創造世界的時候做了三根金剛石柱子，
   在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次只能移動一個圓盤，假設我們需要這些盤片從A柱移動到C柱，應該如何操作？
   

解決：
主要是利用漢諾塔理解下遞回的思想，

來分析它的步驟：（->表示移動）

現在假設只有一個盤片，那么直接就是：A->C

假設現在有兩個盤片，那么就需要三步：

1. 從A柱最頂的盤片移動到B柱：A->B
2. 然后A柱現在只剩最底的盤片，也是最大的盤片，移動到C柱：A->C
3. 最后B柱上的盤片移動到C：B->C

對于此三步，我們再決議一下：

• 當第一步A->B完成后，其實問題就變回了當在A柱上只有一個盤片時怎么操作的問題，因為此時A柱就剩最底的一個盤片啊，所以跟上面只有一個盤片的解決方式一樣，直接A->C，
• 那么第三步呢？第三步其實也是跟只有一個盤片的解決方式一樣，只不過現在是在B柱，那么你可以看成，是B->A->C，也就是把B柱的盤片先移動到A柱，然后再從A柱移動到C柱，這樣對結果并沒有影響并且只是做個思想轉換，而且當從A柱移動到C柱，又回到了只有一個盤片的解決方式一樣，
  

當有三個盤片時，我們把三個盤片從上到下編號1，2，3，想要讓A柱編號3的盤片移動到C柱，必須先移開A柱前兩個盤片，然后才可以把A柱編號3的盤片移動到C柱，我們可以直接把前兩個當成一個整體直接移動到B柱，不在意怎么移的，然后把編號3的盤片移動到C柱，如圖：

通過這張圖可得，目前我們已經解決了移動編號3的盤片的問題，那么剩下的問題就是解決在B柱上的兩個盤片該如何操作？這不就是轉變成只有兩個盤片時該如何移動的問題了嗎？雖然現在是在B柱上，那么這跟剛剛有兩個盤片的操作一樣，

后面四個盤片五個盤片…n個盤片都是一樣的遞回思想，至此對于漢諾塔的遞回思想應該是有頭緒了，

總結：
對于有n個盤片的漢諾塔，我們把n-1個盤片當成一個整體移動到B柱（不用去管細節，怎么移動的，反正移到最后一步肯定是這樣的結果，但是得知道，肯定是借助C柱來把這些盤片從A柱移動到B柱，也就是會將其中的柱作為輔助柱來輔助移動，這句等下可以理解代碼），然后把第n個盤片移動到C柱，最后繼續解決n-1個盤片如何移動的問題，一直到n=1時，直接A->C，

因為解決F(N)之前解決F(N-1),而解決F(N-1)之前解決F(N-2)，直到n=1，所以遞回時首先列印的就是n=1時的移動，然后一直一直回退列印，直到最后列印F(N)，跟前兩道的例題運行流程圖一樣，

代碼實作：

public class HanoiTower {
    /**
     *
     * @param n 盤片數
     * @param a 柱子A
     * @param b 柱子B
     * @param c 柱子C
     * @return 移動步驟
     */
    public static void hanoi(int n, char a, char b, char c){
        // 終止條件
        if(n == 1){
            // 剩最后一個盤片時直接從A移動到C
            System.out.println(a + "->" + c);
        } else {
            // 第一步，把n-1當成整體，從A移動到B，以C柱作為輔助柱來輔助移動，但我們只需要移動后的結果，
            hanoi(n-1, a, c, b);
            // 第二步，剩最后一個盤片時直接從A移動到C
            System.out.println(a + "->" + c);
            // 第三步，繼續解決n-1的問題，此時的問題變成在B柱移動到C柱如何操作
            // 從B移動到C，以A柱作為輔助柱
            hanoi(n-1, b, a, c);
        }
    }

    public static void main(String[] args) {
        hanoi(3,'A','B','C');
    }

}

當n=3時，它的運行結果是：

A->C
A->B
C->B
A->C
B->A
B->C
A->C

會疑惑，第一步是A->C???而不是A->B???
正如前面所說，遞回是解決F(N)之前解決F(N-1),而解決F(N-1)之前解決F(N-2)，并且我們是將前兩片當成一個整體的思路移動到B柱，實際上是：編號1的盤片先從A移動到C，然后編號2的盤片從A移動到B，最后編號1的盤片從C移動到B，

我講得好啰嗦，不過應該徹底明白了，

所以在設計遞回演算法時是不需要去在意細節，我們把F(N-1)當作一個整體，去解決F(N)，

參考：
烏梟的遞回整理
漢諾塔

標籤：其他

上一篇：佇列

下一篇：PAT乙級1008