C递归算法经典实例

一、递归的概念

递归是指函数自己调用自己，通常在解决问题时使用。在C语言中，递归实现的问题与循环实现的问题一样，只是解决问题的思路不同。

递归函数有两个重要的特点：

• 自己调用自己，直到达到某个条件后停止
• 必须有终止条件，否则会一直递归下去，导致栈溢出

二、递归实例：斐波那契数列

斐波那契数列是指：第一项和第二项均为1，第三项开始每一项均为前两项之和，即：1, 1, 2, 3, 5, 8, 13, ……

可使用递归函数实现斐波那契数列：

int fibonacci(int n){
    if(n <= 1){
        return n;
    }
    else{
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

上述代码中，当n为1或0时，直接返回n的值，否则返回前两项之和。

三、递归实例：阶乘

阶乘是指从1到n所有整数的乘积，由于阶乘增长速度快，因此使用递归来求解。

使用递归函数求解阶乘：

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

上述代码中，当n为0或1时，返回1，否则返回n乘以(n-1)的阶乘。

四、递归实例：汉诺塔

汉诺塔是一种经典问题，题目描述：有三个柱子A，B，C，在A柱子上有n个盘子，盘子大小不一，大的在下面，小的在上面。现在需要将A柱子上的n个盘子全部移动到C柱子上，移动过程中要保证大盘子在下面，小盘子在上面，且每次只能移动一个盘子。

使用递归函数实现汉诺塔：

void hanoi(int n, char a, char b, char c){
    if(n == 1){
        printf("Move disk %d from %c to %c\n", n, a, c);
    }
    else{
        hanoi(n-1, a, c, b);
        printf("Move disk %d from %c to %c\n", n, a, c);
        hanoi(n-1, b, a, c);
    }
}

上述代码中，当n为1时直接将盘子从a移动到c，否则将n-1个盘子从a经过c移动到b，将第n个盘子从a移动到c，最后将n-1个盘子从b经过a移动到c。

五、递归实例：快排

快速排序是一种高效的排序算法，使用递归可以简单实现。

使用递归函数实现快速排序：

void quick_sort(int arr[], int left, int right){
    if(left < right){
        int i = left, j = right, pivot = arr[left];
        while(i < j){
            while(i < j && arr[j] >= pivot){
                j--;
            }
            if(i < j){
                arr[i++] = arr[j];
            }
            while(i < j && arr[i] < pivot){
                i++;
            }
            if(i < j){
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quick_sort(arr, left, i-1);
        quick_sort(arr, i+1, right);
    }
}

上述代码中，取最左边的数为基点，设两个指针，i从左边开始，j从右边开始，交换i和j指向的数，直到i>=j，将基点放到i的位置，再递归调用快排函数。

六、总结

递归是一种常用的编程技巧，能够解决许多问题。但是递归也存在一些缺点，如递归层数过多容易导致栈溢出等问题。在使用递归时应该注意终止条件和递归深度的控制。