前言

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

一、遞歸的概念與思想

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

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

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

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

二、遞歸的限制條件 

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

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

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

三、遞歸的實際應用舉例

（一）求 n 的階乘

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

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

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

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

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

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

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

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

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

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

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

四、遞歸與迭代的比較 

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

相比之下，迭代（通常就是循環(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)實現(xiàn)了與遞歸相同的功能，而且效率更高。因為它不需要頻繁地開辟和釋放棧幀空間

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

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

五、遞歸的拓展應用

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

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;
}

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

青蛙跳臺階問題

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

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

總結(jié) 

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

最新評論