Chapter2: 时间复杂度分析、递归、查找与排序

1. 递归

1. 什么是递归

表现：

在函数内部调用函数本身

应用递归的问题特征：

一个问题能够划分为更小规模的子问题求解，通过求解更小规模的子问题最终得到问题的答案。更具体地来说，即在本次函数调用中执行一小部分任务，然后传递一个变化了的参数，调用该函数本身执行接下来的任务。

组成：

• 函数内的自我调用
• 出口条件

设计经验：

• 找重复(子问题)

• 找重复中的变化量（参数）

• 找参数的变化趋势和边界(出口)

  注意设计递归时，变化趋势是大问题 >> 小问题，函数执行时，变化趋势是解决小问题 >> 解决大问题

练习策略：

• 循环改递归
• 了解经典递归
• 大量联系，总结规律，掌握套路
• 找到感觉，挑战更高难度的递归(深度优先、广度优先等)

2. 简单的递归问题示例

2.1 单分支递归

使用递归求阶乘

设计思路：

• 找重复: n! = n * (n-1)!, 求 (n-1)! 是原问题的重复(规模更小)
• 找变化: 变化的量应该作为参数
• 找边界: 即出口，n>=1

代码：

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

打印 [ i , j ] 之间的整数

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

当然这个用一个循环就能解决，这里主要是为了讲解递归的规律

设计思路:

• 找重复: 每次都是打印操作
• 找变化: 第一次执行打印 i , 第二次执行打印 i+1 ,..., 直至 i>j
• 找边界: 即出口，从i开始，到j结束

代码:

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

数组求和

• 找重复: 实际上是不断地执行求和操作
• 找变化: 前边的求和结果+下一个数，下一个数的下标在递增
• 找边界: 直至数组最后一个元素，即i==arr.length-1为最后一次加法

求数组第 i 个元素到最后一个元素的和

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

递归求最大公约数(辗转相除法)

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

递归进行插入排序

插入排序原理示意

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤 3，直到找到小于或等于新元素的已排序的元素
5. 将新元素插入到该元素的位置后
6. 重复步骤 2~5

插入排序原理示意

非递归的插入排序实现

以从小到大的排序为例：

就是不断把新元素与已排序元素从右到左进行比较

• 如果新元素比已排序元素大就不用挪动
• 如果新元素比已排序元素小
  • 将该新元素用 tmp 变量保存
  • 将已排序元素挨个往后挪，直至新元素比已排序元素大，将新元素插入到该元素后

/*按从小到大的插入排序，非递归 */
/*
C++中数组作为函数参数是传址 
*/
void insSort(int arr[],int arrLen){

    //int arrLen = sizeof(arr)/sizeof(arr[0]); 不能在这里计算数组元素个数，因为传入的不是数组而是其地址 
    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;//插入新元素 
    }
    //输出排序后的数组 
    for(int i=0;i<arrLen;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
} 

递归的插入排序

问题的解决思路：

• 找重复：实质就是 "新元素与已排序元素的比较，并在满足条件的情况进行按个的元素挪动再插入新元素" 这一过程的不断重复，随着已排序元素数量的增多，问题规模是在增大的。
• 找变化：问题中每一次排序后，已排序元素数量+1
• 找边界：当已排序元素等于数组元素时结束

然而设计递归问题时，函数的调用方向应该是问题规模不断变小的，这样函数执行时才是 解决小问题>>解决大问题 的方向,这一点需要注意。

递归形式的解决思路

• 找重复：对 N 个元素进行插入排序，可以分解为对 N-1个元素进行插入排序的结果与最后一个数进行排序
• 找变化：不断深入递归，问题规模减小，层次越深，插入排序函数的参数越小
• 找边界：直到下标为0时，不需要再进行插入排序，到达边界，函数返回

代码

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 多分支递归

求斐波那契亚数列第N项

斐波那契亚数列

第n项=第n-1项+第n-2项

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

发现多分支递归会有很多重复项，可以进行优化，之后讨论相关内容

斐波那契亚多分支递归示意

参考资料

[1] 插入排序步骤讲解与实例分析

[2] 插入排序图文讲解

[3] 2.1-2.5 递归与排序解法

[4] C语言通过指针访问一维数组、二维数组、三维数组