遞推與遞歸 （差別）

遞推與遞歸

本文中部分内容轉自他人部落格，作者相關資訊以及部落格位址在文末。

概念

• 遞歸：從已知問題的結果出發，用疊代表達式逐漸推算出問題的開始的條件，即順推法的逆過程，稱為遞歸。

• 遞歸的定義：在一個函數的定義中又直接或間接地調用本身。

• 遞歸思想： 把規模大的、較難解決的問題變成規模較小的、易解決的同一問題。規模較小的問題又變成規模更小的問題，并且小到一定程度可以直接得出它的解，進而得到原來問題的解。

• 遞歸優點： 符合人的思維方式，遞歸程式結構清晰，可讀性，容易了解

• 遞歸缺點： 通過調用函數實作，當遞歸層數過多時，程式的效率低。例如求Fibonacii數列的第1000項?

• 遞歸的應用場合：

1、資料的定義形式是遞歸的，例如求Fibonacii數列的第n項 。

2、資料之間的邏輯關系（即資料結構）是遞歸的，如樹、圖等的定義和操作。

3、某些問題雖然沒有明顯的遞歸關系或結構，但問題的解法是不斷重複執行一組操作，隻是問題規模由大化小，直至某個原操作（基本操作）就結束。例如：漢諾塔問題。

• 遞歸設計的要素：

1、在函數中必須有直接或間接調用自身的語句；

2、在使用遞歸政策時，必須有一個明确的遞歸結束條件，稱為遞歸出口（或遞歸邊界）。

編寫遞歸算法時，首先要對問題的以下三個方面進行分析：

• 決定問題規模的參數。      

需要用遞歸算法解決的問題，其規模通常都是比較大的，在問題中決定規模大小（或問題複雜程度）的量有哪些？把它們找出來。

• 問題的邊界條件及邊界值。      

在什麼情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。

• 解決問題的通式。      

把規模大的、較難解決的問題變成規模較小、易解決的同一問題，需要通過哪些步驟或公式來實作？這是解決遞歸問題的難點。把這些步驟或公式确定下來。

• 遞推：遞推算法是一種用若幹步可重複運算來描述複雜問題的方法。遞推是序列計算中的一種常用算法。通常是通過計算機前面的一些項來得出序列中的指定象的值。

• 遞推：數學推導 發現規律 重複簡單運算

• 遞歸與遞推差別：相對于遞歸算法,遞推算法免除了資料進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值。

算法舉例1

• 斐波那契數列：已知f(1) = 1 , f(2) = 1 , 且滿足關系式f(n) = f(n-1) + f(n-2)，則f(50)等于多少？

• 分析：根據初始條件f(1) = 1 , f(2) = 1 和關系式f(n) = f(n-1) + f(n-2)，可知，f(3) = f(2) + f(1) , f(3) = f(2) + f(1) …….

• 編寫代碼（遞歸）

public class Fibonacci {

    static int fun(int n){
        if(n == 1 || n == 2){
            return 1 ;
        }else{
            return fun(n-1) + fun(n-2) ;
        }
    }
    public static void main(String[] args) {
        for(int i = 1 ; i <= 15 ; ++i)
        System.out.println(fun(i));
    }
}
           

• 編寫代碼（遞推）

static int fun2(int n){
        int a[] = new int[20] ;
        a[1] = 1 ;
        a[2] = 1 ;
        for(int i=3 ; i<=n ;i++){
            a[i] = a[i-1] + a[i-2] ;
        }
        return a[n] ;
    }
           

• 運作結果：

1

1

2

3

5

8

13

21

34

55

89

144

233

377

610

算法舉例2

• 使用遞歸計算1+2+…+100 ；

• 分析：遞歸關系為f(n) = f(n-1) + n ，遞歸出口為f(1) = 1 ;

• 編寫代碼（遞歸）：

public class Sum {

    static int fun(int n){
        if( n == 1){
            return 1 ;
        }else{
            return fun(n-1) + n ;
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(fun(100));
    }
}
           

• 編寫代碼（遞推）

static int fun2(int n){
        int a[] = new int [200] ;
        a[1] = 1 ;
        for(int i=2 ; i<=n ; i++){
            a[i] = a[i-1] + i ;
        }
        return a[n] ;
    }
           

• 運作結果：

5050

算法舉例3

• 爬樓問題：假設有n階樓梯，每次可爬1階或2階，則爬到第n層有幾種方案？

• 問題分析：
• 假設一階時隻有一種方案f(1) = 1 ;
• 二階時有兩種方案（即一次走一階和一次走兩階）f(2) = 2 ;
• 三階時有3種 f(3) = 3 ;
• 四階時有五種 f(5) = 5 ;
• 發現遞歸規律f(n) = f(n-1) + f(n-2) ;
• 遞歸出口為f(1) = 1、f(2) = 2 ;

• 編寫代碼（遞歸）：

public class Ladder {

    static int fun(int n){
        if(n == 1){
            return 1 ;
        }else if(n == 2){
            return 2 ;
        }else{
            return fun(n-1) + fun(n-2) ;
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(fun(5));
    }
}
           

• 編寫代碼（遞推）：

static int fun2(int n){
        int a[] = new int [200] ;
        a[1] = 1 ;
        a[2] = 2 ;
        for(int i=3 ; i<=n ;i++){
            a[i] = a[i-1] + a[i-2] ;
        }
        return a[n] ;
    }
           

• 運作結果：

8

由上述例子可知，遞歸的重點是找到遞歸關系和遞歸出口。

遞 推 小 結：

1、遞推是從已知條件開始；

2、遞推必須有明确的通用公式；

3、遞推必須是有限次運算。

遞 歸 小 結：

1. 遞歸：未知的推到已知的，再由此傳回。

2. 基本思想：将複雜的操作分解為若幹重複的簡單操作。

關于遞推與遞歸的文章還有：

1. https://blog.csdn.net/a1046765624/article/details/66530637

2. 

--------------------- 

作者：葉清逸 

來源：CSDN 

原文：https://blog.csdn.net/u013634252/article/details/80551060 

版權聲明：本文為部落客原創文章，轉載請附上博文連結！