【C语言】递归 & 汉罗塔 & 快速排序

递归

递归是一种编程思想，但是在实际的开发中除特定场景外，尽量不要使用递归

使用递归求解阶乘

#include <stdio.h>

int fact(int);

int fact(int i) {

    long res = 1L; // 计算结果

    if (i > 0) {
        res = i * fact(i - 1);
    }
    return res;
}

int main(void) {
    long res = fact(30);
    printf("res = %ld", res); // 输出 long 类型
    return 0;
}

汉罗塔

汉罗塔的C语言实现

#include <stdio.h>

void hanoi(int n, char x, char y, char z);

void hanoi(int n, char x, char y, char z) {
    if (n == 1) {
        printf("%c --> %c \n", x, z);
    } else {
        hanoi(n - 1, x, z, y);
        printf("%c --> %c \n", x, z);
        hanoi(n - 1, y, x, z);
    }
}

int main() {
    int n;
    printf("请输入层数：");
    scanf("%d", &n);
    hanoi(n, 'X', 'Y', 'Z');
    return 0;

快速排序

#include <stdio.h>

void quick_sort(int array[], int left, int right);

void quick_sort(int array[], int left, int right) {

    int i = left, j = right; // 左右索引
    int pivot; // 中间基准变量
    int temp; // 替换元素的临时变量

    pivot = array[(right +left) / 2];

    while (i <= j){
        // 遍历右边的 小
        while (array[i] < pivot) {i++;};

        // 遍历左边的 大
        while (array[j] > pivot){j--;};

        // 左右大小交换
        if (i <= j){
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        };
    }

    if (left < j){quick_sort(array, left, j);}

    if (i<right){quick_sort(array, i, right);}
}

int main(void) {
    int array[] = {33, 12, 4, 8, 45, 56, 78, 9, 56}; // 待排序数组
    int length;

    length = sizeof(array) / sizeof(array[0]);// 数组长度  数组占用长度 / 其中一个元素长度
    quick_sort(array,0,length - 1);

    for (int k = 0; k < length; ++k) {
        printf("%d ", array[k]);
    }
    putchar("\n");
    return 0;
}

快速排序原理