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 = 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的位置，再遞歸調用快排函數。

六、總結

遞歸是一種常用的編程技巧，能夠解決許多問題。但是遞歸也存在一些缺點，如遞歸層數過多容易導致棧溢出等問題。在使用遞歸時應該注意終止條件和遞歸深度的控制。