C語言中文網 目錄

函數的遞歸調用,C語言函數遞歸調用完全攻略

前面講了函數調用,那么函數到底是如何調用的?函數調用是通過棧實現的。在調用函數時,系統會將被調函數所需的程序空間安排在一個棧中。每當調用一個函數時,就在棧頂為它分配一個存儲區。每當從一個函數退出時就釋放它的存儲區。

也就是說,當前正在運行的函數的存儲區是在棧頂的。因為棧是先進后出的(或者說是后進先出的),所以當有多個函數嵌套調用時,會按照先調用后返回的原則(或者說是后調用先返回的原則)進行返回。

遞歸也是一種函數調用,只不過是函數自己調用自己,是一種特殊的函數調用,調用自己同調用別人是一模一樣的。

因為遞歸也是函數調用,所以遞歸也是用棧實現的。下面來寫一個程序,看看函數是如何自己調用自己的:
# include <stdio.h>
void Func(int n);  //函數聲明
int main(void)
{
    int n;
    printf("想輸出幾個我愛你:");
    scanf("%d", &n);
    Func(n);
    return 0;
}
void Func(int n)
{
    if (n > 0)
    {
        printf("i love you\n");
        Func(n-1);
    }
    else
    {
        return ;
    }
}
輸出結果是:
想輸出幾個我愛你:5
i love you
i love you
i love you
i love you
i love you

這就是“自己調用自己”。從這個程序可以看出,自己調用自己必須要滿足一個條件,就是必須要知道什么時候結束調用。不然函數就會一直不停地調用,造成“死遞歸”。

死遞歸是指遞歸的時候沒有出口,不知道什么時候停下來,不停地自己調用自己,直到棧滿沒有地方放了為止。這時計算機也死機了(除了這個條件之外還有另外一個條件,后續再講)。

使用遞歸必須要滿足的兩個條件

并不是所有的問題都能用遞歸解決。要使用遞歸就必須要具備兩個條件。

遞歸的思想是:為了解決當前問題 F(n),就需要解決問題 F(n–1),而 F(n–1) 的解決依賴于 F(n–2) 的解決……就這樣逐層分解,分解成很多相似的小事件,當最小的事件解決完之后,就能解決高層次的事件。這種“逐層分解,逐層合并”的方式就構成了遞歸的思想。

使用遞歸最主要的是要找到遞歸的出口和遞歸的方式。所以遞歸通常分為兩部分:遞歸的方式遞歸的終止條件(最小事件的解)。這兩個部分是遞歸的關鍵!

遞歸的方式,就是指遞歸公式,即對問題的分解,同時也是向遞歸終止條件收斂的規則。而遞歸的終止條件通常就是得出的最小事件的解。遞歸終止條件的作用就是不讓遞歸無限地進行下去,最后必須要能“停”下來。

綜上所述,使用遞歸必須要滿足的兩個條件就是:
  • 要有遞歸公式。
  • 要有終止條件。

如何學習遞歸

大多數人在學習遞歸的時候一般都會有一個問題,“怎么知道什么時候可以用遞歸,什么時候不可以用遞歸?”

很多人在學習遞歸的時候都會有這個困惑。雖然遞歸的思想也掌握了,也知道使用遞歸必須要具備兩個條件,但就是不會用,無法用遞歸解決新的問題。

那么到底怎么知道一個問題是否可以用遞歸解決呢?其實,一個問題是否可以用遞歸來解決,這是一個數學問題,這個問題不需要我們考慮,換句話說,不要去考慮一個問題能不能用遞歸解決,我們所要做的就是掌握那些已知的、非常經典的遞歸算法。

遞歸和循環的關系

遞歸和循環存在很多關系。理論上講,所有的循環都可以轉化成遞歸,但是利用遞歸可以解決的問題,使用循環不一定能解決。比如編寫樹和圖的程序就必須用遞歸,雖然循環也可以實現,但那樣做絕對是程序員的噩夢。

循環又稱迭代。遞歸算法與迭代算法設計思路的主要區別在于:函數或算法是否具備收斂性!當且僅當一個算法存在預期的收斂效果時,采用遞歸算法才是可行的。否則就不能使用遞歸算法。所謂收斂性就是指要有終止條件,不能無休止地遞歸下去。

遞歸的優缺點

遞歸的優點是簡化程序設計,結構簡潔清晰,容易編程,可讀性強,容易理解。在很多情況下使用遞歸是必要的,它往往能把復雜問題分解為更簡單的步驟,而且能夠反映問題的本質。我們一開始可能發現遞歸理解起來也不容易,這是因為我們的“見識”太少了!等將來學習樹和圖的時候你才能真正領會到遞歸是多么的“好理解”!

又比如漢諾塔,用遞歸的話基本上可以理解,但是如果不用遞歸而用循環的話,程序根本不知道從何處著手!

但是遞歸的缺點也很明顯:速度慢,運行效率低,對存儲空間的占用比循環多。嚴格講,循環幾乎不浪費任何存儲空間,而遞歸浪費的空間實在是太大了,而且速度慢。

因為遞歸是用棧機制實現的,每深入一層都要占用一塊棧數據區域。對嵌套層數深的一些算法,遞歸就會顯得力不從心,最后都會以內存崩潰而告終。而且遞歸也帶來了大量的函數調用,這也有許多額外的時間開銷。函數調用要發送實參,要為被調函數分配存儲空間,還要保存返回的值,又要釋放空間并將值返回給主調函數,這些都太浪費空間和時間。

雖然遞歸有那么多缺點,但是沒有辦法,有些問題太復雜,不用遞歸就解決不了!

與遞歸相比,循環的缺點是不容易理解,遇復雜問題時編寫困難。但它的優點是速度快、效率高、不浪費空間。循環的運行時間只因循環次數增加而增加,沒有其他額外開銷,空間上同樣。

對于初學者而言,我們所遇到的遞歸算法一般都比較簡單,能用遞歸解決的一般都能用循環解決,所以初學編程的時候大家不要總想著使用遞歸。

下面給大家編寫幾個程序,列舉幾個例子,主要通過例子讓大家對遞歸有一個了解。

1) 用遞歸求 n 的階乘。

n!也可以寫成 n×(n–1)!,這就是遞歸公式。
# include <stdio.h>
long Factorial(int n);  //函數聲明
int main(void)
{
    int n;
    printf("請輸入n的值:");
    scanf("%d", &n);
    printf("%d! = %ld\n", n, Factorial(n));
    return 0;
}
long Factorial(int n)  //階乘的英文為factorial
{
    if (n < 0)
    {
        return -1;
    }
    else if (0==n || 1==n)  /*關系運算符的優先級大于邏輯運算符的優點級, 所以不用加括號*/
    {
        return 1;
    }
    else
    {
        return n * Factorial(n-1);
    }
}
輸出結果是:
請輸入n的值:10
10! = 3628800

n 的值不要太大,不然容易溢出,long 類型也放不下。

2) 用遞歸實現 1+2+3+…+100 的和

求和的遞歸公式跟求階乘的遞歸公式很相似:Sum(n)=n+Sum(n–1)。
# include <stdio.h>
int Sum(int n);  //函數聲明
int main(void)
{
    int n;
    printf("請輸入n的值:");
    scanf("%d", &n);
    printf("sum = %d\n", Sum(n));
    return 0;
}
int Sum(int n)
{
    if (n <= 0)
    {
        return -1;
    }
    else if (1 == n)
    {
        return 1;
    }
    else
    {
        return n+Sum(n-1);
    }
}
輸出結果是:
請輸入n的值:100
sum = 5050

3) 用遞歸求斐波那契數列。

所謂斐波那契數列是指數列中每一個數值都是其前兩個數值之和,即:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368……

# include <stdio.h>
long Fibonacci(int n);  //函數聲明
int main(void)
{
    int n;
    printf("請輸入n的值:");
    scanf("%d", &n);
    printf("第n項的值為:%ld\n", Fibonacci(n));
    return 0;
}
long Fibonacci(int n)
{
    if (n < 0)
    {
        return -1;
    }
    else if (0 == n)
    {
        return 0;
    }
    else if (1 == n)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}
輸出結果是:
請輸入n的值:21
第n項的值為:10946

通過上面這幾個程序我們發現遞歸都有一個共同的特點,就是遞歸公式全部都是寫在 return 語句后面的,而且最小事件的解都會返回一個具體的值。如果最小事件的解不返回一個具體值的話,那么遞歸就無法停下來。

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo