C語言 函數(shù)的遞歸調(diào)用

C語言允許函數(shù)遞歸調(diào)用。遞歸就是一個函數(shù)的函數(shù)體內(nèi)直接或間接地出現(xiàn)了調(diào)用自身的語句。這樣的函數(shù)稱為遞歸函數(shù)。

遞歸調(diào)用可以使遞歸函數(shù)使用不同參數(shù)的值重復(fù)執(zhí)行。某些情況下，遞歸過程類似于循環(huán)，所以有時可以做循環(huán)的替代方法。

遞歸調(diào)用中，遞歸函數(shù)既是主調(diào)函數(shù)又是被調(diào)函數(shù)。遞歸執(zhí)行時，每調(diào)用一次就進(jìn)入新的一層。 

例如：

#include <stdio.h>

f(int x)

{

  if(x/2>0)

    f(x/2);

  printf("%d ", x);

}

main()

{

    f(10);

    printf("\n");

}

可以看到，f()函數(shù)體內(nèi)出現(xiàn)了調(diào)用自身的語句f(x/2);,所以f()函數(shù)是一個遞歸函數(shù)。

分析這個程序的執(zhí)行過程：

①當(dāng)main()函數(shù)調(diào)用f()函數(shù)時，將實(shí)參的值10,傳遞給形參x。

②第一次f()函數(shù)的執(zhí)行：執(zhí)行f()函數(shù)，形參x為10，因?yàn)閤/2的值為5，大于0，所以再次調(diào)用f()函數(shù)，此次將表達(dá)式x/2的值5作為實(shí)參傳遞給下一次調(diào)用。

③第一次遞歸調(diào)用：形參x得到實(shí)參的值5，判斷x/2的值，仍然大于0，所以繼續(xù)遞歸調(diào)用f()函數(shù)，此次調(diào)用函數(shù)，傳遞過去的實(shí)參的值將是x/2，即5/2，實(shí)參為2。

④第二次遞歸調(diào)用：形參x的得到實(shí)參傳遞過來的2，判斷x/2的值，結(jié)果為1，仍然大于0，繼續(xù)遞歸調(diào)用f()函數(shù)，傳遞過去的實(shí)參的值將是x/2，即2/2，實(shí)參為1。

⑤第三次遞歸調(diào)用：形參x得到實(shí)參傳遞過來的1,判斷x/2的值，結(jié)果為0，不再大于0，if語句的條件表達(dá)式不成立，執(zhí)行if后面的語句，輸出x的值1。函數(shù)執(zhí)行結(jié)束，返回調(diào)用處，調(diào)用處為第二次遞歸調(diào)用處。

⑥當(dāng)返回第二次遞歸調(diào)用處時，if語句已經(jīng)執(zhí)行完畢，繼續(xù)執(zhí)行if后面的語句，輸出x的值，此時的x是2，輸出。函數(shù)執(zhí)行結(jié)束返回調(diào)用處。調(diào)用處為第一次遞歸調(diào)用。

⑦回到第一次遞歸調(diào)用，此處的if語句也執(zhí)行完畢，執(zhí)行if后面的語句，輸出x的值，此時x的值為5，輸出。函數(shù)執(zhí)行結(jié)束返回調(diào)用處。

⑧此次返回第一次執(zhí)行f()函數(shù)處，同樣執(zhí)行if后面的語句，輸出x的值10,并返回調(diào)用處main()函數(shù)。具體執(zhí)行過程如圖所示：

C語言中的遞歸分為兩種，一種是直接遞歸，另一種是間接遞歸。

直接遞歸就是函數(shù)直接調(diào)用自身。上例就是一個直接遞歸的過程。

間接遞歸是函數(shù)f1()調(diào)用f2(),而f()函數(shù)中又調(diào)用了fl(),過程如圖所示。遞歸函數(shù)設(shè)計(jì)過程中，注意不要出現(xiàn)無休止地調(diào)用其自身的情況，例如：

#include <stdio.h> 

f(int x)

{

    f(x+1);

}

調(diào)用過程如圖所示。

因?yàn)檫f歸在內(nèi)存中使用堆棧的方式，如果無終止遞歸，最終會導(dǎo)致棧溢出。為了防止遞歸調(diào)用無終止地進(jìn)行，函數(shù)內(nèi)必須有終止遞歸調(diào)用的手段。常用的辦法是用一個條件進(jìn)行判斷，滿足某種條件后就不再作遞歸調(diào)用，然后逐層返回。