前言

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

一、遞歸的概念與思想

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

我們來(lái)看一個(gè)簡(jiǎn)單的示例代碼：

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

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

二、遞歸的限制條件 

為了避免遞歸陷入死循環(huán)，我們?cè)谑褂眠f歸時(shí)必須遵循兩個(gè)必要條件：

存在限制條件：當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。這個(gè)限制條件就像是給遞歸設(shè)定了一個(gè)終點(diǎn)，告訴它什么時(shí)候該停下來(lái)。

每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件：這確保了遞歸能夠逐步收斂，最終達(dá)到限制條件，結(jié)束遞歸過(guò)程。

三、遞歸的實(shí)際應(yīng)用舉例

（一）求 n 的階乘

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

根據(jù)這個(gè)公式，我們可以編寫如下函數(shù)來(lái)計(jì)算 n 的階乘：

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

在這個(gè)函數(shù)中，當(dāng) n 等于 0 時(shí)，遞歸結(jié)束，返回 1；否則，繼續(xù)調(diào)用 Fact 函數(shù)，將問(wèn)題規(guī)模逐漸縮小，直到 n 為 0。

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

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

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

（二）順序打印一個(gè)整數(shù)的每一位

輸入一個(gè)整數(shù) m，按照順序打印整數(shù)的每一位。例如，輸入 1234，輸出 1 2 3 4 。我們可以通過(guò) %10 和 / 10 操作來(lái)拆分整數(shù)的每一位。假設(shè)想寫一個(gè)函數(shù) Print 來(lái)打印 n 的每一位，其實(shí)現(xiàn)思路如下：

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

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

四、遞歸與迭代的比較 

遞歸雖然是一種強(qiáng)大的編程技巧，但它也有自己的局限性。在遞歸函數(shù)調(diào)用的過(guò)程中，每一次函數(shù)調(diào)用都需要在內(nèi)存的棧區(qū)申請(qǐng)一塊內(nèi)存空間來(lái)保存函數(shù)調(diào)用期間的各種局部變量的值，這塊空間被稱為運(yùn)行時(shí)堆?；蚝瘮?shù)棧幀。如果遞歸層次太深，就會(huì)浪費(fèi)太多的棧幀空間，甚至可能引起棧溢出的問(wèn)題。

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

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

這段代碼通過(guò)循環(huán)實(shí)現(xiàn)了與遞歸相同的功能，而且效率更高。因?yàn)樗恍枰l繁地開辟和釋放棧幀空間

再比如計(jì)算第 n 個(gè)斐波那契數(shù)，斐波那契數(shù)列的遞歸公式為：

按照這個(gè)公式編寫的遞歸代碼在計(jì)算較大的 n 時(shí)效率極低，因?yàn)闀?huì)產(chǎn)生大量的重復(fù)計(jì)算。例如，在計(jì)算第 40 個(gè)斐波那契數(shù)時(shí)，第 3 個(gè)斐波那契數(shù)就被重復(fù)計(jì)算了 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;
}

五、遞歸的拓展應(yīng)用

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

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

然而，當(dāng)n較大時(shí)，如n=50，使用這種遞歸方式計(jì)算會(huì)花費(fèi)極長(zhǎng)的時(shí)間，因?yàn)檫f歸過(guò)程中存在大量重復(fù)計(jì)算。為了優(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;
}

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

青蛙跳臺(tái)階問(wèn)題

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

int FrogJump(int n)
{

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

同樣，為了提高效率，也可以將其轉(zhuǎn)換為迭代實(shí)現(xiàn)。

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

總結(jié) 

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

最新評(píng)論