窩頭最近很煩惱，昨天老師講的遞歸算法，搞得一頭霧水，心里想著咋就啪啪啪幾下就給一個(gè)復(fù)雜的問題給解決了呢？于是，他準(zhǔn)備去找他們班的學(xué)霸咸菜。 窩頭：“咸菜你在干嘛？”。 咸菜沒好氣的說：“沒看見我在學(xué)習(xí)么？”。 窩頭想咸菜這是咋的啦，火氣那么大,想著自己是來請(qǐng)教問題的也就沒在意。舔著臉笑著說：“咸菜老妹啊，老師講的遞歸沒整明白，你給我指導(dǎo)指導(dǎo)唄！”。 咸菜看窩頭一臉真誠的樣子，就勉為其難的說：“好吧”。 于是，咸菜一邊說一邊敲著如下代碼：

咸菜對(duì)窩頭說：“看吧，是不是很簡單，其實(shí)就是自己調(diào)用自己而已！”。 窩頭說：“自己調(diào)用自己聽起來很酷，那它到底是怎么做到的呢”。 咸菜說：“知道你會(huì)這么問，我就給你畫個(gè)圖吧”。 咸菜說：“窩頭你注意看，我們的函數(shù)一旦調(diào)用就會(huì)被加載到棧中，每個(gè)棧幀就代表被調(diào)用的函數(shù)，這些函數(shù)以先進(jìn)后出的方式排列起來” 咸菜又說：“現(xiàn)在我們假設(shè)傳入的參數(shù)是3的話，在計(jì)算method（3）的時(shí)候，函數(shù)的返回值是3*method（2），但是method（2）的值我們還不知道，那么我們就去調(diào)用函數(shù)求method（2）的值，這樣就需要在棧上面從新開辟一塊空間來計(jì)算，然后是method（1），這樣不就遞歸下去了么，然后method（1），method（2），method（3）， 依次初棧，就能返回method（3）的值了” 窩頭，點(diǎn)頭表示懂了點(diǎn)。 咸菜又跟窩頭說：“但是，遞歸不是無限遞歸下去的，必須要有一個(gè)終止的條件，不然就永遠(yuǎn)循環(huán)下去了，再也跳不出來了” 窩頭又有疑問了：“如果數(shù)據(jù)足夠大的話，棧就需要不斷的去開辟空間，棧的內(nèi)存豈是遲早要放不下了？” 咸菜笑著說：“你還不算太笨，數(shù)據(jù)太大是會(huì)導(dǎo)致你說的情況發(fā)生，但是我們可以把代碼這樣改一下” 咸菜對(duì)窩頭說：“你看出來了有啥不一樣的么？” 窩頭說：“是有些不一樣，多傳了一個(gè)參數(shù)并且最后直接返回一個(gè)函數(shù)了” 咸菜說：“是的，這樣的話就只需要調(diào)用一個(gè)函數(shù)，只是每次傳入的參數(shù)不一樣罷了，以后不管你有多大都沒問題了” 窩頭：“nice！it’s amazing !” 咸菜：“這就是傳說中的尾遞歸，只要函數(shù)執(zhí)行最后的語句并且它的返回值不屬于函數(shù)表達(dá)式的一部分，就是尾遞歸” 窩頭：“咸菜你是我的偶像了！” 咸菜：“誰讓呢整天不學(xué)習(xí)，天天泡妞啊，這都不會(huì)” 窩頭不要臉的說：“以后我不在天天泡妞了，以后就泡你” 咸菜白了他一眼，轉(zhuǎn)過身去說了一句：“那看你的本事了” 未完待續(xù)……… 推薦：http://blog.csdn.net/qchengsj/article/details/37918083