前言

在 C 語言的學習旅程中，函數遞歸是一個既有趣又極具挑戰(zhàn)性的概念。它為我們提供了一種獨特的解決問題的思路，就像一把神奇的鑰匙，能打開許多復雜問題的大門。今天，就讓我們一起深入探索函數遞歸的世界

一、遞歸的概念與思想

遞歸，簡單來說，就是函數自己調用自己。這聽起來有點像在一個無限循環(huán)里打轉，但實際上它有著明確的邏輯和目的。在 C 語言中，遞歸是一種強大的解決問題的方法，其核心思想是把一個大型復雜問題層層轉化為一個與原問題相似，但規(guī)模較小的子問題來求解。直到子問題不能再被拆分，遞歸就結束了，這就是把大事化小的過程。

我們來看一個簡單的示例代碼：

#include <stdio.h>
int main()
{
    printf("hehe\n");
    main();//main函數中又調用了main函數
    return 0;
}

這段代碼展示了遞歸的基本形式，但它只是為了演示，并非用于實際解決問題。由于沒有設置限制條件，它會陷入死遞歸，最終導致棧溢出（Stack overflow）。就好比一個人在一條沒有盡頭的走廊里一直往前走，永遠也走不出去，最后精疲力竭。

二、遞歸的限制條件 

為了避免遞歸陷入死循環(huán)，我們在使用遞歸時必須遵循兩個必要條件：

存在限制條件：當滿足這個限制條件的時候，遞歸便不再繼續(xù)。這個限制條件就像是給遞歸設定了一個終點，告訴它什么時候該停下來。

每次遞歸調用之后越來越接近這個限制條件：這確保了遞歸能夠逐步收斂，最終達到限制條件，結束遞歸過程。

三、遞歸的實際應用舉例

（一）求 n 的階乘

一個正整數的階乘（factorial）是所有小于及等于該數的正整數的積，并且 0 的階乘為 1，自然數 n 的階乘寫作 n! 。其公式為：

根據這個公式，我們可以編寫如下函數來計算 n 的階乘：

int Fact(int n)
{
    if(n==0)
        return 1;
    else
        return n*Fact(n-1);
}

在這個函數中，當 n 等于 0 時，遞歸結束，返回 1；否則，繼續(xù)調用 Fact 函數，將問題規(guī)模逐漸縮小，直到 n 為 0。

測試代碼：（這?不考慮n太?的情況，n太大存在溢出）

棧溢出指的是當程序在棧上不斷分配內存，使得棧的使用空間超出了預先分配的最大容量，就會發(fā)生棧溢出錯誤。這就好像一個容量有限的容器，不斷往里面裝東西，最終東西多得裝不下了。

遞歸函數在調用自身時，每一次調用都會在棧上創(chuàng)建一個新的棧幀。如果遞歸沒有合理的終止條件，或者遞歸深度過大，?？臻g就會不斷被占用，最終導致棧溢出。

（二）順序打印一個整數的每一位

輸入一個整數 m，按照順序打印整數的每一位。例如，輸入 1234，輸出 1 2 3 4 。我們可以通過 %10 和 / 10 操作來拆分整數的每一位。假設想寫一個函數 Print 來打印 n 的每一位，其實現思路如下：

void Print(int n)
{
    if(n>9)
    {
        Print(n/10);
    }
    printf("%d ", n%10);
}

在這個函數中，如果 n 大于 9，就繼續(xù)調用 Print 函數處理 n/10，直到 n 為一位數，然后打印 n%10。這樣就實現了順序打印整數的每一位。

四、遞歸與迭代的比較 

遞歸雖然是一種強大的編程技巧，但它也有自己的局限性。在遞歸函數調用的過程中，每一次函數調用都需要在內存的棧區(qū)申請一塊內存空間來保存函數調用期間的各種局部變量的值，這塊空間被稱為運行時堆?；蚝瘮禇?。如果遞歸層次太深，就會浪費太多的棧幀空間，甚至可能引起棧溢出的問題。

相比之下，迭代（通常就是循環(huán)的方式）在很多情況下效率更高。以計算 n 的階乘為例，使用迭代方式的代碼如下：

int Fact(int n)
{
    int i = 0;
    int ret = 1;
    for(i=1; i<=n; i++)
    {
        ret *= i;
    }
    return ret;
}

這段代碼通過循環(huán)實現了與遞歸相同的功能，而且效率更高。因為它不需要頻繁地開辟和釋放棧幀空間

再比如計算第 n 個斐波那契數，斐波那契數列的遞歸公式為：

按照這個公式編寫的遞歸代碼在計算較大的 n 時效率極低，因為會產生大量的重復計算。例如，在計算第 40 個斐波那契數時，第 3 個斐波那契數就被重復計算了 39088169 次。而使用迭代方式可以大大提高效率：

int Fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    while(n>2)
    {
        c = a+b;
        a = b;
        b = c;
        n--;
    }
    return c;
}

五、遞歸的拓展應用

斐波那契數列的特點是前兩個數為 1，從第三個數開始，每個數都等于前兩個數之和。用遞歸方式計算第n個斐波那契數的代碼如下：

int Fib(int n)
{ 
    if(n==0)
       return 0;
    if(n==1)
       return 1;
    else
       return Fib(n-1)+Fib(n-2);
}

然而，當n較大時，如n=50，使用這種遞歸方式計算會花費極長的時間，因為遞歸過程中存在大量重復計算。為了優(yōu)化，可以采用迭代方式:

int Fib(int n)
{   
    int a = 1;
    int b =1;
    int c= 1;
    while(n>2)
    { 
        C= atb;
        a =b;
        n--j
    }
       
    return c;
}

迭代方式從前往后依次計算斐波那契數，避免了重復計算，大大提高了效率   

青蛙跳臺階問題

一只青蛙一次可以跳上1級臺階，也可以跳上2 級臺階，求青蛙跳上n級臺階總共有多少種跳法。這是一個可以用遞歸很好解決的問題。假設跳上n級臺階的跳法數為F(n)，則有F(N) = F(N-1)+F(N-2) ,這與悲波那韌數列的遞歸公式相似。當n為1時，只有1種跳法;當n為2時，有2種跳法(一次跳2級或分兩次每次跳1級)。遞歸實現代碼如下:

int FrogJump(int n)
{

    if(n == 1)
       return 1;
    if(n == 2)
       return 2;
    
    return FrogJump(n-1)+FrogJump(n-2);
}

同樣，為了提高效率，也可以將其轉換為迭代實現。

漢諾塔問題是一個古老的益智游戲，有三根柱子 A、B、C，A 柱上有若干個盤子，盤子大小不等，大的在下，小的在上。要求將 A柱上的盤子借助 B柱全部移到C柱上，每次只能移動日在移動討程中大母子不能前在小盤子上面。這個問題可以用遞歸完美解決。假設要將n個盤子從 A 柱借助 B 柱移到 C 柱遞歸思路如下:

總結 

到此這篇關于C語言函數遞歸的文章就介紹到這了,更多相關C語言函數遞歸內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論