前言：

在 C 語(yǔ)言函數(shù)學(xué)習(xí)之旅中，遞歸是一個(gè)繞不開的重要話題。它不僅是一種編程技巧，更是一種解決問題的獨(dú)特思路。本文將從遞歸的基本概念出發(fā)，深入剖析其限制條件，通過實(shí)例演示遞歸的應(yīng)用，并對(duì)比遞歸與迭代的優(yōu)劣，幫助你徹底掌握 C 語(yǔ)言中的函數(shù)遞歸。

一、遞歸是什么？

遞歸，從字面意義上看，包含 “遞” 和 “歸” 兩層含義。在 C 語(yǔ)言中，遞歸本質(zhì)上是函數(shù)自己調(diào)用自己的一種行為，它將一個(gè)大型復(fù)雜的問題層層拆解為與原問題相似但規(guī)模更小的子問題，直到子問題無(wú)法再拆分，最終通過子問題的解逐步推導(dǎo)出原問題的解。

1.1遞歸的基本形式

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

這段代碼中，main函數(shù)在自身內(nèi)部調(diào)用了自己，符合于函數(shù)遞歸的定義。但需要注意的是，這段代碼由于缺乏終止條件，最終會(huì)陷入死遞歸，導(dǎo)致棧溢出（Stack overflow）的錯(cuò)誤，出現(xiàn)類似于以下的提示：

“0x7BF20907 (ucrtbased.d11)(test.exe 中) 處有未經(jīng)
處理的異常：0xC0000OP:Stack overflow (參數(shù)
：0x00000000, 0x00602000)”

1.2 遞歸的核心思想

遞歸的核心思想是 “大事化小”。比如要解決一個(gè)復(fù)雜問題A，我們可以將其拆解為問題 B，問題 B 的解決方法與問題 A`相似但規(guī)模更?。唤又賹栴} B 拆解為問題 C，以此類推，直到拆解出的子問題可以直接解決（即遞歸的終止條件），然后再?gòu)淖訂栴}的解逐步回歸，得到原問題的解。

二、遞歸的限制條件

并非任意函數(shù)自己調(diào)用自己都能構(gòu)成有效的遞歸，有效的遞歸必須滿足兩個(gè)必要條件，這兩個(gè)條件缺一不可，否則就會(huì)出現(xiàn)死遞歸。

2.1 存在終止條件

遞歸必須存在一個(gè)明確的限制條件，當(dāng)滿足這個(gè)條件時(shí)，遞歸將不再繼續(xù)。這個(gè)終止條件是遞歸能夠正常結(jié)束的關(guān)鍵，它就像遞歸的 “剎車”，防止遞歸無(wú)限進(jìn)行下去。

2.2 逐步接近終止條件

在每次遞歸調(diào)用過程中，函數(shù)的參數(shù)或狀態(tài)必須逐漸接近遞歸的終止條件。也就是說(shuō)，每一次遞歸調(diào)用都應(yīng)該讓問題的規(guī)模更小，使得問題一步步向可直接解決的方向靠近。

三、遞歸實(shí)例解析

論結(jié)合實(shí)踐才能更好地理解遞歸，下面我們通過兩個(gè)經(jīng)典實(shí)例，詳細(xì)的講解一下遞歸的應(yīng)用過程。

3.1 實(shí)例 1：求 n 的階乘

一個(gè)正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積，并且規(guī)定 0 的階乘為 1。自然數(shù) n 的階乘記作 n!，其數(shù)學(xué)公式為：
當(dāng) n = 0 時(shí)，n! = 1；
當(dāng) n > 0 時(shí)，n! = n × (n - 1) ! 。

問題分析

從公式可以看出，求 n 的階乘可以拆解為求 n 乘以 (n - 1) 的階乘，而求 (n - 1) 的階乘又可以拆解為 (n - 1) 乘以 (n - 2) 的階乘，以此類推，直到拆解到求 0 的階乘（結(jié)果為 1），此時(shí)遞歸終止，再逐步回歸計(jì)算出原問題的解。

舉例
5 ! = 5* 4* 3* 2 1
4 ! = 4 3* 2* 1
所以 ：5 ! = 4 !

代碼實(shí)現(xiàn)

#include <stdio.h>

// 定義遞歸函數(shù)計(jì)算n的階乘
int Fact(int n)
{
    // 遞歸終止條件：n == 0時(shí)，返回1
    if (n == 0)
        return 1;
    // 遞歸調(diào)用：n > 0時(shí)，返回n乘以(n - 1)的階乘
    else
        return n * Fact(n - 1);
}

int main()
{
    int n = 0;
    // 輸入要計(jì)算階乘的數(shù)字
    scanf("%d", &n);
    // 調(diào)用遞歸函數(shù)計(jì)算階乘
    int ret = Fact(n);
    // 輸出結(jié)果
    printf("%d\n", ret);
    return 0;
}

運(yùn)行結(jié)果與推演

當(dāng)輸入 n = 5 時(shí)，程序運(yùn)行結(jié)果為 120，符合 5! = 5×4×3×2×1 = 120 的預(yù)期。我們來(lái)推演一下遞歸過程：

• Fact(5) = 5 × Fact(4)
• Fact(4) = 4 × Fact(3)
• Fact(3) = 3 × Fact(2)
• Fact(2) = 2 × Fact(1)
• Fact(1) = 1 × Fact(0)
• Fact (0) = 1（遞歸終止）

然后開始回歸計(jì)算：

• Fact(1) = 1 × 1 = 1
• Fact(2) = 2 × 1 = 2
• Fact(3) = 3 × 2 = 6
• Fact(4) = 4 × 6 = 24
• Fact(5) = 5 × 24 = 120

3.2 實(shí)例 2：順序打印一個(gè)整數(shù)的每一位

問題分析

輸入一個(gè)整數(shù) m，要求按照順序打印出該整數(shù)的每一位。例如，輸入 1234，輸出 1 2 3 4；輸入 520，輸出 5 2 0。

要解決這個(gè)問題，首先需要思考如何獲取整數(shù)的每一位。對(duì)于一個(gè)多位數(shù)，通過取余運(yùn)算（%10）可以得到其最低位，通過整除運(yùn)算（/10）可以去掉最低位。但直接使用這種方法得到的數(shù)字順序是倒著的，比如 1234，先得到 4，再得到 3，接著得到 2，最后得到 1。

這時(shí)候就可以利用遞歸的思想：要打印 1234 的每一位，可以先打印 123 的每一位，再打印 1234 的最低位 4；要打印 123 的每一位，可以先打印 12 的每一位，再打印 123 的最低位 3；以此類推，直到要打印的數(shù)字是一位數(shù)時(shí)，直接打印該數(shù)字，遞歸終止。

代碼實(shí)現(xiàn)

#include <stdio.h>

// 定義遞歸函數(shù)順序打印整數(shù)的每一位
void Print(int n)
{
    // 遞歸終止條件：當(dāng)n是一位數(shù)時(shí)，直接打印
    if (n > 9)
    {
        // 遞歸調(diào)用：先打印n去掉最低位后的數(shù)字的每一位
        Print(n / 10);
    }
    // 打印n的最低位
    printf("%d ", n % 10);
}

int main()
{
    int m = 0;
    // 輸入要打印每一位的整數(shù)
    scanf("%d", &m);
    // 調(diào)用遞歸函數(shù)打印每一位
    Print(m);
    return 0;
}

運(yùn)行結(jié)果與推演

當(dāng)輸入 m = 1234 時(shí)，程序運(yùn)行結(jié)果為 1 2 3 4，符合預(yù)期。
同樣我們可以來(lái)推演遞歸過程：

• Print (1234)：1234 > 9，調(diào)用 Print (123)，之后打印 1234%10 = 4
• Print (123)：123 > 9，調(diào)用 Print (12)，之后打印 123%10 = 3
• Print (12)：12 > 9，調(diào)用 Print (1)，之后打印 12%10 = 2
• Print (1)：1 <= 9，直接打印 1%10 = 1（遞歸終止）

最終打印順序?yàn)?1 2 3 4。

四、遞歸與迭代

遞歸雖然是一種簡(jiǎn)潔的編程技巧，但并非在所有場(chǎng)景下都是最優(yōu)選擇，很多時(shí)候迭代（通常指循環(huán)）是更好的替代方案。下面我們來(lái)對(duì)比遞歸與迭代的特點(diǎn)，并通過實(shí)例分析何時(shí)該使用遞歸，何時(shí)該使用迭代。

4.1 遞歸的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

• 代碼簡(jiǎn)潔易懂：遞歸能夠直接反映問題的數(shù)學(xué)模型，使得代碼邏輯更加清晰，便于理解和編寫。比如求 n 的階乘，遞歸代碼直接對(duì)應(yīng)階乘的數(shù)學(xué)公式，非常直觀。
• 解決復(fù)雜問題更有優(yōu)勢(shì)：對(duì)于一些復(fù)雜問題，如漢諾塔問題、樹的遍歷等，使用遞歸可以將問題分解為更小的子問題，降低問題的復(fù)雜度，而使用迭代實(shí)現(xiàn)則可能非常繁瑣。

缺點(diǎn)

• 棧溢出風(fēng)險(xiǎn)：在 C 語(yǔ)言中，每一次函數(shù)調(diào)用都會(huì)在棧區(qū)申請(qǐng)一塊棧幀空間來(lái)保存局部變量等信息。如果遞歸層次過深，會(huì)占用大量的棧空間，導(dǎo)致棧溢出錯(cuò)誤。
• 效率較低：遞歸過程中存在函數(shù)調(diào)用的開銷，而且可能會(huì)出現(xiàn)大量重復(fù)計(jì)算的情況，導(dǎo)致程序運(yùn)行效率降低。

4.2 迭代的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

• 效率高：迭代通過循環(huán)實(shí)現(xiàn)，避免了頻繁的函數(shù)調(diào)用開銷，也不會(huì)出現(xiàn)重復(fù)計(jì)算的問題（除非代碼邏輯設(shè)計(jì)不當(dāng)），運(yùn)行效率更高。
• 內(nèi)存占用少：迭代不需要額外的棧幀空間，內(nèi)存占用相對(duì)較少，不存在棧溢出的風(fēng)險(xiǎn)。

缺點(diǎn)

代碼邏輯可能復(fù)雜：對(duì)于一些復(fù)雜問題，使用迭代實(shí)現(xiàn)時(shí)，代碼邏輯可能會(huì)比較繁瑣，不易理解和維護(hù)。

4.3 實(shí)例對(duì)比：求第 n 個(gè)斐波那契數(shù)

斐波那契數(shù)的數(shù)學(xué)定義為：
當(dāng) n <= 2 時(shí)，F(xiàn)ib (n) = 1；
當(dāng) n > 2 時(shí)，F(xiàn)ib (n) = Fib (n - 1) + Fib (n - 2)。
根據(jù)這個(gè)定義，我們能很容易寫出遞歸代碼：

#include <stdio.h>

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

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    return 0;
}

但當(dāng) n = 50 時(shí)，程序需要很長(zhǎng)時(shí)間才能算出結(jié)果，效率極低。這是因?yàn)檫f歸過程中存在大量重復(fù)計(jì)算，我們通過一個(gè)計(jì)數(shù)器來(lái)統(tǒng)計(jì)第 3 個(gè)斐波那契數(shù)的計(jì)算次數(shù)：

#include <stdio.h>
int count = 0;

int Fib(int n)
{
    if (n == 3)
        count++;// 統(tǒng)計(jì)第3個(gè)斐波那契數(shù)被計(jì)算的次數(shù)
    if (n <= 2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    printf("count = %d\n", count);
    return 0;
}

運(yùn)行結(jié)果

40
102334155

count = 39088169

當(dāng)輸入 n = 40 時(shí)，輸出結(jié)果中 count = 39088169，這意味著第 3 個(gè)斐波那契數(shù)被重復(fù)計(jì)算了近 4000 萬(wàn)次，大量的重復(fù)計(jì)算嚴(yán)重影響了程序效率。

4.4 迭代實(shí)現(xiàn)的優(yōu)勢(shì)

針對(duì)斐波那契數(shù)的計(jì)算，我們可以使用迭代的方式來(lái)避免重復(fù)計(jì)算。由于斐波那契數(shù)的前兩個(gè)數(shù)都是 1，從第三個(gè)數(shù)開始，每個(gè)數(shù)都是前兩個(gè)數(shù)的和.
因此我們可以通過循環(huán)從前往后依次計(jì)算：

#include <stdio.h>

int Fib(int n)
{
    // 初始化前兩個(gè)斐波那契數(shù)
    int a = 1;
    int b = 1;
    // 存儲(chǔ)當(dāng)前斐波那契數(shù)，初始值為1（當(dāng)n <= 2時(shí)）
    int c = 1;
    // 循環(huán)計(jì)算從第3個(gè)到第n個(gè)斐波那契數(shù)
    while (n > 2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    return 0;
}

使用迭代實(shí)現(xiàn)后，即使 n = 100，程序也能快速計(jì)算出結(jié)果，效率遠(yuǎn)高于遞歸實(shí)現(xiàn)。

4.5 遞歸與迭代的選擇建議

• 當(dāng)問題的遞歸實(shí)現(xiàn)簡(jiǎn)潔易懂，且遞歸層次不深，不存在大量重復(fù)計(jì)算時(shí)，可以選擇遞歸。例如求 n 的階乘、順序打印整數(shù)的每一位等。
• 當(dāng)遞歸層次較深，或者存在大量重復(fù)計(jì)算時(shí)，應(yīng)優(yōu)先選擇迭代。例如求第 n 個(gè)斐波那契數(shù)。
• 對(duì)于一些復(fù)雜問題，如漢諾塔問題、樹的遍歷等，遞歸實(shí)現(xiàn)具有明顯優(yōu)勢(shì)，此時(shí)可以選擇遞歸。

到此這篇關(guān)于C語(yǔ)言中函數(shù)遞歸的實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)C語(yǔ)言 函數(shù)遞歸內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論