第7章 C语言的递归函数 (六)

文档视频讲解链接地址

1. 腾讯课堂链接 : 72_函数_递归函数
2. 腾讯课堂链接 : 73_函数_快速排序

7.6 递归函数

1. 什么是递归

   • 简单的定义: 当函数直接或者间接调用自己时，则发生了递归。

     

2. 递归函数

   • 递归函数是指一个函数的函数体中直接调用或间接调用了该函数自身。
   • 直接调用：指一个函数的函数体中含有调用自身的语句，
   • 间接调用：指一个函数在函数体里调用了其它函数，而其它函数又会调用该函数的情况。

3. 递归函数的执行过程分为两个阶段：

   • 递推阶段：从原问题出发，按递归公式递推从未知到已知，最终达到递归终止条件。
   • 回归阶段：按递归终止条件求出结果，逆向逐步代入递归公式，回归到原问题求解。

4. 递推阶段

   • 递推部分是一个分解问题的过程，每一次调用自身，都会重新初始化，重新为形参n开辟内存空间。
   • 函数一次次被自身调用，当不能再次调用自己时，说明递推阶段结束。

5. 回归阶段

   • 回归是一个不断返回主调函数的过程，先执行最底层的函数体，然后再利用该层的返回值result（不一定是return值，任何在函数运行中被调用到的处于最后状态的值都算是返回值），返回到其主调函数main（）中。
   • 当满足了main函数中输出的要求，且已经到了回归的最顶层，表示回归阶段结束，返回主调函数main()。

6. 实例100

   • 用递归函数的方式，求1+2+3+···+100之和。
   • 源文件

   01-cbase\100-ditui.c
   1

   • 源代码

   #include  
   
   int sum = 0 ; 
   void mysum(int i)
   {
       printf("mysum:%d\n",i); // 正常要执行的语句  
       sum = sum + i; 
       i ++; // 必须有有一个条件时刻变化  
   
       if(i > 100) return;   // 要想正常使用递归 ,必须有终止条件 
   
       mysum(i) ; // 自己调用自己 
   }
   
   
   int main(int argc, char const *argv[])
   {
       mysum(1);
       printf("sum=%d\n",sum);
       return 0;
   }
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

   • 运行结果

   mysum:1
   mysum:2
   mysum:3
   mysum:4
   mysum:5
   mysum:6
   mysum:7
   ... 
   mysum:94
   mysum:95
   mysum:96
   mysum:97
   mysum:98
   mysum:99
   mysum:100
   sum=5050
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16

7.7 递归应用-快速排序法

1. 快速排序法

   • 基本原理：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

     

2. 快速排序的过程

   1. 从待排序的数中选取一个数作为基准数，一般选取第一个数。
   2. 把比基准数大的数放在基准数后面，把比基准数小的数放在基准数前面。
   3. 对基准数的左边和右边分别作第2步处理，需要多次进行操作，采取递归的方式。
   4. 对于拆分出来的两个区间的再次拆分，根据上次拆分的基准数下标来确定这两个区间的low、hight。
   5. 在拆分的时候，low和hight都往中间靠拢，最后low和hight是要重合的，这个重合的位置就是基准值要存放的位置，也是要返回的位置。
   6. 直到左右区间不能在拆分时，完成排序。

3. 实例

   • 
   • 
   • 代码如下:

   void quick_sort(int *a, int left, int right)  
   {
       if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
       {
           return ;
       }
       int i = left;
       int j = right;
       int key = a[left];
       while(i < j)                            // 控制在当组内寻找一遍 
       {
           // 而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）
           // 2，没有符合条 件1的，并且i与j的大小没有反转 
           while(i < j && key <= a[j])
               {   
               j--;   /*向前寻找*/ 
           }    
           a[i] = a[j]; // a[i] 和a[j]交换 这是伪代码 
           // 找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是 a[left]，那么就是给key）
           /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反， 因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/    
           while(i < j && key >= a[i])
           { 
               i++; 
           }
           a[j] = a[i];  // a[i] 和a[j]交换 这是伪代码 
          
           sort(a, left, i - 1);    /*最后用同样的方式对分出来的左边的小组进行同上的做法*/
           sort(a, i + 1, right);   /*用同样的方式对分出来的右边的小组进行同上的做法*/
           /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31

4. 实例101

   • 用递归函数的方式，实现快速排序
   • 源文件

   01-cbase\101-quick_sort.c
   1

   • 源代码

   #include 
   
   #define N 6
   
   int display_array(int *pa, int n )
   {
       printf("数组的内容为 >:");
       for (int i = 0; i < n; i++)
       {
           printf("%d ", pa[i]);
       }
       printf("\n");
       return 0;
   }
   
   /*
    * 函数功能 :  快速排序法
    * 参数     :
    * a       : 数组名, 也是数组的首地址
    * left    : 数组的第一个元素下标 = 0
    * right   : 数组的最后一个元素下标 数组元素个数-1
    * 返回值:
    * 成功返回 : 0
    * 失败返回 : -1
    */
   int quick_sort(int *a, int left, int right)
   {
       int i = left;    // i 指向数组第一个元素下标
       int j = right;   // j 指向数组的最后一个元素下标
       int k = a[left]; // 数组第一个元素的值
   
       // 在使用递归时, 一定不能少递归结束条件  
       if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
       {   
           return 0;
       }
   
   
       while (i<j)  // i < j  说明 没有碰头 , i>=j, 表示碰头(第一次比较结束)
       {
           // 计算比 j 小的部分
           // 这种情况是 k比数组右边元素小, 此时要递减j
           // 找到比k 小的数, 并把这个数和k(数组的第一个元素)交换
           while ((i<j)&&(k <= a[j]))
           {
               j--;
           }
           // k > a[j]  表示找到了比k小的数, 要交换 a[i] <=> a[j]
           int t = a[i];
           a[i] = a[j];
           a[j] = t;
          // display_array(a, N);
   
           // 计算比 i 大的部分
           // 这种情况是 k比数组左边元素大, 此时要递增i
           // 找到比k 大的数, 并把这个数和k(数组的第一个元素)交换
           while ((i<j)&&(a[i] <= k))
           {
               i++;
           }
           // a[j] >k  表示找到了比k大的数, 要交换 a[i] <=> a[j]
           t = a[i];
           a[i] = a[j];
           a[j] = t;
          // display_array(a, N);
       }
       quick_sort(a,left,i-1) ;// 左边分组 
       quick_sort(a,i+1,right); // 右边边分组 
   
   
       return 0;
   }
   
   int main(int argc, char const *argv[])
   {
       int a[N] = {6, 2, 7, 3, 8, 9};
       display_array(a, N);
       quick_sort(a, 0, N - 1);
       display_array(a, N);
   
       return 0;
   }
   
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83

   • 运算结果

   数组的内容为 >:6 2 7 3 8 9 
   数组的内容为 >:2 3 6 7 8 9
   1
   2