可能很多人在大一的時候,就已經(jīng)接觸了遞歸了,不過,我敢保證很多人初學(xué)者剛開始接觸遞歸的時候,是一臉懵逼的,我當(dāng)初也是,給我的感覺就是,遞歸太神奇了!
可能也有一大部分人知道遞歸,也能看的懂遞歸,但在實際做題過程中,卻不知道怎么使用,有時候還容易被遞歸給搞暈。也有好幾個人來問我有沒有快速掌握遞歸的捷徑啊。說實話,哪來那么多捷徑啊,不過,我還是想寫一篇文章,談?wù)勎业囊恍┙?jīng)驗,或許,能夠給你帶來一些幫助。
為了兼顧初學(xué)者,我會從最簡單的題講起!
遞歸的三大要素
第一要素:明確你這個函數(shù)想要干什么
對于遞歸,我覺得很重要的一個事就是,這個函數(shù)的功能是什么,他要完成什么樣的一件事,而這個,是完全由你自己來定義的。也就是說,我們先不管函數(shù)里面的代碼什么,而是要先明白,你這個函數(shù)是要用來干什么。
例如,我定義了一個函數(shù)
1//算n的階乘(假設(shè)n不為0)2intf(intn){34}
這個函數(shù)的功能是算 n 的階乘。好了,我們已經(jīng)定義了一個函數(shù),并且定義了它的功能是什么,接下來我們看第二要素。
第二要素:尋找遞歸結(jié)束條件
所謂遞歸,就是會在函數(shù)內(nèi)部代碼中,調(diào)用這個函數(shù)本身,所以,我們必須要找出遞歸的結(jié)束條件,不然的話,會一直調(diào)用自己,進(jìn)入無底洞。也就是說,我們需要找出當(dāng)參數(shù)為啥時,遞歸結(jié)束,之后直接把結(jié)果返回,請注意,這個時候我們必須能根據(jù)這個參數(shù)的值,能夠直接知道函數(shù)的結(jié)果是什么。
例如,上面那個例子,當(dāng) n = 1 時,那你應(yīng)該能夠直接知道 f(n) 是啥吧?此時,f(1) = 1。完善我們函數(shù)內(nèi)部的代碼,把第二要素加進(jìn)代碼里面,如下
1//算n的階乘(假設(shè)n不為0)2intf(intn){3if(n==1){4return1;5}6}
有人可能會說,當(dāng) n = 2 時,那我們可以直接知道 f(n) 等于多少啊,那我可以把 n = 2 作為遞歸的結(jié)束條件嗎?
當(dāng)然可以,只要你覺得參數(shù)是什么時,你能夠直接知道函數(shù)的結(jié)果,那么你就可以把這個參數(shù)作為結(jié)束的條件,所以下面這段代碼也是可以的。
1//算n的階乘(假設(shè)n>=2)2intf(intn){3if(n==2){4return2;5}6}
注意我代碼里面寫的注釋,假設(shè) n >= 2,因為如果 n = 1時,會被漏掉,當(dāng) n <= 2時,f(n) = n,所以為了更加嚴(yán)謹(jǐn),我們可以寫成這樣:
1//算n的階乘(假設(shè)n不為0)2intf(intn){3if(n<=?2){4????????return?n;5????}6}
第三要素:找出函數(shù)的等價關(guān)系式
第三要素就是,我們要不斷縮小參數(shù)的范圍,縮小之后,我們可以通過一些輔助的變量或者操作,使原函數(shù)的結(jié)果不變。
例如,f(n) 這個范圍比較大,我們可以讓 f(n) = n * f(n-1)。這樣,范圍就由 n 變成了 n-1 了,范圍變小了,并且為了原函數(shù)f(n) 不變,我們需要讓 f(n-1) 乘以 n。
說白了,就是要找到原函數(shù)的一個等價關(guān)系式,f(n) 的等價關(guān)系式為 n * f(n-1),即
f(n) = n * f(n-1)。
這個等價關(guān)系式的尋找,可以說是最難的一步了,如果你不大懂也沒關(guān)系,因為你不是天才,你還需要多接觸幾道題,我會在接下來的文章中,找 10 道遞歸題,讓你慢慢熟悉起來。
找出了這個等價,繼續(xù)完善我們的代碼,我們把這個等價式寫進(jìn)函數(shù)里。如下:
1//算n的階乘(假設(shè)n不為0)2intf(intn){3if(n<=?2){4????????return?n;5????}6????//?把?f(n)?的等價操作寫進(jìn)去7????return?f(n-1)?*?n;8}
至此,遞歸三要素已經(jīng)都寫進(jìn)代碼里了,所以這個 f(n) 功能的內(nèi)部代碼我們已經(jīng)寫好了。
這就是遞歸最重要的三要素,每次做遞歸的時候,你就強(qiáng)迫自己試著去尋找這三個要素。
還是不懂?沒關(guān)系,我再按照這個模式講一些題。
有些有點(diǎn)小基礎(chǔ)的可能覺得我寫的太簡單了,沒耐心看?少俠,請繼續(xù)看,我下面還會講如何優(yōu)化遞歸。當(dāng)然,大佬請隨意,可以直接拉動最下面留言給我一些建議,萬分感謝!
案例1:斐波那契數(shù)列
斐波那契數(shù)列的是這樣一個數(shù)列:1、1、2、3、5、8、13、21、34….,即第一項 f(1) = 1,第二項 f(2) = 1…..,第 n 項目為 f(n) = f(n-1) + f(n-2)。求第 n 項的值是多少。
1、第一遞歸函數(shù)功能
假設(shè) f(n) 的功能是求第 n 項的值,代碼如下:
1intf(intn){23}
2、找出遞歸結(jié)束的條件
顯然,當(dāng) n = 1 或者 n = 2 ,我們可以輕易著知道結(jié)果 f(1) = f(2) = 1。所以遞歸結(jié)束條件可以為 n <= 2。代碼如下:
1intf(intn){2if(n<=?2){3????????return?1;4????}5}
第三要素:找出函數(shù)的等價關(guān)系式
題目已經(jīng)把等價關(guān)系式給我們了,所以我們很容易就能夠知道 f(n) = f(n-1) + f(n-2)。我說過,等價關(guān)系式是最難找的一個,而這個題目卻把關(guān)系式給我們了,這也太容易,好吧,我這是為了兼顧幾乎零基礎(chǔ)的讀者。
所以最終代碼如下:
1intf(intn){2//1.先寫遞歸結(jié)束條件3if(n<=?2){4????????return?1;5????}6????//?2.接著寫等價關(guān)系式7????return?f(n-1)?+?f(n?-?2);8}
搞定,是不是很簡單?
零基礎(chǔ)的可能還是不大懂,沒關(guān)系,之后慢慢按照這個模式練習(xí)!好吧,有大佬可能在吐槽太簡單了。
案例2:小青蛙跳臺階
一只青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
1、第一遞歸函數(shù)功能
假設(shè) f(n) 的功能是求青蛙跳上一個n級的臺階總共有多少種跳法,代碼如下:
1intf(intn){23}
2、找出遞歸結(jié)束的條件
我說了,求遞歸結(jié)束的條件,你直接把 n 壓縮到很小很小就行了,因為 n 越小,我們就越容易直觀著算出 f(n) 的多少,所以當(dāng) n = 1時,你知道 f(1) 為多少吧?夠直觀吧?即 f(1) = 1。代碼如下:
1intf(intn){2if(n==1){3return1;4}5}
第三要素:找出函數(shù)的等價關(guān)系式
每次跳的時候,小青蛙可以跳一個臺階,也可以跳兩個臺階,也就是說,每次跳的時候,小青蛙有兩種跳法。
第一種跳法:第一次我跳了一個臺階,那么還剩下n-1個臺階還沒跳,剩下的n-1個臺階的跳法有f(n-1)種。
第二種跳法:第一次跳了兩個臺階,那么還剩下n-2個臺階還沒,剩下的n-2個臺階的跳法有f(n-2)種。
所以,小青蛙的全部跳法就是這兩種跳法之和了,即 f(n) = f(n-1) + f(n-2)。至此,等價關(guān)系式就求出來了。于是寫出代碼:
1intf(intn){2if(n==1){3return1;4}5ruturnf(n-1)+f(n-2);6}
大家覺得上面的代碼對不對?
答是不大對,當(dāng) n = 2 時,顯然會有 f(2) = f(1) + f(0)。我們知道,f(0) = 0,按道理是遞歸結(jié)束,不用繼續(xù)往下調(diào)用的,但我們上面的代碼邏輯中,會繼續(xù)調(diào)用 f(0) = f(-1) + f(-2)。這會導(dǎo)致無限調(diào)用,進(jìn)入死循環(huán)。
這也是我要和你們說的,關(guān)于遞歸結(jié)束條件是否夠嚴(yán)謹(jǐn)問題,有很多人在使用遞歸的時候,由于結(jié)束條件不夠嚴(yán)謹(jǐn),導(dǎo)致出現(xiàn)死循環(huán)。也就是說,當(dāng)我們在第二步找出了一個遞歸結(jié)束條件的時候,可以把結(jié)束條件寫進(jìn)代碼,然后進(jìn)行第三步,但是請注意,當(dāng)我們第三步找出等價函數(shù)之后,還得再返回去第二步,根據(jù)第三步函數(shù)的調(diào)用關(guān)系,會不會出現(xiàn)一些漏掉的結(jié)束條件。就像上面,f(n-2)這個函數(shù)的調(diào)用,有可能出現(xiàn) f(0) 的情況,導(dǎo)致死循環(huán),所以我們把它補(bǔ)上。代碼如下:
1intf(intn){2//f(0)=0,f(1)=1,等價于n<=1時,f(n)?=?n。3????if(n?<=?1){4????????return?n;5????}6????ruturn?f(n-1)?+?f(n-2);7}
有人可能會說,我不知道我的結(jié)束條件有沒有漏掉怎么辦?別怕,多練幾道就知道怎么辦了。
看到這里有人可能要吐槽了,這兩道題也太容易了吧??能不能被這么敷衍。少俠,別走啊,下面出道難一點(diǎn)的。
下面其實也不難了,就比上面的題目難一點(diǎn)點(diǎn)而已,特別是第三步等價的尋找。
案例3:反轉(zhuǎn)單鏈表。
反轉(zhuǎn)單鏈表。例如鏈表為:1->2->3->4。反轉(zhuǎn)后為 4->3->2->1
鏈表的節(jié)點(diǎn)定義如下:
1classNode{2intdate;3Nodenext;4}
雖然是 Java語言,但就算你沒學(xué)過 Java,我覺得也是影響不大,能看懂。
還是老套路,三要素一步一步來。
1、定義遞歸函數(shù)功能
假設(shè)函數(shù) reverseList(head) 的功能是反轉(zhuǎn)但鏈表,其中 head 表示鏈表的頭節(jié)點(diǎn)。代碼如下:
1NodereverseList(Nodehead){23}
2. 尋找結(jié)束條件
當(dāng)鏈表只有一個節(jié)點(diǎn),或者如果是空表的話,你應(yīng)該知道結(jié)果吧?直接啥也不用干,直接把 head 返回唄。代碼如下:
1NodereverseList(Nodehead){2if(head==null||head.next==null){3returnhead;4}5}
3. 尋找等價關(guān)系
這個的等價關(guān)系不像 n 是個數(shù)值那樣,比較容易尋找。但是我告訴你,它的等價條件中,一定是范圍不斷在縮小,對于鏈表來說,就是鏈表的節(jié)點(diǎn)個數(shù)不斷在變小,所以,如果你實在找不出,你就先對 reverseList(head.next) 遞歸走一遍,看看結(jié)果是咋樣的。例如鏈表節(jié)點(diǎn)如下
我們就縮小范圍,先對 2->3->4遞歸下試試,即代碼如下
1NodereverseList(Nodehead){2if(head==null||head.next==null){3returnhead;4}5//我們先把遞歸的結(jié)果保存起來,先不返回,因為我們還不清楚這樣遞歸是對還是錯。,6NodenewList=reverseList(head.next);7}
我們在第一步的時候,就已經(jīng)定義了 reverseLis t函數(shù)的功能可以把一個單鏈表反轉(zhuǎn),所以,我們對 2->3->4反轉(zhuǎn)之后的結(jié)果應(yīng)該是這樣:
我們把 2->3->4 遞歸成 4->3->2。不過,1 這個節(jié)點(diǎn)我們并沒有去碰它,所以 1 的 next 節(jié)點(diǎn)仍然是連接這 2。
接下來呢?該怎么辦?
其實,接下來就簡單了,我們接下來只需要把節(jié)點(diǎn) 2 的 next 指向 1,然后把 1 的 next 指向 null,不就行了?,即通過改變 newList 鏈表之后的結(jié)果如下:
也就是說,reverseList(head) 等價于 ** reverseList(head.next)** +改變一下1,2兩個節(jié)點(diǎn)的指向。好了,等價關(guān)系找出來了,代碼如下(有詳細(xì)的解釋):
1//用遞歸的方法反轉(zhuǎn)鏈表 2publicstaticNodereverseList2(Nodehead){ 3//1.遞歸結(jié)束條件 4if(head==null||head.next==null){ 5returnhead; 6} 7//遞歸反轉(zhuǎn)子鏈表 8NodenewList=reverseList2(head.next); 9//改變1,2節(jié)點(diǎn)的指向。10//通過head.next獲取節(jié)點(diǎn)211Nodet1=head.next;12//讓2的next指向213t1.next=head;14//1的next指向null.15head.next=null;16//把調(diào)整之后的鏈表返回。17returnnewList;18}
這道題的第三步看的很懵?正常,因為你做的太少了,可能沒有想到還可以這樣,多練幾道就可以了。但是,我希望通過這三道題,給了你以后用遞歸做題時的一些思路,你以后做題可以按照我這個模式去想。通過一篇文章是不可能掌握遞歸的,還得多練,我相信,只要你認(rèn)真看我的這篇文章,多看幾次,一定能找到一些思路??!
我已經(jīng)強(qiáng)調(diào)了好多次,多練幾道了,所以呢,后面我也會找大概 10 道遞歸的練習(xí)題供大家學(xué)習(xí),不過,我找的可能會有一定的難度。不會像今天這樣,比較簡單,所以呢,初學(xué)者還得自己多去找題練練,相信我,掌握了遞歸,你的思維抽象能力會更強(qiáng)!
接下來我講講有關(guān)遞歸的一些優(yōu)化。
有關(guān)遞歸的一些優(yōu)化思路
1. 考慮是否重復(fù)計算
告訴你吧,如果你使用遞歸的時候不進(jìn)行優(yōu)化,是有非常非常非常多的子問題被重復(fù)計算的。
啥是子問題? f(n-1),f(n-2)….就是 f(n) 的子問題了。
例如對于案例2那道題,f(n) = f(n-1) + f(n-2)。遞歸調(diào)用的狀態(tài)圖如下:
看到?jīng)]有,遞歸計算的時候,重復(fù)計算了兩次 f(5),五次 f(4)。。。。這是非??植赖?,n 越大,重復(fù)計算的就越多,所以我們必須進(jìn)行優(yōu)化。
如何優(yōu)化?一般我們可以把我們計算的結(jié)果保證起來,例如把 f(4) 的計算結(jié)果保證起來,當(dāng)再次要計算 f(4) 的時候,我們先判斷一下,之前是否計算過,如果計算過,直接把 f(4) 的結(jié)果取出來就可以了,沒有計算過的話,再遞歸計算。
用什么保存呢?可以用數(shù)組或者 HashMap 保存,我們用數(shù)組來保存把,把 n 作為我們的數(shù)組下標(biāo),f(n) 作為值,例如 arr[n] = f(n)。f(n) 還沒有計算過的時候,我們讓 arr[n] 等于一個特殊值,例如 arr[n] = -1。
當(dāng)我們要判斷的時候,如果 arr[n] = -1,則證明 f(n) 沒有計算過,否則, f(n) 就已經(jīng)計算過了,且 f(n) = arr[n]。直接把值取出來就行了。代碼如下:
1//我們實現(xiàn)假定arr數(shù)組已經(jīng)初始化好的了。 2intf(intn){ 3if(n<=?1){ 4????????return?n; 5????} 6????//先判斷有沒計算過 7????if(arr[n]?!=?-1){ 8????????//計算過,直接返回 9????????return?arr[n];10????}else{11????????//?沒有計算過,遞歸計算,并且把結(jié)果保存到?arr數(shù)組里12????????arr[n]?=?f(n-1)?+?f(n-1);13????????reutrn?arr[n];14????}15}
也就是說,使用遞歸的時候,必要須要考慮有沒有重復(fù)計算,如果重復(fù)計算了,一定要把計算過的狀態(tài)保存起來。
2. 考慮是否可以自底向上
對于遞歸的問題,我們一般都是從上往下遞歸的,直到遞歸到最底,再一層一層著把值返回。
不過,有時候當(dāng) n 比較大的時候,例如當(dāng) n = 10000 時,那么必須要往下遞歸10000層直到 n <=1 才將結(jié)果慢慢返回,如果n太大的話,可能??臻g會不夠用。
對于這種情況,其實我們是可以考慮自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我們就可以推出 f(3) = f(2) + f(1) = 3。從而可以推出f(4),f(5)等直到f(n)。因此,我們可以考慮使用自底向上的方法來取代遞歸,代碼如下:
1publicintf(intn){ 2if(n<=?2) 3???????????return?n; 4???????int?f1?=?1; 5???????int?f2?=?2; 6???????int?sum?=?0; 7 8???????for?(int?i?=?3;?i?<=?n;?i++)?{ 9???????????sum?=?f1?+?f2;10???????????f1?=?f2;11???????????f2?=?sum;12???????}13???????return?sum;14???}
這種方法,其實也被稱之為遞推。
最后總結(jié)
其實,遞歸不一定總是從上往下,也是有很多是從下往上的,例如 n = 1 開始,一直遞歸到 n = 1000,例如一些排序組合。對于這種從下往上的,也是有對應(yīng)的優(yōu)化技巧,不過,我就先不寫了,后面再慢慢寫。這篇文章寫了很久了,脖子有點(diǎn)受不了了,,,,頸椎???害怕。。。。
說實話,對于遞歸這種比較抽象的思想,要把他講明白,特別是講給初學(xué)者聽,還是挺難的,這也是我這篇文章用了很長時間的原因,不過,只要能讓你們看完,有所收獲,我覺得值得!有些人可能覺得講的有點(diǎn)簡單,沒事,我后面會找一些不怎么簡單的題。
-
函數(shù)
+關(guān)注
關(guān)注
3文章
4262瀏覽量
62233 -
遞歸
+關(guān)注
關(guān)注
0文章
28瀏覽量
8999
原文標(biāo)題:為什么你學(xué)不會遞歸?告別遞歸,談?wù)勎业囊恍┙?jīng)驗
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論