【C语言】学习笔记第9章函数 9.6 递归

布满荆棘的人生 2024-03-22 10:19 66阅读 0赞

### 【C语言】学习笔记 ###

#### 文章目录 ####

*   *  【C语言】学习笔记
     *   *  第9章 函数
         *   *  9.6 递归
             *   *  快速排序算法

#### 第9章 函数 ####

![在这里插入图片描述][bb0918f153f6416e95cdcae7468fa3cc.png_pic_center]

函数是 C 程序的构建块。每个函数本质上是一个自带声明和语句的小程序。可以利用函数 把程序划分成小块，这样便于人们理解和修改程序。由于不必重复编写要多次使用的代码，函 数可以使编程不那么单调乏味。此外，函数可以复用：一个函数最初可能是某个程序的一部分， 但可以将其用于其他程序。

##### 9.6 递归 #####

如果函数调用它本身，那么此函数就是递归的（recursive）。

举个栗子，利用公式  n ! = n × （ n − 1 ) ! n!= n× （n - 1)! n!=n×（n−1)!， 下面的函数可以递归地计算出  n ! n! n!的结果：

int fact(int n) 
    {
         
        if (n <= 1) 
        	return 1; 
        else 
        	return n * fact(n - 1); 
    }

为了了解递归的工作原理，一起来跟踪下面这个语句的执行：

i = fact(3);

下面是实现过程：

fact(3)发现 3 不是小于或等于 1 的，所以 fact(3)调用 
    	fact(2)，此函数发现 2 不是小于或等于 1 的，所以 fact(2)调用 
    		fact(1)，此函数发现 1 是小于或等于 1 的，所以 fact(1)返回 1，从而导致 
    	fact(2)返回 2×1=2，从而导致 
    fact(3)返回 3×2=6。

###### 快速排序算法 ######

对于要求函数调用自身两次或多次的复杂算法来说，递归要用得更多。

实际上，递归经常作为分治法（divide-and-conquer）的结果自然地出现。

这种称为分治法 的算法设计方法把一个大问题划分成多个较小的问题，然后采用相同的算法分别解决这些小问 题。分治法的经典示例就是流行的排序算法——快速排序（quicksort）。

快速排序算法的操作如 下（为了简化，假设要排序的数组的下标从 1 到 n）：

*  (1) 选择数组元素 e（作为“分割元素”），然后重新排列数组，使得元素从 1 一直到 i - 1 都 是小于或等于 e 的，元素 i 包含 e，而元素从 i+1 一直到 n 都是大于或等于 e 的。
 *  (2) 通过递归地采用快速排序方法，对从 1 到 i - 1 的元素进行排序。
 *  (3) 通过递归地采用快速排序方法，对从 i+1 到 n 的元素进行排序。

执行完第(1)步后，元素 e 处在正确的位置上。因为 e 左侧的元素全都是小于或等于 e 的， 所以第(2)步对这些元素进行排序时，这些小于或等于 e 的元素也会处在正确的位置上。类似的 推理也可以应用于 e 右侧的元素。

下面的实例演示了对一个整数数组进行快排的过程：

![在这里插入图片描述][d586edb79d79431f840c302378dee5e8.png_pic_center]

此时我们已经实现了目标：分割元素左侧的所有元素都小于或等于 12，而其右侧的所有元 素都大于或等于 12。既然已经分割了数组，那就可以使用快速排序法对数组的前 4 个元素（10、 3、6 和 7）和后 2 个元素（15 和 18）进行递归快速排序了。

**【程序】快速排序**

`qsort.c`

#include <stdio.h> 
    #define N 10 
    
    void quicksort(int a[], int low, int high);
    int split(int a[], int low, int high);
    
    int main(void)
    {
        
        int a[N], i;
    
        printf("Enter %d numbers to be sorted: ", N);
    
        for (i = 0; i < N; i++)
            scanf("%d", &a[i]);
    
        quicksort(a, 0, N - 1);
    
        printf("In sorted order: ");
    
        for (i = 0; i < N; i++)
            printf("%d ", a[i]);
    
        printf("\n");
    
        return 0;
    }
    
    void quicksort(int a[], int low, int high)
    {
        
        int middle;
    
        if (low >= high) return;
    
        middle = split(a, low, high);
        quicksort(a, low, middle - 1);
        quicksort(a, middle + 1, high);
    }
    
    int split(int a[], int low, int high)
    {
        
    
        int part_element = a[low];
    
        for (;;) {
        
            while (low < high && part_element <= a[high])
                high--;
            if (low >= high) break;
            a[low++] = a[high];
            while (low < high && a[low] <= part_element)
                low++;
            if (low >= high) break;
            a[high--] = a[low];
        }
    
        a[high] = part_element;
    
        return high;
    }

![在这里插入图片描述][d9c9a7f1c56143d1ae1a51b0fca8b564.png_pic_center]

虽然此版本的快速排序可行，但它不是最好的。有许多方法可以用来改进这个程序的性能：

*  改进分割算法。上面介绍的方法不是最有效的。我们不再选择数组中的第一个元素作为 分割元素。更好的方法是取第一个元素、中间元素和最后一个元素的中间值。分割过程 本身也可以加速。特别是在两个 while 循环中避免测试 low < high 是可能的。
 *  采用不同的方法进行小数组排序。不再递归地使用快速排序法，用一个元素从头到尾地 检查数组。针对小数组（比如元素数量少于 25 个的数组）更好的方法是采用较为简单 的方法。
 *  使得快速排序非递归。虽然快速排序本质上是递归算法，并且递归格式的快速排序是最 容易理解的，但是实际上若去掉递归会更高效。

[bb0918f153f6416e95cdcae7468fa3cc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a5d9165030b44a899e1affd93a730652.png
[d586edb79d79431f840c302378dee5e8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/e2e9cef7ac2c4626b8b27160f65a65b6.png
[d9c9a7f1c56143d1ae1a51b0fca8b564.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/036b73f961aa466c88a45aaa4905d427.png