不知道大家發(fā)現(xiàn)沒有,執(zhí)行遞歸算法兆旬,特別是遞歸執(zhí)行層數(shù)多的時(shí)候假抄,結(jié)果極其的慢,而且遞歸層數(shù)達(dá)到一定的值丽猬,還可能出現(xiàn)內(nèi)存溢出的情況宿饱。本文就要將為你解釋原因和對(duì)應(yīng)的解決方案。
一脚祟、遞歸與循環(huán)
1.1所謂的遞歸慢到底是什么原因呢谬以?
大家都知道遞歸的實(shí)現(xiàn)是通過調(diào)用函數(shù)本身,函數(shù)調(diào)用的時(shí)候由桌,每次調(diào)用時(shí)要做地址保存为黎,參數(shù)傳遞等,這是通過一個(gè)遞歸工作棧實(shí)現(xiàn)的行您。具體是每次調(diào)用函數(shù)本身要保存的內(nèi)容包括:局部變量铭乾、形參、調(diào)用函數(shù)地址娃循、返回值炕檩。那么,如果遞歸調(diào)用N次捌斧,就要分配N局部變量笛质、N形參、N調(diào)用函數(shù)地址捞蚂、N返回值妇押,這勢(shì)必是影響效率的,同時(shí)洞难,這也是內(nèi)存溢出的原因舆吮,因?yàn)榉e累了大量的中間變量無法釋放揭朝。
1.2用循環(huán)效率會(huì)比遞歸效率高嗎?
遞歸與循環(huán)是兩種不同的解決問題的典型思路色冀。當(dāng)然也并不是說循環(huán)效率就一定比遞歸高潭袱,遞歸和循環(huán)是兩碼事,遞歸帶有棧操作锋恬,循環(huán)則不一定屯换,兩個(gè)概念不是一個(gè)層次,不同場(chǎng)景做不同的嘗試与学。
2.1遞歸算法:
優(yōu)點(diǎn):代碼簡(jiǎn)潔彤悔、清晰,并且容易驗(yàn)證正確性索守。(如果你真的理解了算法的話晕窑,否則你更暈)
缺點(diǎn):它的運(yùn)行需要較多次數(shù)的函數(shù)調(diào)用,如果調(diào)用層數(shù)比較深卵佛,需要增加額外的堆棧處理(還有可能出現(xiàn)堆棧溢出的情況)杨赤,比如參數(shù)傳遞需要壓棧等操作,會(huì)對(duì)執(zhí)行效率有一定影響截汪。但是疾牲,對(duì)于某些問題,如果不使用遞歸衙解,那將是極端難看的代碼阳柔。
2.2循環(huán)算法:
優(yōu)點(diǎn):速度快,結(jié)構(gòu)簡(jiǎn)單蚓峦。
缺點(diǎn):并不能解決所有的問題舌剂。有的問題適合使用遞歸而不是循環(huán)。如果使用循環(huán)并不困難的話枫匾,最好使用循環(huán)架诞。
2.3遞歸算法和循環(huán)算法總結(jié):
1) 一般遞歸調(diào)用可以處理的算法,也可以通過循環(huán)去解決干茉,常需要額外的低效處理。
2)現(xiàn)在的編譯器在優(yōu)化后很泊,對(duì)于多次調(diào)用的函數(shù)處理會(huì)有非常好的效率優(yōu)化角虫,效率未必低于循環(huán)。
3) 遞歸和循環(huán)兩者完全可以互換委造。如果用到遞歸的地方可以很方便使用循環(huán)替換戳鹅,而不影響程序的閱讀,那么替換成遞歸往往是好的昏兆。(例如:求階乘的遞歸實(shí)現(xiàn)與循環(huán)實(shí)現(xiàn)枫虏。)
1.3.那么遞歸使用的棧是什么樣的一個(gè)棧呢?
首先,看一下系統(tǒng)棧和用戶棧的用途隶债。
3.1系統(tǒng)棧(也叫核心棧腾它、內(nèi)核棧)
是內(nèi)存中屬于操作系統(tǒng)空間的一塊區(qū)域,其主要用途為:
1)保存中斷現(xiàn)場(chǎng)死讹,對(duì)于嵌套中斷瞒滴,被中斷程序的現(xiàn)場(chǎng)信息依次壓入系統(tǒng)棧,中斷返回時(shí)逆序彈出赞警;
2)保存操作系統(tǒng)子程序間相互調(diào)用的參數(shù)妓忍、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量愧旦。
3.2用戶棧
是用戶進(jìn)程空間中的一塊區(qū)域世剖,用于保存用戶進(jìn)程的子程序間相互調(diào)用的參數(shù)、返回值笤虫、返回點(diǎn)以及子程序(函數(shù))的局部變量旁瘫。
我們編寫的遞歸程序?qū)儆谟脩舫绦颍虼耸褂玫氖怯脩魲耕皮!?/p>
二境蜕、遞歸與尾遞歸
以上初略介紹了遞歸與循環(huán)的實(shí)現(xiàn)機(jī)理,似乎代碼簡(jiǎn)潔和效率不能共存凌停。那么有沒有一種方法能擁有遞歸代碼簡(jiǎn)潔的好處粱年,同時(shí)給我們帶來更快的速率么?算法的世界會(huì)告訴你罚拟,一切皆有可能台诗。它的名字叫做尾遞歸。
讓遞歸和尾遞歸來做一個(gè)對(duì)比吧赐俗。
2.1遞歸
用線性遞歸實(shí)現(xiàn)Fibonacci函數(shù)拉队,程序如下所示:
int FibonacciRecursive(int n)
{
if( n < 2)
return n;
return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
}
遞歸寫的代碼非常容易懂,完全是根據(jù)函數(shù)的條件進(jìn)行選擇計(jì)算機(jī)步驟阻逮。例如現(xiàn)在要計(jì)算n=5時(shí)的值粱快,遞歸調(diào)用過程如下圖所示,可以看出叔扼,程序向下遞歸事哭,向上返回,所以每一步都需要存儲(chǔ)中間變量和過程瓜富。
2.2 尾遞歸
顧名思義鳍咱,尾遞歸就是從最后開始計(jì)算, 每遞歸一次就算出相應(yīng)的結(jié)果, 也就是說, 函數(shù)調(diào)用出現(xiàn)在調(diào)用者函數(shù)的尾部, 因?yàn)槭俏膊? 所以根本沒有必要去保存任何局部變量。直接讓被調(diào)用的函數(shù)返回時(shí)越過調(diào)用者, 返回到調(diào)用者的調(diào)用者去与柑。尾遞歸就是把當(dāng)前的運(yùn)算結(jié)果(或路徑)放在參數(shù)里傳給下層函數(shù)谤辜,深層函數(shù)所面對(duì)的不是越來越簡(jiǎn)單的問題蓄坏,而是越來越復(fù)雜的問題,因?yàn)閰?shù)里帶有前面若干步的運(yùn)算路徑丑念。
尾遞歸是極其重要的涡戳,不用尾遞歸,函數(shù)的堆棧耗用難以估量渠欺,需要保存很多中間函數(shù)的堆棧妹蔽。比如f(n, sum) = f(n-1) + value(n) + sum,會(huì)保存n個(gè)函數(shù)調(diào)用堆棧挠将,而使用尾遞歸f(n, sum) = f(n-1, sum+value(n))胳岂,這樣則只保留后一個(gè)函數(shù)堆棧即可。
采用尾遞歸實(shí)現(xiàn)Fibonacci函數(shù)舔稀,程序如下所示:
int FibonacciTailRecursive(int n,int ret1,int ret2)
{
if(n==0)
return ret1;
return FibonacciTailRecursive(n-1,ret2,ret1+ret2);
}
例如現(xiàn)在要計(jì)算n=5時(shí)的值乳丰,尾遞歸調(diào)用過程如下圖所示:從圖可以看出,尾遞歸不需要向上返回了内贮,但是需要引入額外的兩個(gè)空間來保持當(dāng)前的結(jié)果产园,這樣減少了中間變量的存儲(chǔ)和返回,大大提升了效率夜郁,而且避免了內(nèi)存溢出什燕。
三、舉一反三
相信很多讀者對(duì)于快速排序都耳熟能詳竞端,不知道各位還記得快速排序的實(shí)現(xiàn)就是基于遞歸實(shí)現(xiàn)的么屎即,于是這里就提供了一種優(yōu)化快速排序的方案,當(dāng)然尾遞歸不能改變快速排序的時(shí)間復(fù)雜度事富,但是提升性能還是沒問題的技俐。筆者不再做詳細(xì)介紹,只貼上實(shí)現(xiàn)代碼统台,留給各位獨(dú)立思考的空間雕擂。
int Partition(int *p,int len,int start,int last)
{
int flag=*(p+start);
int i=start;
int j=last;
while(i<j)
{
while(i<j && *(p+j)>flag) --j;
*(p+i)=*(p+j);
while(i<j && *(p+i)<=flag) ++i;
*(p+j)=*(p+i);
}
*(p+i)=flag;
return i;
}
void QuickSort(int *p,int len,int start,int last)
{
if(NULL=p) return;
int index;
while(start<last)
{
index=Partition(p,len,start,last);
QuickSort(p,len,start,index-1);
//QuickSort(p,len,index+1,last); /**遞歸調(diào)用*/
start=index+1; /**尾遞歸調(diào)用*/
}
}