算法之遞歸案例

目錄介紹

  • 01.什么是遞歸
  • 02.遞歸三個(gè)條件
  • 03.斐波那契數(shù)列
  • 04.找指定目錄下所有文件
  • 05.求1+2+…+N和
  • 06.求100的階乘
  • 07.有序數(shù)組合并
  • 08.求一個(gè)數(shù)乘方
  • 09.背包問題
  • 10.選擇一支隊(duì)伍
  • 11.漢諾塔問題
  • 12.二分法查找
  • 13.警惕重復(fù)計(jì)算
  • 14.開源項(xiàng)目推薦

01.什么是遞歸

  • 遞歸：在一個(gè)方法內(nèi)部對自身進(jìn)行調(diào)用。利用遞歸可以用簡單的程序來解決一些復(fù)雜的問題。比如：裴波那契數(shù)列的計(jì)算、漢諾塔、快排等問題。
  • 遞歸結(jié)構(gòu)包括兩個(gè)部分：
    • 1、定義遞歸頭。解答：什么時(shí)候不調(diào)用自身方法。如果沒有頭，將陷入死循環(huán)，也就是遞歸的結(jié)束條件。
    • 2、遞歸體。解答：什么時(shí)候需要調(diào)用自身方法。

02.遞歸三個(gè)條件

  • 遞歸需要滿足的三個(gè)條件。剛剛這個(gè)例子是非常典型的遞歸，那究竟什么樣的問題可以用遞歸來解決呢？我總結(jié)了三個(gè)條件，只要同時(shí)滿足以下三個(gè)條件，就可以用遞歸來解決。
  • 1.一個(gè)問題的解可以分解為幾個(gè)子問題的解
    • 何為子問題？子問題就是數(shù)據(jù)規(guī)模更小的問題。比如，前面講的電影院的例子，你要知道，“自己在哪一排”的問題，可以分解為“前一排的人在哪一排”這樣一個(gè)子問題。
  • 2.這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
    • 比如電影院那個(gè)例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一樣的。
  • 3.存在遞歸終止條件+把問題分解為子問題，把子問題再分解為子子問題，一層一層分解下去，不能存在無限循環(huán)，這就需要有終止條件。
  • 還是電影院的例子，第一排的人不需要再繼續(xù)詢問任何人，就知道自己在哪一排，也就是 f(1)=1，這就是遞歸的終止條件。

03.斐波那契數(shù)列

  • 題目要求
    • 大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請你輸出斐波那契數(shù)列的第n項(xiàng)。n<=39
  • 什么是斐波那契數(shù)列？
    • 1，1，2，3，5，8，13，21......斐波那契數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。斐波那契數(shù)列是由數(shù)學(xué)家 Leonardoda Fibonacci 以兔子繁殖為例子而提出的，所以也叫做“兔子數(shù)列”。
  • 解題思路
    • 可以肯定的是這一題通過遞歸的方式是肯定能做出來，但是這樣會(huì)有一個(gè)很大的問題，那就是遞歸大量的重復(fù)計(jì)算會(huì)導(dǎo)致內(nèi)存溢出。另外可以使用迭代法，用fn1和fn2保存計(jì)算過程中的結(jié)果，并復(fù)用起來。下面我會(huì)把兩個(gè)方法示例代碼都給出來并給出兩個(gè)方法的運(yùn)行時(shí)間對比。
  • 采用迭代法： 
    int Fibonacci(int number) {
    if (number <= 0) {
        return 0;
    }
    if (number == 1 || number == 2) {
        return 1;
    }
    int first = 1, second = 1, third = 0;
    for (int i = 3; i <= number; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}
  • 采用遞歸：f(n) = f(n-1) + f(n-2) 
    public int Fibonacci(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1||n==2) {
        return 1;
    }
    return Fibonacci(n - 2) + Fibonacci(n - 1);
}
  • 執(zhí)行時(shí)間對比
    • 假設(shè)n為40我們分別使用迭代法和遞歸法計(jì)算，計(jì)算結(jié)果如下：
      • 1.迭代法：耗費(fèi)時(shí)間1ms
      • 2.遞歸法：耗費(fèi)時(shí)間272ms
  • 為何遞歸效率低
    • 如果簡單分析一下程序的執(zhí)行流，就會(huì)發(fā)現(xiàn)問題在哪，以計(jì)算Fibonacci(5)為例
    • 從上圖可以看出，在計(jì)算Fib(5)的過程中，F(xiàn)ib(1)計(jì)算了兩次、Fib(2)計(jì)算了3次，F(xiàn)ib(3)計(jì)算了兩次，本來只需要5次計(jì)算就可以完成的任務(wù)卻計(jì)算了9次。這個(gè)問題隨著規(guī)模的增加會(huì)愈發(fā)凸顯，以至于Fib(1000)已經(jīng)無法再可接受的時(shí)間內(nèi)算出。
    • 當(dāng)時(shí)使用的是簡單的用定義來求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。這樣的想法是很容易想到的，可是仔細(xì)分析一下我們發(fā)現(xiàn)，當(dāng)調(diào)用fib(n-1)的時(shí)候，還要調(diào)用fib(n-2)，也就是說fib(n-2)調(diào)用了兩次，同樣的道理，調(diào)用f(n-2)時(shí)f(n-3)也調(diào)用了兩次，而這些冗余的調(diào)用是完全沒有必要的?？梢杂?jì)算這個(gè)算法的復(fù)雜度是指數(shù)級的。
  • 遞歸迭代效率比較
    • 遞歸調(diào)用實(shí)際上是函數(shù)自己在調(diào)用自己，而函數(shù)的調(diào)用開銷是很大的，系統(tǒng)要為每次函數(shù)調(diào)用分配存儲空間，并將調(diào)用點(diǎn)壓棧予以記錄。而在函數(shù)調(diào)用結(jié)束后，還要釋放空間，彈?；謴?fù)斷點(diǎn)。所以說，函數(shù)調(diào)用不僅浪費(fèi)空間，還浪費(fèi)時(shí)間。它的很多時(shí)間浪費(fèi)在對函數(shù)調(diào)用的處理上。

04.找指定目錄下所有文件

  • 問題如下所示：
    • 列出（或刪除）指定目錄下的所有文件
  • 實(shí)例代碼，如下所示 
    /**
 * 找出指定目錄下的所有文件
 * 遞歸
 *
 * @param files
 * @return
 */
public static List<File> listFiles(File files) {
    List<File> fileList = new ArrayList<>();
    if (files.isDirectory()) {
        for (File file : files.listFiles()) {
            fileList.addAll(listFiles(file));
        }
    } else {
        fileList.add(files);
    }
    return fileList;
}
  • 測試代碼 
    public static void main(String args[]) {
    List<File> l = listFiles(new File("E:\\yc\\JavaProjectTest\\src"));
    System.out.println("共" + l.size() + "個(gè)文件");
    for (File f : l) {
        System.out.println(f.getName());
        //(這里只打印了文件的文件名)
    }
}

05.求1+2+…+N和

  • 題目要求
    • 問題如下所示：
      • 計(jì)算從1+2+3+…+N的和
    • 示例 : 
      計(jì)算從1+2+3+…+100的和是5050
  • 實(shí)例代碼，如下所示 
    /**
 * 獲取從1+到N的和
 *
 * @param num
 * @return
 */
public static int getSum(int num) {
    if (num == 1) {
        return 1;
    }
    return num + getSum(num - 1);
}
  • 測試代碼 
    public static void main(String args[]) {
     System.out.println(getSum(100));
}

//執(zhí)行結(jié)果
5050

06.求100的階乘

  • 問題如下所示：
    • 求100的階乘
  • 實(shí)例代碼，如下所示 
    public BigInteger sum(int i) {
    if (i == 1) {
        return BigInteger.ONE;
    }
    return BigInteger.valueOf(i).multiply(sum(i - 1));
}
  • 測試代碼 
    public static void main(String[] args) {
    LoopMutiply test = new LoopMutiply();
    try {
        System.out.println("yc計(jì)算結(jié)果：" + test.sum(50) + "!");
    } catch (Exception e) {
        e.printStackTrace();
    }
}

07.有序數(shù)組合并

  • 問題如下所示：
    • 給你兩個(gè)有序數(shù)組，a是{ 1, 3, 4 }，b是{ 2, 3, 5, 6 }，請把他合成一個(gè)新的數(shù)組，然后輸出……
  • 實(shí)例代碼，如下所示 
    // 合并數(shù)組
public static int[] mergeArray(int[] a, int[] b) {
    int result[] = new int[a.length + b.length];
    if (checkSort(a) && checkSort(b)) {
        // 說明ab數(shù)組都是有序的數(shù)組
        // 定義兩個(gè)游標(biāo)
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }
        while (i < a.length) {
            // 說明a數(shù)組還有剩余
            result[k++] = a[i++];
        }
        while (j < b.length) {
            result[k++] = b[j++];
        }
    }
    return result;
}
// 檢查一個(gè)數(shù)組是否是有序1 2 3
public static boolean checkSort(int[] a) {
    boolean flag = false;// 默認(rèn)不是有序的
    for (int i = 0; i < a.length - 1; i++) {
        if (a[i] > a[i + 1]) {
            // 說明不是有序的
            flag = false;
            break;
        } else {
            flag = true;
        }
    }
    return flag;
}
  • 測試結(jié)果 
    public static void main(String[] args) {
    int[] a = { 1, 3, 4 };
    int[] b = { 2, 3, 5, 6 };
    int[] c = mergeArray(a, b);
    for (int n : c) {
        System.out.print(n + " ");
    }
}

08.求一個(gè)數(shù)乘方

  • 問題如下所示：
    • 求一個(gè)數(shù)的乘方
  • 示例 : 
    比如2^8,我們可以會(huì)求表達(dá)式2*2*2*2*2*2*2*2的值，但是如果y的值很大，這個(gè)會(huì)顯得表達(dá)式很冗長。那么由沒有更快一點(diǎn)方法呢？
  • 問題分析
    • 一般稍微復(fù)雜一點(diǎn)的計(jì)算器上面都能求一個(gè)數(shù)的乘法，通常計(jì)算器上面的標(biāo)志是 x^y 這樣的按鍵，表示求 x 的 y 次方。一般情況下我們是如何求一個(gè)數(shù)的乘法的呢？
    • 數(shù)學(xué)公式如下是成立的：(Xa)b = Xa*b
    • 如果如果求28次方，我們可以先假定22=a,于是28 = （22）4 ，那么就是a4 ；假定 a2 = b，那么 a4 = b2，而b2可以寫成(b2)1。于是現(xiàn)在28就轉(zhuǎn)換成：b*b
    • 也就是說我們將乘方的運(yùn)算轉(zhuǎn)換為乘法的運(yùn)算。求xy的值，當(dāng)y是偶數(shù)的時(shí)候，最后能轉(zhuǎn)換成兩個(gè)數(shù)相乘，當(dāng)時(shí)當(dāng)y是奇數(shù)的時(shí)候，最后我們必須要在返回值后面額外的乘以一個(gè)x。
    • x^y= (x2)(y/2)，定義a=x^2,b=y/2, 則得到形如： x^y= a^b;
  • 實(shí)例代碼,如下所示 
    public static int pow(int x,int y){
    if(x == 0 || x == 1){
        return x;
    }
    if(y > 1){
        int b = y/2;
        int a = x*x;
        if(y%2 == 1){//y為奇數(shù)
            return pow(a,b)*x;
        }else{//y為偶數(shù)
            return pow(a,b);
        }
    }else if(y == 0){
        return 1;
    }else{//y==1
        return x;
    }
}
  • 測試結(jié)果 
    public static void main(String[] args) {
    System.out.println("yc計(jì)算結(jié)果：" + pow(2,8) + "!");
}

09.背包問題

  • 問題如下所示：
    • 背包問題也是計(jì)算機(jī)中的經(jīng)典問題。在最簡單的形式中，包括試圖將不同重量的數(shù)據(jù)項(xiàng)放到背包中，以使得背包最后達(dá)到指定的總重量。
  • 示例 :
    • 比如：假設(shè)想要讓背包精確地承重20磅，并且有 5 個(gè)可以放入的數(shù)據(jù)項(xiàng)，它們的重量分別是 11 磅，8 磅，7 磅，6 磅，5 磅。這個(gè)問題可能對于人類來說很簡單，我們大概就可以計(jì)算出 8 磅+ 7 磅 + 5 磅 = 20 磅。但是如果讓計(jì)算機(jī)來解決這個(gè)問題，就需要給計(jì)算機(jī)設(shè)定詳細(xì)的指令了。
  • 問題分析
    • 一、如果在這個(gè)過程的任何時(shí)刻，選擇的數(shù)據(jù)項(xiàng)的總和符合目標(biāo)重量，那么工作便完成了。
    • 二、從選擇的第一個(gè)數(shù)據(jù)項(xiàng)開始，剩余的數(shù)據(jù)項(xiàng)的加和必須符合背包的目標(biāo)重量減去第一個(gè)數(shù)據(jù)項(xiàng)的重量，這是一個(gè)新的目標(biāo)重量。
    • 三、逐個(gè)的試每種剩余數(shù)據(jù)項(xiàng)組合的可能性，但是注意不要去試所有的組合，因?yàn)橹灰獢?shù)據(jù)項(xiàng)的和大于目標(biāo)重量的時(shí)候，就停止添加數(shù)據(jù)。
    • 四、如果沒有合適的組合，放棄第一個(gè)數(shù)據(jù)項(xiàng)，并且從第二個(gè)數(shù)據(jù)項(xiàng)開始再重復(fù)一遍整個(gè)過程。
    • 五、繼續(xù)從第三個(gè)數(shù)據(jù)項(xiàng)開始，如此下去直到你已經(jīng)試驗(yàn)了所有的組合，這時(shí)才知道有沒有解決方案。
  • 實(shí)例代碼,如下所示 
    public class Knapsack {
    private int[] weights; //可供選擇的重量
    private boolean[] selects; //記錄是否被選擇
     
    public Knapsack(int[] weights){
        this.weights = weights;
        selects = new boolean[weights.length];
    }
     
    /**
     * 找出符合承重重量的組合
     * @param total 總重量
     * @param index 可供選擇的重量下標(biāo)
     */
    public void knapsack(int total,int index){
        if(total < 0 || total > 0 && index >= weights.length){
            return;//沒找到解決辦法，直接返回
        }
        if(total == 0){//總重量為0，則找到解決辦法了
            for(int i = 0 ; i < index ; i++){
                if(selects[i] == true){
                    System.out.println(weights[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        selects[index] = true;
        knapsack(total-weights[index], index+1);
        selects[index] = false;
        knapsack(total, index+1);
    }
}
  • 測試結(jié)果 
    public static void main(String[] args) {
    int array[] = {11,9,7,6,5};
    int total = 20;
    Knapsack k = new Knapsack(array);
    k.knapsack(total, 0);
}

10.選擇一支隊(duì)伍

  • 問題如下所示：
    • 在數(shù)學(xué)中，組合是對事物的一種選擇，而不考慮他們的順序。
  • 示例 :
    • 比如有5個(gè)登山隊(duì)員，名稱為A,B,C,D和E。想要從這五個(gè)隊(duì)員中選擇三個(gè)隊(duì)員去登峰，這時(shí)候如何列出所有的隊(duì)員組合。（不考慮順序）
  • 問題分析
    • 還是以遞歸的思想來解決：首先這五個(gè)人的組合選擇三個(gè)人分成兩個(gè)部分，第一部分包含A隊(duì)員，第二部分不包含A隊(duì)員。假設(shè)把從 5 個(gè)人中選出 3 個(gè)人的組合簡寫為（5,3），規(guī)定 n 是這群人的大小，并且 k 是組隊(duì)的大小。那么根據(jù)法則可以有：
    • (n,k) = (n-1,k-1) + (n-1,k)
    • 對于從 5 個(gè)人中選擇 3 個(gè)人，
    • 有：(5,3) = (4,2)+(4,3)
    • (4,2)表示已經(jīng)有A隊(duì)員了，然后從剩下的4個(gè)隊(duì)員中選擇2個(gè)隊(duì)員，(4,3)表示從5個(gè)人中剔除A隊(duì)員，從剩下的4個(gè)隊(duì)員中選擇3個(gè)隊(duì)員，這兩種情況相加就是從5個(gè)隊(duì)員中選擇3個(gè)隊(duì)員。
    • 現(xiàn)在已經(jīng)把一個(gè)大問題轉(zhuǎn)換為兩個(gè)小問題了。從4個(gè)人的人群中做兩次選擇（一次選擇2個(gè)，一次選擇3個(gè)），而不是從5個(gè)人的人群中選擇3個(gè)。
    • 從4個(gè)人的人群中選擇2個(gè)人，又可以表示為：(4,2) = (3,1) + (3,2)，以此類推，很容易想到遞歸的思想。
  • 實(shí)例代碼,如下所示 
    public class Combination {
    private char[] persons;//組中所有可供選擇的人員
    private boolean[] selects;//標(biāo)記成員是否被選中，選中為true
     
    public Combination(char[] persons){
        this.persons = persons;
        selects = new boolean[persons.length];
    }
    public void showTeams(int teamNumber){
        combination(teamNumber,0);
    }
    /**
     *
     * @param teamNumber 需要選擇的隊(duì)員數(shù)
     * @param index 從第幾個(gè)隊(duì)員開始選擇
     */
    public void combination(int teamNumber,int index){
        if(teamNumber == 0){//當(dāng)teamNumber=0時(shí)，找到一組
            for(int i = 0 ; i < selects.length ; i++){
                if(selects[i] == true){
                    System.out.print(persons[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        //index超過組中人員總數(shù)，表示未找到
        if(index >= persons.length ){
            return;
        }
        selects[index] = true;
        combination(teamNumber-1, index+1);
        selects[index] = false;
        combination(teamNumber, index+1);
    }
}
  • 測試結(jié)果 
    public static void main(String[] args) {
    char[] persons = {'A','B','C','D','E'};
    Combination cb = new Combination(persons);
    cb.showTeams(3);
}

11.漢諾塔問題

  • 問題如下所示：
    • 漢諾塔問題是由很多放置在三個(gè)塔座上的盤子組成的一個(gè)古老的難題。所有盤子的直徑是不同的，并且盤子中央都有一個(gè)洞使得它們剛好可以放在塔座上。所有的盤子剛開始都放置在A 塔座上。這個(gè)難題的目標(biāo)是將所有的盤子都從塔座A移動(dòng)到塔座C上，每次只可以移動(dòng)一個(gè)盤子，并且任何一個(gè)盤子都不可以放置在比自己小的盤子之上。
  • 示例 :
    • 試想一下，如果只有兩個(gè)盤子，盤子從小到大我們以數(shù)字命名（也可以想象為直徑），兩個(gè)盤子上面就是盤子1，下面是盤子2，那么我們只需要將盤子1先移動(dòng)到B塔座上，然后將盤子2移動(dòng)到C塔座，最后將盤子1移動(dòng)到C塔座上。即完成2個(gè)盤子從A到C的移動(dòng)。
    • 如果有三個(gè)盤子，那么我們將盤子1放到C塔座，盤子2放到B塔座，在將C塔座的盤子1放到B塔座上，然后將A塔座的盤子3放到C塔座上，然后將B塔座的盤子1放到A塔座，將B塔座的盤子2放到C塔座，最后將A塔座的盤子1放到C塔座上。
  • 問題分析
    • 如果有四個(gè)，五個(gè)，N個(gè)盤子，那么我們應(yīng)該怎么去做？這時(shí)候遞歸的思想就很好解決這樣的問題了，當(dāng)只有兩個(gè)盤子的時(shí)候，我們只需要將B塔座作為中介，將盤子1先放到中介塔座B上，然后將盤子2放到目標(biāo)塔座C上，最后將中介塔座B上的盤子放到目標(biāo)塔座C上即可。
    • 所以無論有多少個(gè)盤子，我們都將其看做只有兩個(gè)盤子。假設(shè)有 N 個(gè)盤子在塔座A上，我們將其看為兩個(gè)盤子，其中(N-1)~1個(gè)盤子看成是一個(gè)盤子，最下面第N個(gè)盤子看成是一個(gè)盤子，那么解決辦法為：
      • ①、先將A塔座的第(N-1)~1個(gè)盤子看成是一個(gè)盤子，放到中介塔座B上，然后將第N個(gè)盤子放到目標(biāo)塔座C上。
      • ②、然后A塔座為空，看成是中介塔座，B塔座這時(shí)候有N-1個(gè)盤子，將第(N-2)~1個(gè)盤子看成是一個(gè)盤子，放到中介塔座A上，然后將B塔座的第(N-1)號盤子放到目標(biāo)塔座C上。
      • ③、這時(shí)候A塔座上有(N-2)個(gè)盤子，B塔座為空，又將B塔座視為中介塔座，重復(fù)①，②步驟，直到所有盤子都放到目標(biāo)塔座C上結(jié)束。
    • 簡單來說，跟把大象放進(jìn)冰箱的步驟一樣，遞歸算法為：
      • ①、從初始塔座A上移動(dòng)包含n-1個(gè)盤子到中介塔座B上。
      • ②、將初始塔座A上剩余的一個(gè)盤子（最大的一個(gè)盤子）放到目標(biāo)塔座C上。
      • ③、將中介塔座B上n-1個(gè)盤子移動(dòng)到目標(biāo)塔座C上。
  • 實(shí)例代碼,如下所示 
    /**
 * 漢諾塔問題
 * @param dish 盤子個(gè)數(shù)(也表示名稱)
 * @param from 初始塔座
 * @param temp 中介塔座
 * @param to   目標(biāo)塔座
 */
public static void move(int dish,String from,String temp,String to){
    if(dish == 1){
        System.out.println("將盤子"+dish+"從塔座"+from+"移動(dòng)到目標(biāo)塔座"+to);
    }else{
        move(dish-1,from,to,temp);//A為初始塔座，B為目標(biāo)塔座，C為中介塔座
        System.out.println("將盤子"+dish+"從塔座"+from+"移動(dòng)到目標(biāo)塔座"+to);
        move(dish-1,temp,from,to);//B為初始塔座，C為目標(biāo)塔座，A為中介塔座
    }
}
  • 測試結(jié)果 
    move(3,"A","B","C");

12.二分法查找

  • 問題如下所示：
    • 一個(gè)一系列數(shù)組，然后找到某個(gè)值的索引
  • 問題分析
    • 一定是有序表,升序降序都可以
  • 實(shí)例代碼,如下所示 
    /**
 * @param array 有序數(shù)組,但不限于數(shù)組
 * @param start 開始查找的數(shù)組下標(biāo)
 * @param end 結(jié)束查找的數(shù)組下標(biāo)
 * @param searchValue 要搜索的值
 * @return
 */
public static int search(int[] array, int start, int end, int searchValue){
    if (array != null && array.length > 0){
        int middle = (start + end) / 2;
        int middleValue = array[middle];
        if (searchValue == middleValue){
            return middle;
        }else if (searchValue < middleValue){
            //查詢值小于中值,在中值前面再次搜索,縮小范圍
            return search(array, start, middle-1, searchValue);
        }else {
            //查詢值大于中值,在中值后面再次搜索,縮小范圍
            return search(array, middle+1, end, searchValue);
        }
    }else {
        return -1;
    }
}
  • 測試結(jié)果 
    public static void main(String[] args) {
    int[] array = {1,3,5,7,9,12,14,15,19,20,22,23,28,30};
    System.out.println(search(array, 0, array.length-1, 20));
}

13.警惕重復(fù)計(jì)算

  • 除此之外，使用遞歸時(shí)還會(huì)出現(xiàn)重復(fù)計(jì)算的問題。剛才講的第三個(gè)遞歸代碼的例子，如果我們把整個(gè)遞歸過程分解一下的話，那就是這樣的：
  • 想要計(jì)算 f(5)，需要先計(jì)算 f(4) 和 f(3)，而計(jì)算 f(4) 還需要計(jì)算 f(3)，因此，f(3) 就被計(jì)算了很多次，這就是重復(fù)計(jì)算問題。
  • 為了避免重復(fù)計(jì)算，我們可以通過一個(gè)數(shù)據(jù)結(jié)構(gòu)（比如散列表）來保存已經(jīng)求解過的 f(k)。當(dāng)遞歸調(diào)用到 f(k) 時(shí)，先看下是否已經(jīng)求解過了。如果是，則直接從散列表中取值返回，不需要重復(fù)計(jì)算，這樣就能避免剛講的問題了。
  • 按照上面的思路，我們來改造一下剛才的代碼： 
    public int Fibonacci(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
   
  // hasSolvedList 可以理解成一個(gè) Map，key 是 n，value 是 f(n)
  if (hasSolvedList.containsKey(n)) {
    return hasSovledList.get(n);
  }
   
  int ret = f(n-1) + f(n-2);
  hasSovledList.put(n, ret);
  return ret;
}
  • 除了堆棧溢出、重復(fù)計(jì)算這兩個(gè)常見的問題。遞歸代碼還有很多別的問題。在時(shí)間效率上，遞歸代碼里多了很多函數(shù)調(diào)用，當(dāng)這些函數(shù)調(diào)用的數(shù)量較大時(shí)，就會(huì)積聚成一個(gè)可觀的時(shí)間成本。

14.開源項(xiàng)目推薦

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 在C語言中,五種基本數(shù)據(jù)類型存儲空間長度的排列順序是: A)char B)char=int<=float C)ch...
    夏天再來閱讀 4,042評論 0贊 2
  • Java經(jīng)典問題算法大全 /*【程序1】 題目：古典問題：有一對兔子，從出生后第3個(gè)月起每個(gè)月都生一對兔子，小兔子...
    趙宇_阿特奇閱讀 2,077評論 0贊 2
  • 回溯算法 回溯法：也稱為試探法，它并不考慮問題規(guī)模的大小，而是從問題的最明顯的最小規(guī)模開始逐步求解出可能的答案，并...
    fredal閱讀 14,010評論 0贊 89
  • 專業(yè)考題類型管理運(yùn)行工作負(fù)責(zé)人一般作業(yè)考題內(nèi)容選項(xiàng)A選項(xiàng)B選項(xiàng)C選項(xiàng)D選項(xiàng)E選項(xiàng)F正確答案 變電單選GYSZ本規(guī)程...
    小白兔去釣魚閱讀 10,561評論 0贊 13
  • 《從受歡迎到被需要》中學(xué)習(xí)到一個(gè)詞匯，叫人際交往中的邊界感。 每個(gè)人都會(huì)有自己的交際邊界，有自己的禁區(qū)，一旦越過就...
    HR弟閱讀 954評論 0贊 1

友情鏈接更多精彩內(nèi)容