前言

遞歸是一種非常重要的算法思想，無論你是前端開發(fā)，還是后端開發(fā)，都需要掌握它。在日常工作中，統(tǒng)計文件夾大小，解析xml文件等等，都需要用到遞歸算法。它太基礎太重要了，這也是為什么面試的時候，面試官經(jīng)常讓我們手寫遞歸算法。本文呢，將跟大家一起學習遞歸算法~

什么是遞歸？

遞歸，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。簡單來說，遞歸表現(xiàn)為函數(shù)調(diào)用函數(shù)本身。在知乎看到一個比喻遞歸的例子，個人覺得非常形象，大家看一下：

?

遞歸最恰當?shù)谋扔?，就是查詞典。我們使用的詞典，本身就是遞歸，為了解釋一個詞，需要使用更多的詞。當你查一個詞，發(fā)現(xiàn)這個詞的解釋中某個詞仍然不懂，于是你開始查這第二個詞，可惜，第二個詞里仍然有不懂的詞，于是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那么遞歸走到了盡頭，然后你開始后退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。

?

來試試水，看一個遞歸的代碼例子吧，如下：

遞歸的特點

實際上，遞歸有兩個顯著的特征,終止條件和自身調(diào)用:

自身調(diào)用：原問題可以分解為子問題，子問題和原問題的求解方法是一致的，即都是調(diào)用自身的同一個函數(shù)。

終止條件：遞歸必須有一個終止的條件，即不能無限循環(huán)地調(diào)用本身。

結(jié)合以上demo代碼例子，看下遞歸的特點：

遞歸與棧的關系

其實，遞歸的過程，可以理解為出入棧的過程的，這個比喻呢，只是為了方便讀者朋友更好理解遞歸哈。以上代碼例子計算sum（n=3）的出入棧圖如下：

為了更容易理解一些，我們來看一下 函數(shù)sum（n=5）的遞歸執(zhí)行過程，如下：

計算sum（5）時，先sum（5）入棧，然后原問題sum（5）拆分為子問題sum（4），再入棧，直到終止條件sum（n=1）=1，就開始出棧。

sum（1）出棧后，sum（2）開始出棧，接著sum（3）。

最后呢,sum（1）就是后進先出，sum（5）是先進后出，因此遞歸過程可以理解為棧出入過程啦~

遞歸的經(jīng)典應用場景

哪些問題我們可以考慮使用遞歸來解決呢？即遞歸的應用場景一般有哪些呢？

階乘問題

二叉樹深度

漢諾塔問題

斐波那契數(shù)列

快速排序、歸并排序（分治算法也使用遞歸實現(xiàn)）

遍歷文件，解析xml文件

遞歸解題思路

解決遞歸問題一般就三步曲，分別是：

第一步，定義函數(shù)功能

第二步，尋找遞歸終止條件

第二步，遞推函數(shù)的等價關系式

這個遞歸解題三板斧理解起來有點抽象，我們拿階乘遞歸例子來喵喵吧~

1.定義函數(shù)功能

定義函數(shù)功能，就是說，你這個函數(shù)是干嘛的，做什么事情，換句話說，你要知道遞歸原問題是什么呀？比如你需要解決階乘問題，定義的函數(shù)功能就是n的階乘，如下：

2.尋找遞歸終止條件

遞歸的一個典型特征就是必須有一個終止的條件，即不能無限循環(huán)地調(diào)用本身。所以，用遞歸思路去解決問題的時候，就需要尋找遞歸終止條件是什么。比如階乘問題，當n=1的時候，不用再往下遞歸了，可以跳出循環(huán)啦，n=1就可以作為遞歸的終止條件，如下：

3.遞推函數(shù)的等價關系式

遞歸的?「本義」?，就是原問題可以拆為同類且更容易解決的子問題，即?「原問題和子問題都可以用同一個函數(shù)關系表示。遞推函數(shù)的等價關系式，這個步驟就等價于尋找原問題與子問題的關系，如何用一個公式把這個函數(shù)表達清楚」?。階乘的公式就可以表示為 f(n) = n * f(n-1), 因此，階乘的遞歸程序代碼就可以寫成這樣，如下：

「注意啦」?，不是所有遞推函數(shù)的等價關系都像階乘這么簡單，一下子就能推導出來。需要我們多接觸，多積累，多思考，多練習遞歸題目滴~

leetcode案例分析

來分析一道leetcode遞歸的經(jīng)典題目吧~

?

原題鏈接在這里哈：https://leetcode-cn.com/problems/invert-binary-tree/

?

「題目：」??翻轉(zhuǎn)一棵二叉樹。

輸入：

輸出：

照以上遞歸解題的三板斧來：

「1. 定義函數(shù)功能」

函數(shù)功能（即這個遞歸原問題是），給出一顆樹，然后翻轉(zhuǎn)它，所以，函數(shù)可以定義為：

「2.尋找遞歸終止條件」

這棵樹什么時候不用翻轉(zhuǎn)呢？當然是當前節(jié)點為null或者當前節(jié)點為葉子節(jié)點的時候啦。因此，加上終止條件就是：

「3. 遞推函數(shù)的等價關系式」

原問題之你要翻轉(zhuǎn)一顆樹，是不是可以拆分為子問題，分別翻轉(zhuǎn)它的左子樹和右子樹？子問題之翻轉(zhuǎn)它的左子樹，是不是又可以拆分為，翻轉(zhuǎn)它左子樹的左子樹以及它左子樹的右子樹？然后一直翻轉(zhuǎn)到葉子節(jié)點為止。嗯，看圖理解一下咯~

首先，你要翻轉(zhuǎn)根節(jié)點為4的樹，就需要?「翻轉(zhuǎn)它的左子樹（根節(jié)點為2）和右子樹(根節(jié)點為7）」?。這就是遞歸的?「遞」?的過程啦

然后呢，根節(jié)點為2的樹，不是葉子節(jié)點，你需要繼續(xù)?「翻轉(zhuǎn)它的左子樹（根節(jié)點為1）和右子樹（根節(jié)點為3）」?。因為節(jié)點1和3都是?「葉子節(jié)點」?了，所以就返回啦。這也是遞歸的「遞」?的過程~

同理，根節(jié)點為7的樹，也不是葉子節(jié)點，你需要翻轉(zhuǎn)?「它的左子樹（根節(jié)點為6）和右子樹（根節(jié)點為9）」?。因為節(jié)點6和9都是葉子節(jié)點了，所以也返回啦。

左子樹（根節(jié)點為2）和右子樹(根節(jié)點為7）都被翻轉(zhuǎn)完后，這幾個步驟就?「歸來」?，即遞歸的歸過程，翻轉(zhuǎn)樹的任務就完成了~

顯然，?「遞推關系式」?就是：invertTree（root）=?invertTree（root.left）?+?invertTree（root.right）;

于是，很容易可以得出以下代碼：

這里代碼有個地方需要注意，翻轉(zhuǎn)完一棵樹的左右子樹，還要交換它左右子樹的引用位置。

root.left=right;?

root.right=left;

因此，leetcode這個遞歸經(jīng)典題目的?「終極解決代碼」?如下：

拿終極解決代碼去leetcode提交一下，通過啦~

遞歸存在的問題

遞歸調(diào)用層級太多，導致棧溢出問題

遞歸重復計算，導致效率低下

棧溢出問題

每一次函數(shù)調(diào)用在內(nèi)存棧中分配空間，而每個進程的棧容量是有限的。

當遞歸調(diào)用的層級太多時，就會超出棧的容量，從而導致調(diào)用棧溢出。

其實，我們在前面小節(jié)也討論了，遞歸過程類似于出棧入棧，如果遞歸次數(shù)過多，棧的深度就需要越深，最后棧容量真的不夠咯

「代碼例子如下：」

怎么解決這個棧溢出問題？首先需要?「優(yōu)化一下你的遞歸」?，真的需要遞歸調(diào)用這么多次嘛？如果真的需要，先稍微?「調(diào)大JVM的?？臻g內(nèi)存」?，如果還是不行，那就需要棄用遞歸，?「優(yōu)化為其他方案」?咯~

重復計算，導致程序效率低下

我們再來看一道經(jīng)典的青蛙跳階問題：一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。

絕大多數(shù)讀者朋友，很容易就想到以下遞歸代碼去解決：

但是呢，去leetcode提交一下，就有問題啦，超出時間限制了！

為什么超時了呢？遞歸耗時在哪里呢？先畫出?「遞歸樹」?看看：

要計算原問題 f(10)，就需要先計算出子問題 f(9) 和 f(8)

然后要計算 f(9)，又要先算出子問題 f(8) 和 f(7)，以此類推。

一直到 f(2) 和 f(1），遞歸樹才終止。

我們先來看看這個遞歸的時間復雜度吧，?「遞歸時間復雜度 = 解決一個子問題時間*子問題個數(shù)」

一個子問題時間 = f（n-1）+f（n-2），也就是一個加法的操作，所以復雜度是??「O(1)」?；

問題個數(shù) = 遞歸樹節(jié)點的總數(shù)，遞歸樹的總結(jié)點 = 2^n-1，所以是復雜度?「O(2^n)」?。

因此，青蛙跳階，遞歸解法的時間復雜度 = O(1) * O(2^n) = O(2^n)，就是指數(shù)級別的，爆炸增長的，?「如果n比較大的話，超時很正常的了」?。

回過頭來，你仔細觀察這顆遞歸樹，你會發(fā)現(xiàn)存在?「大量重復計算」?，比如f（8）被計算了兩次，f（7）被重復計算了3次...所以這個遞歸算法低效的原因，就是存在大量的重復計算！

「那么，怎么解決這個問題呢？」

既然存在大量重復計算，那么我們可以先把計算好的答案存下來，即造一個備忘錄，等到下次需要的話，先去?「備忘錄」?查一下，如果有，就直接取就好了，備忘錄沒有才再計算，那就可以省去重新重復計算的耗時啦！這就是?「帶備忘錄的解法」

我們來看一下?「帶備忘錄的遞歸解法」?吧~

一般使用一個數(shù)組或者一個哈希map充當這個?「備忘錄」?。

假設f(10)求解加上?「備忘錄」?，我們再來畫一下遞歸樹：

「第一步」?，f（10）= f(9) + f(8)，f(9) 和f（8）都需要計算出來，然后再加到備忘錄中，如下：

「第二步，」??f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因為 f(8) 已經(jīng)在備忘錄中啦，所以可以省掉，f(7),f（6）都需要計算出來，加到備忘錄中~

「第三步，」??f(8) = f（7）+ f(6),發(fā)現(xiàn)f(8)，f(7),f（6）全部都在備忘錄上了，所以都可以剪掉。

所以呢，用了備忘錄遞歸算法，遞歸樹變成光禿禿的樹干咯，如下：

帶「備忘錄」的遞歸算法，子問題個數(shù)=樹節(jié)點數(shù)=n，解決一個子問題還是O(1),所以?「帶「備忘錄」的遞歸算法的時間復雜度是O(n)」?。接下來呢，我們用帶「備忘錄」的遞歸算法去擼代碼，解決這個青蛙跳階問題的超時問題咯~，代碼如下：

寫在最后

既然你們能看到這里說明這篇文章對你們的幫助還是有的，筆者可不可以給你們索要一個小小的贊呢。當然啦，筆者其實是一位C/C++的程序員哦~每天分享的更多的當然是C語言C++的知識，不過今天看到這一篇Java程序員分享的算法知識還是很不錯的，所以分享給大家。

原文鏈接：https://xie.infoq.cn/article/0d1cf877d9e0b31a16cd76486?utm_source=tuicool&utm_medium=referral

另外如果你想更好的提升你的編程能力，學好C語言C++編程！彎道超車，快人一步！

分享（源碼、項目實戰(zhàn)視頻、項目筆記，基礎入門教程）

歡迎轉(zhuǎn)行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！

學習C/C++編程知識，提升C/C++編程能力，歡迎關注UP一起來成長！
另外，UP在主頁上傳了一些學習C/C++編程的視頻教程，有興趣或者正在學習的小伙伴一定要去看一看哦！會對你有幫助的~