引言
在調(diào)用一個(gè)函數(shù)的過(guò)程中有出現(xiàn)直接或間接地調(diào)用該函數(shù)本身,稱(chēng)為函數(shù)的遞歸調(diào)用.對(duì)于初學(xué)者來(lái)說(shuō),遞歸函數(shù)是比較難以理解的.現(xiàn)在的程序設(shè)計(jì)的教材對(duì)于遞歸都比較簡(jiǎn)單,例子從一開(kāi)始較難理解.加之不了解函數(shù)調(diào)用在計(jì)算機(jī)中的實(shí)現(xiàn)過(guò)程就更難理解遞歸調(diào)用了.這篇文章從初學(xué)者的角度對(duì)遞歸給予了一定的解釋.
從一個(gè)簡(jiǎn)單的數(shù)學(xué)題開(kāi)始
有一個(gè)等差數(shù)列,首項(xiàng)是3,公差是2,求第5項(xiàng)a5.我想這是所有高中生都會(huì)的題.再簡(jiǎn)單不過(guò),只要知道通項(xiàng)公式an=a1+(n-1)k (這里k是公差) 代入即可. 大家都知道通項(xiàng)是由遞推公式推導(dǎo)來(lái)的,遞推公式直接用數(shù)學(xué)語(yǔ)言反映了等差數(shù)列的性質(zhì),an=a(n-1)+k.如果大家不知道通項(xiàng)公式,那么在這道題中,計(jì)算的方法是:a2=a1+2;a3=a2+2;a4=a3+2;a5=a4+2.知道a5=11,經(jīng)過(guò)5次計(jì)算便可以得到a5的值.如果計(jì)算機(jī)也不知道通項(xiàng)公式,在如果我們要計(jì)算第一百項(xiàng),亦或是第一萬(wàn)項(xiàng),我們難道要a2=a1+2;a3=a2+2......a10000=a9999+2 這樣來(lái)計(jì)算嗎.當(dāng)然不是,我們可以用遞歸函數(shù)實(shí)現(xiàn),而a2=a1+2;a3=a2+2......a10000=a9999+2 的過(guò)程便是遞歸的回推過(guò)程,可是計(jì)算機(jī)確實(shí)沒(méi)有我們廣大高中生聰明,它不知道直接這樣求解,呵呵.
在計(jì)算機(jī)中的實(shí)現(xiàn)
要說(shuō)清楚遞歸函數(shù)的實(shí)現(xiàn)就要了解程序里函數(shù)嵌套調(diào)用在計(jì)算機(jī)中的實(shí)現(xiàn)過(guò)程.我們來(lái)看下面一個(gè)函數(shù)的調(diào)用,這里我們用類(lèi)似C語(yǔ)言的函數(shù)形式:
f()
{ .... //其他代碼
g(a); //調(diào)用函數(shù)g(),參數(shù)是a
return ... //函數(shù)的返回值
}
//-----------------------------------------------------------
main() //主函數(shù)
{ ..... //其他代碼
f(b); //調(diào)用函數(shù)f(),參數(shù)是b
}
主函數(shù)在執(zhí)行的過(guò)程中調(diào)用了函數(shù)f(),而f()其自身又調(diào)用了另一個(gè)函數(shù)g().那么這種嵌套調(diào)用在計(jì)算機(jī)中又是怎么實(shí)現(xiàn)的呢?在函數(shù)的執(zhí)行過(guò)程中,系統(tǒng)用到了棧內(nèi)存.棧是一種數(shù)據(jù)結(jié)構(gòu),就是有特定數(shù)據(jù)存取方式的容器.棧使用的存取方式稱(chēng)為后進(jìn)先出LIFO(late in first out),也就是后面放入的數(shù)據(jù)先離開(kāi)棧,最先放入的數(shù)據(jù)最后離開(kāi).大家可以把?？闯梢粋€(gè)和盤(pán)子一樣大小放的水槽,放入其中的盤(pán)子只能從最上面依次取走,不下面的盤(pán)子只能等它上面的取走之后才能取出.棧是一種在計(jì)算機(jī)中非常重要的數(shù)據(jù)結(jié)構(gòu),它后進(jìn)先出的性質(zhì)也直接關(guān)系到了函數(shù)嵌套調(diào)用在計(jì)算機(jī)中的實(shí)現(xiàn).
當(dāng)一個(gè)函數(shù)的執(zhí)行過(guò)程中需要調(diào)用另一個(gè)函數(shù)時(shí),需要保留現(xiàn)場(chǎng),意思是系統(tǒng)保存現(xiàn)有的所有數(shù)據(jù),把他們放入棧內(nèi)存,稱(chēng)為壓入棧.之后就轉(zhuǎn)到要調(diào)用的那個(gè)函數(shù)處執(zhí)行了,并把參數(shù)傳給它.等到調(diào)用的那個(gè)函數(shù)執(zhí)行完了,系統(tǒng)就把剛才壓入棧內(nèi)存的數(shù)據(jù)都取出,稱(chēng)為彈出棧.并且把他調(diào)用的函數(shù)的返回值給原函數(shù).如果被調(diào)用的函數(shù)中還要調(diào)用其他函數(shù),系統(tǒng)也按照上述的方法保存和取回?cái)?shù)據(jù).棧的性質(zhì)能很好得適用于這一過(guò)程.
在來(lái)看遞歸函數(shù),按引言里的意思,在上述的過(guò)程中被調(diào)用的函數(shù)就是調(diào)用函數(shù)自己.其實(shí)現(xiàn)的過(guò)程是一樣的.是不是很簡(jiǎn)單?
再看一些例子
文章開(kāi)始等差數(shù)列的例子寫(xiě)成函數(shù)就是(方便起見(jiàn),值都設(shè)為整數(shù)):
int getan(int n, int a1) // 要求第n項(xiàng),a1為已知的首項(xiàng)
{
if(n==1)
return a1; //如果n=1,返回a1的值,這是遞歸得以結(jié)束的關(guān)鍵
else
return getan(n-1,a1)+2 ; //不等于1,則再次調(diào)用自身求出第n-1項(xiàng),返回結(jié)果加上公差2
}
//-------------------------------------------------------
main() //主函數(shù)
{
int a1=3; //設(shè)首項(xiàng)
int a5=getan(5,3); //遞歸求解第5項(xiàng)a5
printf(d%,a5); //輸出
}
遞歸函數(shù)調(diào)用自身是一個(gè)不斷循環(huán)過(guò)程,就像循環(huán)語(yǔ)句需要有條件讓它停止循環(huán),否則就陷入了無(wú)限循環(huán)之中,那后果......天啊!所以if(n=1) return a1;就是停止遞歸的條件.
我們來(lái)仔細(xì)地看一下a5是如何求出的,不要嫌羅嗦,來(lái):
首先當(dāng)主函數(shù)執(zhí)行到int a5=getan(5,3); 開(kāi)始求 a5的值.
n=5>1 所以gatan()函數(shù)又調(diào)用自身,并把參數(shù)5-1=4和3傳給下一個(gè)函數(shù),所以執(zhí)行g(shù)etan(4,3);
n=4>1 gatan()函數(shù)再次調(diào)用自身,并把參數(shù)3和3傳給下一個(gè)函數(shù),所以執(zhí)行g(shù)etan(3,3);
n=3>1 執(zhí)行g(shù)etan(2,3);
n=2>1 執(zhí)行g(shù)etan(1,3);
終于,n=1了,現(xiàn)在getan(1,3)的返回值是3.
getan(2,3); 返回值是3+2=5.
getan(3,3);返回7.
getan(4,3);返回9.
最后getan(5,3);返回11,變量a5=11,結(jié)果也就出來(lái)了.
從理論上我們把函數(shù)反復(fù)調(diào)用自身的過(guò)程稱(chēng)為遞推的過(guò)程,而每個(gè)函數(shù)的返回稱(chēng)之為回推.遞推的過(guò)程把復(fù)雜的問(wèn)題一步步分解開(kāi),直到出現(xiàn)最簡(jiǎn)單的情況,就像已知a1=3.得到了最簡(jiǎn)單情況的解,就可以回推回去得出原來(lái)復(fù)雜問(wèn)題的答案了.要說(shuō)明的一點(diǎn)是,在這里我們認(rèn)為函數(shù)的使用者總是正確的,不會(huì)把諸如-1,0,5.2等之類(lèi)不合理項(xiàng)數(shù)作為參數(shù)輸入,所以沒(méi)有做出錯(cuò)檢查.
在調(diào)用一個(gè)函數(shù)的過(guò)程中有出現(xiàn)直接或間接地調(diào)用該函數(shù)本身,稱(chēng)為函數(shù)的遞歸調(diào)用.對(duì)于初學(xué)者來(lái)說(shuō),遞歸函數(shù)是比較難以理解的.現(xiàn)在的程序設(shè)計(jì)的教材對(duì)于遞歸都比較簡(jiǎn)單,例子從一開(kāi)始較難理解.加之不了解函數(shù)調(diào)用在計(jì)算機(jī)中的實(shí)現(xiàn)過(guò)程就更難理解遞歸調(diào)用了.這篇文章從初學(xué)者的角度對(duì)遞歸給予了一定的解釋.
從一個(gè)簡(jiǎn)單的數(shù)學(xué)題開(kāi)始
有一個(gè)等差數(shù)列,首項(xiàng)是3,公差是2,求第5項(xiàng)a5.我想這是所有高中生都會(huì)的題.再簡(jiǎn)單不過(guò),只要知道通項(xiàng)公式an=a1+(n-1)k (這里k是公差) 代入即可. 大家都知道通項(xiàng)是由遞推公式推導(dǎo)來(lái)的,遞推公式直接用數(shù)學(xué)語(yǔ)言反映了等差數(shù)列的性質(zhì),an=a(n-1)+k.如果大家不知道通項(xiàng)公式,那么在這道題中,計(jì)算的方法是:a2=a1+2;a3=a2+2;a4=a3+2;a5=a4+2.知道a5=11,經(jīng)過(guò)5次計(jì)算便可以得到a5的值.如果計(jì)算機(jī)也不知道通項(xiàng)公式,在如果我們要計(jì)算第一百項(xiàng),亦或是第一萬(wàn)項(xiàng),我們難道要a2=a1+2;a3=a2+2......a10000=a9999+2 這樣來(lái)計(jì)算嗎.當(dāng)然不是,我們可以用遞歸函數(shù)實(shí)現(xiàn),而a2=a1+2;a3=a2+2......a10000=a9999+2 的過(guò)程便是遞歸的回推過(guò)程,可是計(jì)算機(jī)確實(shí)沒(méi)有我們廣大高中生聰明,它不知道直接這樣求解,呵呵.
在計(jì)算機(jī)中的實(shí)現(xiàn)
要說(shuō)清楚遞歸函數(shù)的實(shí)現(xiàn)就要了解程序里函數(shù)嵌套調(diào)用在計(jì)算機(jī)中的實(shí)現(xiàn)過(guò)程.我們來(lái)看下面一個(gè)函數(shù)的調(diào)用,這里我們用類(lèi)似C語(yǔ)言的函數(shù)形式:
f()
{ .... //其他代碼
g(a); //調(diào)用函數(shù)g(),參數(shù)是a
return ... //函數(shù)的返回值
}
//-----------------------------------------------------------
main() //主函數(shù)
{ ..... //其他代碼
f(b); //調(diào)用函數(shù)f(),參數(shù)是b
}
主函數(shù)在執(zhí)行的過(guò)程中調(diào)用了函數(shù)f(),而f()其自身又調(diào)用了另一個(gè)函數(shù)g().那么這種嵌套調(diào)用在計(jì)算機(jī)中又是怎么實(shí)現(xiàn)的呢?在函數(shù)的執(zhí)行過(guò)程中,系統(tǒng)用到了棧內(nèi)存.棧是一種數(shù)據(jù)結(jié)構(gòu),就是有特定數(shù)據(jù)存取方式的容器.棧使用的存取方式稱(chēng)為后進(jìn)先出LIFO(late in first out),也就是后面放入的數(shù)據(jù)先離開(kāi)棧,最先放入的數(shù)據(jù)最后離開(kāi).大家可以把?？闯梢粋€(gè)和盤(pán)子一樣大小放的水槽,放入其中的盤(pán)子只能從最上面依次取走,不下面的盤(pán)子只能等它上面的取走之后才能取出.棧是一種在計(jì)算機(jī)中非常重要的數(shù)據(jù)結(jié)構(gòu),它后進(jìn)先出的性質(zhì)也直接關(guān)系到了函數(shù)嵌套調(diào)用在計(jì)算機(jī)中的實(shí)現(xiàn).
當(dāng)一個(gè)函數(shù)的執(zhí)行過(guò)程中需要調(diào)用另一個(gè)函數(shù)時(shí),需要保留現(xiàn)場(chǎng),意思是系統(tǒng)保存現(xiàn)有的所有數(shù)據(jù),把他們放入棧內(nèi)存,稱(chēng)為壓入棧.之后就轉(zhuǎn)到要調(diào)用的那個(gè)函數(shù)處執(zhí)行了,并把參數(shù)傳給它.等到調(diào)用的那個(gè)函數(shù)執(zhí)行完了,系統(tǒng)就把剛才壓入棧內(nèi)存的數(shù)據(jù)都取出,稱(chēng)為彈出棧.并且把他調(diào)用的函數(shù)的返回值給原函數(shù).如果被調(diào)用的函數(shù)中還要調(diào)用其他函數(shù),系統(tǒng)也按照上述的方法保存和取回?cái)?shù)據(jù).棧的性質(zhì)能很好得適用于這一過(guò)程.
在來(lái)看遞歸函數(shù),按引言里的意思,在上述的過(guò)程中被調(diào)用的函數(shù)就是調(diào)用函數(shù)自己.其實(shí)現(xiàn)的過(guò)程是一樣的.是不是很簡(jiǎn)單?
再看一些例子
文章開(kāi)始等差數(shù)列的例子寫(xiě)成函數(shù)就是(方便起見(jiàn),值都設(shè)為整數(shù)):
int getan(int n, int a1) // 要求第n項(xiàng),a1為已知的首項(xiàng)
{
if(n==1)
return a1; //如果n=1,返回a1的值,這是遞歸得以結(jié)束的關(guān)鍵
else
return getan(n-1,a1)+2 ; //不等于1,則再次調(diào)用自身求出第n-1項(xiàng),返回結(jié)果加上公差2
}
//-------------------------------------------------------
main() //主函數(shù)
{
int a1=3; //設(shè)首項(xiàng)
int a5=getan(5,3); //遞歸求解第5項(xiàng)a5
printf(d%,a5); //輸出
}
遞歸函數(shù)調(diào)用自身是一個(gè)不斷循環(huán)過(guò)程,就像循環(huán)語(yǔ)句需要有條件讓它停止循環(huán),否則就陷入了無(wú)限循環(huán)之中,那后果......天啊!所以if(n=1) return a1;就是停止遞歸的條件.
我們來(lái)仔細(xì)地看一下a5是如何求出的,不要嫌羅嗦,來(lái):
首先當(dāng)主函數(shù)執(zhí)行到int a5=getan(5,3); 開(kāi)始求 a5的值.
n=5>1 所以gatan()函數(shù)又調(diào)用自身,并把參數(shù)5-1=4和3傳給下一個(gè)函數(shù),所以執(zhí)行g(shù)etan(4,3);
n=4>1 gatan()函數(shù)再次調(diào)用自身,并把參數(shù)3和3傳給下一個(gè)函數(shù),所以執(zhí)行g(shù)etan(3,3);
n=3>1 執(zhí)行g(shù)etan(2,3);
n=2>1 執(zhí)行g(shù)etan(1,3);
終于,n=1了,現(xiàn)在getan(1,3)的返回值是3.
getan(2,3); 返回值是3+2=5.
getan(3,3);返回7.
getan(4,3);返回9.
最后getan(5,3);返回11,變量a5=11,結(jié)果也就出來(lái)了.
從理論上我們把函數(shù)反復(fù)調(diào)用自身的過(guò)程稱(chēng)為遞推的過(guò)程,而每個(gè)函數(shù)的返回稱(chēng)之為回推.遞推的過(guò)程把復(fù)雜的問(wèn)題一步步分解開(kāi),直到出現(xiàn)最簡(jiǎn)單的情況,就像已知a1=3.得到了最簡(jiǎn)單情況的解,就可以回推回去得出原來(lái)復(fù)雜問(wèn)題的答案了.要說(shuō)明的一點(diǎn)是,在這里我們認(rèn)為函數(shù)的使用者總是正確的,不會(huì)把諸如-1,0,5.2等之類(lèi)不合理項(xiàng)數(shù)作為參數(shù)輸入,所以沒(méi)有做出錯(cuò)檢查.