不知道大家發(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);
}
從圖可以看出，尾遞歸不需要向上返回了内贮，但是需要引入額外的兩個(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)用*／
}
}
