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