遞歸為什么那么慢柿冲?遞歸的改進(jìn)算法

不知道大家發(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)用*/
   }          
} 
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市贱勃,隨后出現(xiàn)的幾起案子井赌,更是在濱河造成了極大的恐慌,老刑警劉巖贵扰,帶你破解...
    沈念sama閱讀 222,590評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件族展,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡拔鹰,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門贵涵,熙熙樓的掌柜王于貴愁眉苦臉地迎上來列肢,“玉大人恰画,你說我怎么就攤上這事〈陕恚” “怎么了拴还?”我有些...
    開封第一講書人閱讀 169,301評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)欧聘。 經(jīng)常有香客問我片林,道長(zhǎng),這世上最難降的妖魔是什么怀骤? 我笑而不...
    開封第一講書人閱讀 60,078評(píng)論 1 300
  • 正文 為了忘掉前任费封,我火速辦了婚禮,結(jié)果婚禮上蒋伦,老公的妹妹穿的比我還像新娘弓摘。我一直安慰自己,他們只是感情好痕届,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,082評(píng)論 6 398
  • 文/花漫 我一把揭開白布韧献。 她就那樣靜靜地躺著,像睡著了一般研叫。 火紅的嫁衣襯著肌膚如雪锤窑。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,682評(píng)論 1 312
  • 那天嚷炉,我揣著相機(jī)與錄音渊啰,去河邊找鬼。 笑死渤昌,一個(gè)胖子當(dāng)著我的面吹牛虽抄,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播独柑,決...
    沈念sama閱讀 41,155評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼迈窟,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了忌栅?” 一聲冷哼從身側(cè)響起车酣,我...
    開封第一講書人閱讀 40,098評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎索绪,沒想到半個(gè)月后湖员,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡瑞驱,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,701評(píng)論 3 342
  • 正文 我和宋清朗相戀三年娘摔,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片唤反。...
    茶點(diǎn)故事閱讀 40,852評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡凳寺,死狀恐怖鸭津,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情肠缨,我是刑警寧澤逆趋,帶...
    沈念sama閱讀 36,520評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站晒奕,受9級(jí)特大地震影響闻书,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜脑慧,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,181評(píng)論 3 335
  • 文/蒙蒙 一魄眉、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧漾橙,春花似錦杆融、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至淘捡,卻和暖如春藕各,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背焦除。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工激况, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人膘魄。 一個(gè)月前我還...
    沈念sama閱讀 49,279評(píng)論 3 379
  • 正文 我出身青樓乌逐,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親创葡。 傳聞我的和親對(duì)象是個(gè)殘疾皇子浙踢,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,851評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容