Chapter2: 時間復雜度分析、遞歸、查找與排序

1. 遞歸

1. 什么是遞歸

表現(xiàn)：

在函數(shù)內部調用函數(shù)本身

應用遞歸的問題特征：

一個問題能夠劃分為更小規(guī)模的子問題求解，通過求解更小規(guī)模的子問題最終得到問題的答案。更具體地來說，即在本次函數(shù)調用中執(zhí)行一小部分任務，然后傳遞一個變化了的參數(shù)，調用該函數(shù)本身執(zhí)行接下來的任務。

組成：

• 函數(shù)內的自我調用
• 出口條件

設計經(jīng)驗：

• 找重復(子問題)

• 找重復中的變化量（參數(shù)）

• 找參數(shù)的變化趨勢和邊界(出口)

  注意設計遞歸時，變化趨勢是大問題 >> 小問題，函數(shù)執(zhí)行時，變化趨勢是解決小問題 >> 解決大問題

練習策略：

• 循環(huán)改遞歸
• 了解經(jīng)典遞歸
• 大量聯(lián)系，總結規(guī)律，掌握套路
• 找到感覺，挑戰(zhàn)更高難度的遞歸(深度優(yōu)先、廣度優(yōu)先等)

2. 簡單的遞歸問題示例

2.1 單分支遞歸

使用遞歸求階乘

設計思路：

• 找重復: n! = n * (n-1)!, 求 (n-1)! 是原問題的重復(規(guī)模更小)
• 找變化: 變化的量應該作為參數(shù)
• 找邊界: 即出口，n>=1

代碼：

int f(int n){
    if(n==1){
        return 1;
    }
    return n*f(n-1);
}

打印 [ i , j ] 之間的整數(shù)

即打印 i, i+1 ,..., j

當然這個用一個循環(huán)就能解決，這里主要是為了講解遞歸的規(guī)律

設計思路:

• 找重復: 每次都是打印操作
• 找變化: 第一次執(zhí)行打印 i , 第二次執(zhí)行打印 i+1 ,..., 直至 i>j
• 找邊界: 即出口，從i開始，到j結束

代碼:

void printItoJ(int i,int j){
    if(i<j){
        return;
    }
    printf("%d ",i);
    printItoJ(i+1);
}

數(shù)組求和

• 找重復: 實際上是不斷地執(zhí)行求和操作
• 找變化: 前邊的求和結果+下一個數(shù)，下一個數(shù)的下標在遞增
• 找邊界: 直至數(shù)組最后一個元素，即i==arr.length-1為最后一次加法

求數(shù)組第 i 個元素到最后一個元素的和

int sumArray(int[] arr,int i){
    if(i==arr.length){
        return 0;
    }
    return arr[i]+sumArray[i+1]；
}

遞歸求最大公約數(shù)(輾轉相除法)

int gcd(int a,int b){
    if(a%b==0){
        return b;
    }
    return gcd(b,a%b);
}

遞歸進行插入排序

插入排序原理示意

1. 從第一個元素開始，該元素可以認為已經(jīng)被排序
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復步驟 3，直到找到小于或等于新元素的已排序的元素
5. 將新元素插入到該元素的位置后
6. 重復步驟 2~5

插入排序原理示意

非遞歸的插入排序實現(xiàn)

以從小到大的排序為例：

就是不斷把新元素與已排序元素從右到左進行比較

• 如果新元素比已排序元素大就不用挪動
• 如果新元素比已排序元素小
  • 將該新元素用 tmp 變量保存
  • 將已排序元素挨個往后挪，直至新元素比已排序元素大，將新元素插入到該元素后

/*按從小到大的插入排序，非遞歸 */
/*
C++中數(shù)組作為函數(shù)參數(shù)是傳址 
*/
void insSort(int arr[],int arrLen){

    //int arrLen = sizeof(arr)/sizeof(arr[0]); 不能在這里計算數(shù)組元素個數(shù)，因為傳入的不是數(shù)組而是其地址 
    for(int i=1;i<arrLen;i++){//第一個元素當作已排列序列，從第二個元素開始排列 
        int tmp=arr[i];//未排序的最靠左的元素 
        int j=i-1;//已排序元的最靠后素的下標 
        while(j>=0 && tmp<arr[j]){//當新元素<已排序元素時，已排序元素挨個往后挪 
            arr[j+1]=arr[j];
            j--;            
        }
        arr[j+1]=tmp;//插入新元素 
    }
    //輸出排序后的數(shù)組 
    for(int i=0;i<arrLen;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
} 

遞歸的插入排序

問題的解決思路：

• 找重復：實質就是 "新元素與已排序元素的比較，并在滿足條件的情況進行按個的元素挪動再插入新元素" 這一過程的不斷重復，隨著已排序元素數(shù)量的增多，問題規(guī)模是在增大的。
• 找變化：問題中每一次排序后，已排序元素數(shù)量+1
• 找邊界：當已排序元素等于數(shù)組元素時結束

然而設計遞歸問題時，函數(shù)的調用方向應該是問題規(guī)模不斷變小的，這樣函數(shù)執(zhí)行時才是 解決小問題>>解決大問題 的方向,這一點需要注意。

遞歸形式的解決思路

• 找重復：對 N 個元素進行插入排序，可以分解為對 N-1個元素進行插入排序的結果與最后一個數(shù)進行排序
• 找變化：不斷深入遞歸，問題規(guī)模減小，層次越深，插入排序函數(shù)的參數(shù)越小
• 找邊界：直到下標為0時，不需要再進行插入排序，到達邊界，函數(shù)返回

代碼

void insSort2(int* arr,int i){
    
    if(i==0){//第1(下標為0)個元素插入排序的結果 
        return;
    }
    
    insSort2(arr,i-1);//第i個元素的插入排序需要第i-1個元素的插入排序的結果 
    
    /*進行第i個元素的插入排序*/
    int tmp=arr[i];//保存未排序的新元素 
    int j=i-1;//最靠右的已排序元素的下標 
    while(j>=0 && tmp<arr[j]){//當新元素小于已排序元素時，不斷將已排序元素挨個往后挪 
        arr[j+1]=arr[j];
        j--;
    } 
    
    arr[j+1]=tmp;//插入新元素 
}

2.2 多分支遞歸

求斐波那契亞數(shù)列第N項

斐波那契亞數(shù)列

第n項=第n-1項+第n-2項

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

發(fā)現(xiàn)多分支遞歸會有很多重復項，可以進行優(yōu)化，之后討論相關內容

斐波那契亞多分支遞歸示意

參考資料

[1] 插入排序步驟講解與實例分析

[2] 插入排序圖文講解

[3] 2.1-2.5 遞歸與排序解法

[4] C語言通過指針訪問一維數(shù)組、二維數(shù)組、三維數(shù)組