前言
遞歸是一種非常重要的算法思想,無論你是前端開發(fā),還是后端開發(fā),都需要掌握它。在日常工作中,統(tǒng)計(jì)文件夾大小,解析xml文件等等,都需要用到遞歸算法。它太基礎(chǔ)太重要了,這也是為什么面試的時(shí)候,面試官經(jīng)常讓我們手寫遞歸算法。本文呢,將跟大家一起學(xué)習(xí)遞歸算法~
-
什么是遞歸? -
遞歸的特點(diǎn) -
遞歸與棧的關(guān)系 -
遞歸應(yīng)用場景 -
遞歸解題思路 -
leetcode案例分析 -
遞歸可能存在的問題以及解決方案
什么是遞歸?
遞歸,在計(jì)算機(jī)科學(xué)中是指一種通過重復(fù)將問題分解為同類的子問題而解決問題的方法。簡單來說,遞歸表現(xiàn)為函數(shù)調(diào)用函數(shù)本身。在知乎看到一個(gè)比喻遞歸的例子,個(gè)人覺得非常形象,大家看一下:
遞歸最恰當(dāng)?shù)谋扔鳎褪遣樵~典。我們使用的詞典,本身就是遞歸,為了解釋一個(gè)詞,需要使用更多的詞。當(dāng)你查一個(gè)詞,發(fā)現(xiàn)這個(gè)詞的解釋中某個(gè)詞仍然不懂,于是你開始查這第二個(gè)詞,可惜,第二個(gè)詞里仍然有不懂的詞,于是查第三個(gè)詞,這樣查下去,直到有一個(gè)詞的解釋是你完全能看懂的,那么遞歸走到了盡頭,然后你開始后退,逐個(gè)明白之前查過的每一個(gè)詞,最終,你明白了最開始那個(gè)詞的意思。
來試試水,看一個(gè)遞歸的代碼例子吧,如下:
public?int?sum(int?n)?{
????if?(n?<=?1)?{
????????return?1;
????}?
????return?sum(n?-?1)?+?n;?
}
遞歸的特點(diǎn)
實(shí)際上,遞歸有兩個(gè)顯著的特征,終止條件和自身調(diào)用:
-
自身調(diào)用:原問題可以分解為子問題,子問題和原問題的求解方法是一致的,即都是調(diào)用自身的同一個(gè)函數(shù)。 -
終止條件:遞歸必須有一個(gè)終止的條件,即不能無限循環(huán)地調(diào)用本身。
結(jié)合以上demo代碼例子,看下遞歸的特點(diǎn):
遞歸與棧的關(guān)系
其實(shí),遞歸的過程,可以理解為出入棧的過程的,這個(gè)比喻呢,只是為了方便讀者朋友更好理解遞歸哈。以上代碼例子計(jì)算sum(n=3)的出入棧圖如下:
為了更容易理解一些,我們來看一下 函數(shù)sum(n=5)的遞歸執(zhí)行過程,如下:
-
計(jì)算sum(5)時(shí),先sum(5)入棧,然后原問題sum(5)拆分為子問題sum(4),再入棧,直到終止條件sum(n=1)=1,就開始出棧。 -
sum(1)出棧后,sum(2)開始出棧,接著sum(3)。 -
最后呢,sum(1)就是后進(jìn)先出,sum(5)是先進(jìn)后出,因此遞歸過程可以理解為棧出入過程啦~
遞歸的經(jīng)典應(yīng)用場景
哪些問題我們可以考慮使用遞歸來解決呢?即遞歸的應(yīng)用場景一般有哪些呢?
-
階乘問題 -
二叉樹深度 -
漢諾塔問題 -
斐波那契數(shù)列 -
快速排序、歸并排序(分治算法體現(xiàn)遞歸) -
遍歷文件,解析xml文件
遞歸解題思路
解決遞歸問題一般就三步曲,分別是:
-
第一步,定義函數(shù)功能 -
第二步,尋找遞歸終止條件 -
第二步,遞推函數(shù)的等價(jià)關(guān)系式
這個(gè)遞歸解題三板斧理解起來有點(diǎn)抽象,我們拿階乘遞歸例子來喵喵吧~
1.定義函數(shù)功能
定義函數(shù)功能,就是說,你這個(gè)函數(shù)是干嘛的,做什么事情,換句話說,你要知道遞歸原問題是什么呀?比如你需要解決階乘問題,定義的函數(shù)功能就是n的階乘,如下:
//n的階乘(n為大于0的自然數(shù))
int?factorial?(int?n){
}
2.尋找遞歸終止條件
遞歸的一個(gè)典型特征就是必須有一個(gè)終止的條件,即不能無限循環(huán)地調(diào)用本身。所以,用遞歸思路去解決問題的時(shí)候,就需要尋找遞歸終止條件是什么。比如階乘問題,當(dāng)n=1的時(shí)候,不用再往下遞歸了,可以跳出循環(huán)啦,n=1就可以作為遞歸的終止條件,如下:
//n的階乘(n為大于0的自然數(shù))
int?factorial?(int?n){
????if(n==1){
??????return?1;
????}
}
3.遞推函數(shù)的等價(jià)關(guān)系式
遞歸的「本義」,就是原問題可以拆為同類且更容易解決的子問題,即「原問題和子問題都可以用同一個(gè)函數(shù)關(guān)系表示。遞推函數(shù)的等價(jià)關(guān)系式,這個(gè)步驟就等價(jià)于尋找原問題與子問題的關(guān)系,如何用一個(gè)公式把這個(gè)函數(shù)表達(dá)清楚」。階乘的公式就可以表示為 f(n) = n * f(n-1), 因此,階乘的遞歸程序代碼就可以寫成這樣,如下:
int?factorial?(int?n){
????if(n==1){
??????return?1;
????}
????return?n?*?factorial(n-1);
}
「注意啦」,不是所有遞推函數(shù)的等價(jià)關(guān)系都像階乘這么簡單,一下子就能推導(dǎo)出來。需要我們多接觸,多積累,多思考,多練習(xí)遞歸題目滴~
leetcode案例分析
來分析一道leetcode遞歸的經(jīng)典題目吧~
原題鏈接在這里哈:https://leetcode-cn.com/problems/invert-binary-tree/
「題目:」 翻轉(zhuǎn)一棵二叉樹。
輸入:
?????4
???/???\
??2?????7
?/?\???/?\
1???3?6???9
輸出:
?????4
???/???\
??7?????2
?/?\???/?\
9???6?3???1
我們按照以上遞歸解題的三板斧來:
「1. 定義函數(shù)功能」
函數(shù)功能(即這個(gè)遞歸原問題是),給出一顆樹,然后翻轉(zhuǎn)它,所以,函數(shù)可以定義為:
//翻轉(zhuǎn)一顆二叉樹
public?TreeNode?invertTree(TreeNode?root)?{
}
/**
?*?Definition?for?a?binary?tree?node.
?*?public?class?TreeNode?{
?*?????int?val;
?*?????TreeNode?left;
?*?????TreeNode?right;
?*?????TreeNode(int?x)?{?val?=?x;?}
?*?}
?*/
「2.尋找遞歸終止條件」
這棵樹什么時(shí)候不用翻轉(zhuǎn)呢?當(dāng)然是當(dāng)前節(jié)點(diǎn)為null或者當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)的時(shí)候啦。因此,加上終止條件就是:
//翻轉(zhuǎn)一顆二叉樹
public?TreeNode?invertTree(TreeNode?root)?{
????if(root==null?||?(root.left?==null?&&?root.right?==null)){
???????return?root;
????}
}
「3. 遞推函數(shù)的等價(jià)關(guān)系式」
原問題之你要翻轉(zhuǎn)一顆樹,是不是可以拆分為子問題,分別翻轉(zhuǎn)它的左子樹和右子樹?子問題之翻轉(zhuǎn)它的左子樹,是不是又可以拆分為,翻轉(zhuǎn)它左子樹的左子樹以及它左子樹的右子樹?然后一直翻轉(zhuǎn)到葉子節(jié)點(diǎn)為止。嗯,看圖理解一下咯~
首先,你要翻轉(zhuǎn)根節(jié)點(diǎn)為4的樹,就需要「翻轉(zhuǎn)它的左子樹(根節(jié)點(diǎn)為2)和右子樹(根節(jié)點(diǎn)為7)」。這就是遞歸的「遞」的過程啦
然后呢,根節(jié)點(diǎn)為2的樹,不是葉子節(jié)點(diǎn),你需要繼續(xù)「翻轉(zhuǎn)它的左子樹(根節(jié)點(diǎn)為1)和右子樹(根節(jié)點(diǎn)為3)」。因?yàn)楣?jié)點(diǎn)1和3都是「葉子節(jié)點(diǎn)」了,所以就返回啦。這也是遞歸的「遞」的過程~
同理,根節(jié)點(diǎn)為7的樹,也不是葉子節(jié)點(diǎn),你需要翻轉(zhuǎn)「它的左子樹(根節(jié)點(diǎn)為6)和右子樹(根節(jié)點(diǎn)為9)」。因?yàn)楣?jié)點(diǎn)6和9都是葉子節(jié)點(diǎn)了,所以也返回啦。
左子樹(根節(jié)點(diǎn)為2)和右子樹(根節(jié)點(diǎn)為7)都被翻轉(zhuǎn)完后,這幾個(gè)步驟就「歸來」,即遞歸的歸過程,翻轉(zhuǎn)樹的任務(wù)就完成了~
顯然,「遞推關(guān)系式」就是:
invertTree(root)=?invertTree(root.left)?+?invertTree(root.right);
于是,很容易可以得出以下代碼:
//翻轉(zhuǎn)一顆二叉樹
public?TreeNode?invertTree(TreeNode?root)?{
????if(root==null?||?(root.left?==null?&&?root.right?==null){
???????return?root;
????}
????//翻轉(zhuǎn)左子樹
????TreeNode?left?=?invertTree(root.left);
????//翻轉(zhuǎn)右子樹
????TreeNode?right=?invertTree(root.right);
}
這里代碼有個(gè)地方需要注意,翻轉(zhuǎn)完一棵樹的左右子樹,還要交換它左右子樹的引用位置。
?root.left?=?right;
?root.right?=?left;
因此,leetcode這個(gè)遞歸經(jīng)典題目的「終極解決代碼」如下:
class?Solution?{
????public?TreeNode?invertTree(TreeNode?root)?{
?????????if(root==null?||?(root.left?==null?&&?root.right?==null)){
???????????return?root;
?????????}
?????????//翻轉(zhuǎn)左子樹
?????????TreeNode?left?=?invertTree(root.left);
?????????//翻轉(zhuǎn)右子樹
?????????TreeNode?right=?invertTree(root.right);
?????????//左右子樹交換位置~
?????????root.left?=?right;
?????????root.right?=?left;
?????????return?root;
????}
}
拿終極解決代碼去leetcode提交一下,通過啦~
遞歸存在的問題
-
遞歸調(diào)用層級太多,導(dǎo)致棧溢出問題 -
遞歸重復(fù)計(jì)算,導(dǎo)致效率低下
棧溢出問題
-
每一次函數(shù)調(diào)用在內(nèi)存棧中分配空間,而每個(gè)進(jìn)程的棧容量是有限的。 -
當(dāng)遞歸調(diào)用的層級太多時(shí),就會超出棧的容量,從而導(dǎo)致調(diào)用棧溢出。 -
其實(shí),我們在前面小節(jié)也討論了,遞歸過程類似于出棧入棧,如果遞歸次數(shù)過多,棧的深度就需要越深,最后棧容量真的不夠咯
「代碼例子如下:」
/**
?*?遞歸棧溢出測試
?*/
public?class?RecursionTest?{
????public?static?void?main(String[]?args)?{
????????sum(50000);
????}
????private?static?int?sum(int?n)?{
????????if?(n?<=?1)?{
????????????return?1;
????????}
????????return?sum(n?-?1)?+?n;
????}
}
「運(yùn)行結(jié)果:」
Exception?in?thread?"main"?java.lang.StackOverflowError
?at?recursion.RecursionTest.sum(RecursionTest.java:13)
怎么解決這個(gè)棧溢出問題?首先需要「優(yōu)化一下你的遞歸」,真的需要遞歸調(diào)用這么多次嘛?如果真的需要,先稍微「調(diào)大JVM的??臻g內(nèi)存」,如果還是不行,那就需要棄用遞歸,「優(yōu)化為其他方案」咯~
重復(fù)計(jì)算,導(dǎo)致程序效率低下
我們再來看一道經(jīng)典的青蛙跳階問題:一只青蛙一次可以跳上1級臺階,也可以跳上2級臺階。求該青蛙跳上一個(gè) n 級的臺階總共有多少種跳法。
絕大多數(shù)讀者朋友,很容易就想到以下遞歸代碼去解決:
class?Solution?{
????public?int?numWays(int?n)?{
????if?(n?==?0){
???????return?1;
?????}
????if(n?<=?2){
????????return?n;
????}
????return?numWays(n-1)?+?numWays(n-2);
????}
}
但是呢,去leetcode提交一下,就有問題啦,超出時(shí)間限制了
為什么超時(shí)了呢?遞歸耗時(shí)在哪里呢?先畫出「遞歸樹」看看:
-
要計(jì)算原問題 f(10),就需要先計(jì)算出子問題 f(9) 和 f(8) -
然后要計(jì)算 f(9),又要先算出子問題 f(8) 和 f(7),以此類推。 -
一直到 f(2) 和 f(1),遞歸樹才終止。
我們先來看看這個(gè)遞歸的時(shí)間復(fù)雜度吧,「遞歸時(shí)間復(fù)雜度 = 解決一個(gè)子問題時(shí)間*子問題個(gè)數(shù)」
-
一個(gè)子問題時(shí)間 = ?f(n-1)+f(n-2),也就是一個(gè)加法的操作,所以復(fù)雜度是 「O(1)」; -
問題個(gè)數(shù) = 遞歸樹節(jié)點(diǎn)的總數(shù),遞歸樹的總結(jié)點(diǎn) = 2^n-1,所以是復(fù)雜度 「O(2^n)」。
因此,青蛙跳階,遞歸解法的時(shí)間復(fù)雜度 = O(1) * O(2^n) = ?O(2^n),就是指數(shù)級別的,爆炸增長的,「如果n比較大的話,超時(shí)很正常的了」。
回過頭來,你仔細(xì)觀察這顆遞歸樹,你會發(fā)現(xiàn)存在「大量重復(fù)計(jì)算」,比如f(8)被計(jì)算了兩次,f(7)被重復(fù)計(jì)算了3次...所以這個(gè)遞歸算法低效的原因,就是存在大量的重復(fù)計(jì)算!
「那么,怎么解決這個(gè)問題呢?」
既然存在大量重復(fù)計(jì)算,那么我們可以先把計(jì)算好的答案存下來,即造一個(gè)備忘錄,等到下次需要的話,先去「備忘錄」查一下,如果有,就直接取就好了,備忘錄沒有才再計(jì)算,那就可以省去重新重復(fù)計(jì)算的耗時(shí)啦!這就是「帶備忘錄的解法」
我們來看一下「帶備忘錄的遞歸解法」吧~
一般使用一個(gè)數(shù)組或者一個(gè)哈希map充當(dāng)這個(gè)「備忘錄」。
假設(shè)f(10)求解加上「備忘錄」,我們再來畫一下遞歸樹:
「第一步」,f(10)= f(9) + f(8),f(9) 和f(8)都需要計(jì)算出來,然后再加到備忘錄中,如下:
「第二步,」 ?f(9) = f(8)+ f(7),f(8)= f(7)+ f(6), 因?yàn)?f(8) 已經(jīng)在備忘錄中啦,所以可以省掉,f(7),f(6)都需要計(jì)算出來,加到備忘錄中~
「第三步,」 f(8) = f(7)+ f(6),發(fā)現(xiàn)f(8),f(7),f(6)全部都在備忘錄上了,所以都可以剪掉。
所以呢,用了備忘錄遞歸算法,遞歸樹變成光禿禿的樹干咯,如下:
帶「備忘錄」的遞歸算法,子問題個(gè)數(shù)=樹節(jié)點(diǎn)數(shù)=n,解決一個(gè)子問題還是O(1),所以「帶「備忘錄」的遞歸算法的時(shí)間復(fù)雜度是O(n)」。接下來呢,我們用帶「備忘錄」的遞歸算法去擼代碼,解決這個(gè)青蛙跳階問題的超時(shí)問題咯~,代碼如下:
public?class?Solution?{
????//使用哈希map,充當(dāng)備忘錄的作用
????Map?tempMap?=?new?HashMap();
????public?int?numWays(int?n)?{
????????//?n?=?0?也算1種
????????if?(n?==?0)?{
????????????return?1;
????????}
????????if?(n?<=?2)?{
????????????return?n;
????????}
????????//先判斷有沒計(jì)算過,即看看備忘錄有沒有
????????if?(tempMap.containsKey(n))?{
????????????//備忘錄有,即計(jì)算過,直接返回
????????????return?tempMap.get(n);
????????}?else?{
????????????//?備忘錄沒有,即沒有計(jì)算過,執(zhí)行遞歸計(jì)算,并且把結(jié)果保存到備忘錄map中,對1000000007取余(這個(gè)是leetcode題目規(guī)定的)
????????????tempMap.put(n,?(numWays(n?-?1)?+?numWays(n?-?2))?%?1000000007);
????????????return?tempMap.get(n);
????????}
????}
}
去leetcode提交一下,如圖,穩(wěn)了:
還有沒有其他方案解決這個(gè)問題呢?只有「帶備忘錄的遞歸解法」?其實(shí)吧,還可以用「動(dòng)態(tài)規(guī)劃」去解決
動(dòng)態(tài)規(guī)劃算法思想怎么解題呢?我們下期繼續(xù)~ 謝謝閱讀~
參考與感謝
-
[一文學(xué)會遞歸解題] (https://mp.weixin.qq.com/s/Hew44D8rdXb3pf8mZGk67w) -
[動(dòng)態(tài)規(guī)劃詳解] (https://mp.weixin.qq.com/s/1V3aHVonWBEXlNUvK3S28w)
免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺僅提供信息存儲服務(wù)。文章僅代表作者個(gè)人觀點(diǎn),不代表本平臺立場,如有問題,請聯(lián)系我們,謝謝!