- 相關(guān)推薦
C語(yǔ)言函數遞歸教程
引導語(yǔ)：遞歸做為一種算法在程序設計語(yǔ)言中廣泛應用。以下是百分網(wǎng)小編分享給大家的C語(yǔ)言函數遞歸教程，歡迎閱讀!
一、棧
在說(shuō)函數遞歸的時(shí)候，順便說(shuō)一下棧的概念。
棧是一個(gè)后進(jìn)先出的壓入(push)和彈出(pop)式數據結構。在程序運行時(shí)，系統每次向棧中壓入一個(gè)對象，然后棧指針向下移動(dòng)一個(gè)位置。當系統從棧中彈出一個(gè)對象時(shí)，最近進(jìn)棧的對象將被彈出。然后棧指針向上移動(dòng)一個(gè)位置。程序員經(jīng)常利用棧這種數據結構來(lái)處理那些最適合用后進(jìn)先出邏輯來(lái)描述的編程問(wèn)題。這里討論的程序中的棧在每個(gè)程序中都是存在的，它不需要程序員編寫(xiě)代碼去維護，而是由運行是系統自動(dòng)處理。所謂的系統自動(dòng)維護，實(shí)際上就是編譯器所產(chǎn)生的程序代碼。盡管在源代碼中看不到它們，但程序員應該對此有所了解。
再來(lái)看看程序中的棧是如何工作的。當一個(gè)函數(調用者)調用另一個(gè)函數(被調用者)時(shí)，運行時(shí)系統將把調用者的所有實(shí)參和返回地址壓入到棧中，棧指針將移到合適的位置來(lái)容納這些數據。最后進(jìn)棧的是調用者的返回地址。當被調用者開(kāi)始執行時(shí)，系統把被調用者的自變量壓入到棧中，并把棧指針再向下移，以保證有足夠的空間存儲被調用者聲明的所有自變量。當調用者把實(shí)參壓入棧后，被調用者就在棧中以自變量的形式建立了形參。被調用者內部的其他自變量也是存放在棧中的。由于這些進(jìn)棧操作，棧指針已經(jīng)移動(dòng)所有這些局部變量之下。但是被調用者記錄了它剛開(kāi)始執行時(shí)的初始棧指針，以他為參考，用正或負的偏移值來(lái)訪(fǎng)問(wèn)棧中的變量。當被調用者準備返回時(shí)，系統彈出棧中所有的自變量，這時(shí)棧指針移動(dòng)了被調用者剛開(kāi)始執行時(shí)的位置。接著(zhù)被調用者返回，系統從棧中彈出返回地址，調用者就可以繼續執行了。當調用者繼續執行時(shí)，系統還將從棧中彈出調用者的實(shí)參，于是棧指針回到了調用發(fā)生前的位置。
可能剛開(kāi)始學(xué)的人看不太懂上面的講解，棧涉及到指針問(wèn)題，具體可以看看一些數據結構的書(shū)。要想學(xué)好編程語(yǔ)言，數據結構是一定要學(xué)的。
二、遞歸
遞歸，是函數實(shí)現的一個(gè)很重要的環(huán)節，很多程序中都或多或少的使用了遞歸函數。遞歸的意思就是函數自己調用自己本身，或者在自己函數調用的下級函數中調用自己。
遞歸之所以能實(shí)現，是因為函數的每個(gè)執行過(guò)程都在棧中有自己的形參和局部變量的拷貝，這些拷貝和函數的其他執行過(guò)程毫不相干。這種機制是當代大多數程序設計語(yǔ)言實(shí)現子程序結構的基礎，是使得遞歸成為可能。假定某個(gè)調用函數調用了一個(gè)被調用函數，再假定被調用函數又反過(guò)來(lái)調用了調用函數。這第二個(gè)調用就被稱(chēng)為調用函數的遞歸，因為它發(fā)生在調用函數的當前執行過(guò)程運行完畢之前。而且，因為這個(gè)原先的調用函數、現在的被調用函數在棧中較低的位置有它獨立的一組參數和自變量，原先的參數和變量將不受影響，所以遞歸能正常工作。程序遍歷執行這些函數的過(guò)程就被稱(chēng)為遞歸下降。
程序員需保證遞歸函數不會(huì )隨意改變靜態(tài)變量和全局變量的值，以避免在遞歸下降過(guò)程中的上層函數出錯。程序員還必須確保有一個(gè)終止條件來(lái)結束遞歸下降過(guò)程，并且返回到頂層。
例如這樣的程序就是遞歸：
void a(int);
main()
{
int num=5;
a(num);
}
void a(int num)
{
if(num==0) return;
printf(%d,num);
a(--num);
}
在函數a()里面又調用了自己，也就是自己調用本身，這樣就是遞歸。那么有些人可能要想，這不是死循環(huán)嗎?所以在遞歸函數中，一定要有return語(yǔ)句，沒(méi)有return語(yǔ)句的遞歸函數是死循環(huán)。
我們分析上面的例子，先調用a(5)，然后輸出5，再在函數中調用本身a(4)，接著(zhù)回到函數起點(diǎn)，輸出4，……，一直到調用a(0)，這時(shí)發(fā)現已經(jīng)滿(mǎn)足if條件，不在調用而是返回了，所以這個(gè)遞歸一共進(jìn)行了5次。如果沒(méi)有這個(gè)return，肯定是死循環(huán)的。
雖然遞歸不難理解，但是很多在在使用遞歸函數的時(shí)候，問(wèn)題多多。這里面一般有兩個(gè)原因：一是如何往下遞歸，也就是不知道怎么取一個(gè)變量遞歸下去;二是不知道怎么終止遞歸，經(jīng)常弄個(gè)死循環(huán)出來(lái)。
下面看幾個(gè)例子：
1.求1+2+……+100的和
先分析一下。第一遞歸變量的問(wèn)題，從題目上看應該取1,2,……,100這些變量的值作為遞歸的條件;第二就是如何終止的問(wèn)題，從題目上看應該是當數為100的時(shí)候就不能往下加了。那么我們試著(zhù)寫(xiě)一下程序。
int add(int);
main()
{
int num=1,sn;
sn=add(num);
printf(%d\n,sn);
getch();
}
int add(int num)
{
static int sn;
sn+=num;
if(num==100) return sn;
add(++num);
}
分析一下程序：前調用add(1)，然后在子函數中把這個(gè)1加到sn上面。接著(zhù)調用add(2)，再把sn加2上來(lái)。這樣一直到100，到了100的時(shí)候，先加上來(lái)，然后發(fā)現滿(mǎn)足了if條件，這時(shí)返回sn的值，也就是1+2+……+100的值了。
這里有一個(gè)問(wèn)題一定要注意，就是static int sn;
有些人就不明白，為什么要使用static類(lèi)型修飾符，為什么不使用int sn=0;?如果使用int sn=0;這樣的語(yǔ)句，在每次調用函數add()的時(shí)候，sn的值都是賦值為0,也就是第一步雖然加了1上來(lái)，可是第二次調用的時(shí)候，sn又回到了0。我們前面說(shuō)了，static能保證本次初始化的值是上次執行后的值，這樣也就保證了前面想加的結果不會(huì )丟失。如果你修改為int sn=0，最后結果一定是最后的100這個(gè)值而不是5050。
2.求數列s(n)=s(n-1)+s(n-2)的第n項。其中s(1)=s(2)=1。
可以看出，終止條件一定是s(1)=s(2)=1。遞歸下降的參數一定是n。
int a(int);
main()
{
int n,s;
scanf(%d,&n);
s=a(n);
printf(%d\n,s);
getch();
}
int a(int n)
{
if(n<3) return 1;
return a(n-1)+a(n-2);
}
這個(gè)題目主要說(shuō)明的是，在函數中，不一定只有一個(gè)return語(yǔ)句，可以有很多，但是每次對歸的時(shí)候只有一個(gè)起作用。題目不難理解，這兒不分析了。
說(shuō)了這些遞歸，其實(shí)它和函數的調用沒(méi)有大的區別，主要就是一個(gè)終止條件要選好。遞歸函數很多時(shí)候都能用循環(huán)來(lái)處理。
main()
{
int n=20,array[20];
int i;
for(i=0;i {
if(i<2) array[i]=1;
else array[i]=array[i-1]+array[i-2];
}
printf(%d\n,array[19]);
getch();
}
上面的程序就是實(shí)現一模一樣的功能的。但是它有一個(gè)缺陷，就是n的值不是通過(guò)鍵盤(pán)輸入來(lái)得到。如果想通過(guò)鍵盤(pán)來(lái)得到n，可以這樣：
main()
{
int n,i;
int s1=1,s2=1,temp
scanf(%d,&n);
for(i=3;i<=n;i++)
{
temp=s2;
s2+=s1;
s1=temp;
}
printf(%d\n,s2);
getch();
}
但是在某些場(chǎng)合，使用遞歸比使用循環(huán)要簡(jiǎn)單的多。而且有些題目，一看就知道應該使用遞歸而不是循環(huán)來(lái)處理。
【C語(yǔ)言函數遞歸教程】相關(guān)文章：
C語(yǔ)言函數的遞歸調用08-26
C語(yǔ)言函數的遞歸和調用08-22
C語(yǔ)言遞歸函數的執行與求解08-11
C語(yǔ)言中遞歸算法的剖析08-15
C++函數指針學(xué)習教程10-01
對C語(yǔ)言中遞歸算法的深入解析09-26