程序員必備的基本算法：遞歸詳解
前言
遞歸是一種非常重要的算法思想，無(wú)論你是前端開發(fā)，還是后端開發(fā)，都需要掌握它。在日常工作中，統(tǒng)計(jì)文件夾大小，解析xml文件等等，都需要用到遞歸算法。它太基礎(chǔ)太重要了，這也是為什么面試的時(shí)候，面試官經(jīng)常讓我們手寫遞歸算法。本文呢，將跟大家一起學(xué)習(xí)遞歸算法~
- 什么是遞歸?
- 遞歸的特點(diǎn)
- 遞歸與棧的關(guān)系
- 遞歸應(yīng)用場(chǎng)景
- 遞歸解題思路
- leetcode案例分析
- 遞歸可能存在的問(wèn)題以及解決方案
什么是遞歸?
遞歸，在計(jì)算機(jī)科學(xué)中是指一種通過(guò)重復(fù)將問(wèn)題分解為同類的子問(wèn)題而解決問(wèn)題的方法。簡(jiǎn)單來(lái)說(shuō)，遞歸表現(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è)明白之前查過(guò)的每一個(gè)詞，最終，你明白了最開始那個(gè)詞的意思。❞
來(lái)試試水，看一個(gè)遞歸的代碼例子吧，如下：
- public int sum(int n) {
- if (n <= 1) {
- return 1;
- }
- return sum(n - 1) + n;
- }
遞歸的特點(diǎn)
實(shí)際上，遞歸有兩個(gè)顯著的特征,終止條件和自身調(diào)用:
- 自身調(diào)用：原問(wèn)題可以分解為子問(wèn)題，子問(wèn)題和原問(wèn)題的求解方法是一致的，即都是調(diào)用自身的同一個(gè)函數(shù)。
- 終止條件：遞歸必須有一個(gè)終止的條件，即不能無(wú)限循環(huán)地調(diào)用本身。
結(jié)合以上demo代碼例子，看下遞歸的特點(diǎn)：
遞歸與棧的關(guān)系
其實(shí)，遞歸的過(guò)程，可以理解為出入棧的過(guò)程的，這個(gè)比喻呢，只是為了方便讀者朋友更好理解遞歸哈。以上代碼例子計(jì)算sum(n=3)的出入棧圖如下：
為了更容易理解一些，我們來(lái)看一下 函數(shù)sum(n=5)的遞歸執(zhí)行過(guò)程，如下：
- 計(jì)算sum(5)時(shí)，先sum(5)入棧，然后原問(wèn)題sum(5)拆分為子問(wèn)題sum(4)，再入棧，直到終止條件sum(n=1)=1，就開始出棧。
- sum(1)出棧后，sum(2)開始出棧，接著sum(3)。
- 最后呢,sum(1)就是后進(jìn)先出，sum(5)是先進(jìn)后出，因此遞歸過(guò)程可以理解為棧出入過(guò)程啦~
遞歸的經(jīng)典應(yīng)用場(chǎng)景
哪些問(wèn)題我們可以考慮使用遞歸來(lái)解決呢?即遞歸的應(yīng)用場(chǎng)景一般有哪些呢?
- 階乘問(wèn)題
- 二叉樹深度
- 漢諾塔問(wèn)題
- 斐波那契數(shù)列
- 快速排序、歸并排序(分治算法體現(xiàn)遞歸)
- 遍歷文件，解析xml文件
遞歸解題思路
解決遞歸問(wèn)題一般就三步曲，分別是：
- 第一步，定義函數(shù)功能
- 第二步，尋找遞歸終止條件
- 第二步，遞推函數(shù)的等價(jià)關(guān)系式
這個(gè)遞歸解題三板斧理解起來(lái)有點(diǎn)抽象，我們拿階乘遞歸例子來(lái)喵喵吧~
1.定義函數(shù)功能
定義函數(shù)功能，就是說(shuō)，你這個(gè)函數(shù)是干嘛的，做什么事情，換句話說(shuō)，你要知道遞歸原問(wèn)題是什么呀?比如你需要解決階乘問(wèn)題，定義的函數(shù)功能就是n的階乘，如下：
- //n的階乘（n為大于0的自然數(shù)）
- int factorial (int n){
- }
2.尋找遞歸終止條件
遞歸的一個(gè)典型特征就是必須有一個(gè)終止的條件，即不能無(wú)限循環(huán)地調(diào)用本身。所以，用遞歸思路去解決問(wèn)題的時(shí)候，就需要尋找遞歸終止條件是什么。比如階乘問(wèn)題，當(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)系式
遞歸的「本義」，就是原問(wèn)題可以拆為同類且更容易解決的子問(wèn)題，即「原問(wèn)題和子問(wèn)題都可以用同一個(gè)函數(shù)關(guān)系表示。遞推函數(shù)的等價(jià)關(guān)系式，這個(gè)步驟就等價(jià)于尋找原問(wèn)題與子問(wèn)題的關(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)系都像階乘這么簡(jiǎn)單，一下子就能推導(dǎo)出來(lái)。需要我們多接觸，多積累，多思考，多練習(xí)遞歸題目滴~
leetcode案例分析
來(lái)分析一道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
我們按照以上遞歸解題的三板斧來(lái)：
「1. 定義函數(shù)功能」
函數(shù)功能(即這個(gè)遞歸原問(wèn)題是)，給出一顆樹，然后翻轉(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)系式」
原問(wèn)題之你要翻轉(zhuǎn)一顆樹，是不是可以拆分為子問(wèn)題，分別翻轉(zhuǎn)它的左子樹和右子樹?子問(wè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)」。這就是遞歸的「遞」的過(guò)程啦
然后呢，根節(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)」了，所以就返回啦。這也是遞歸的「遞」的過(guò)程~
同理，根節(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è)步驟就「歸來(lái)」，即遞歸的歸過(guò)程，翻轉(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提交一下，通過(guò)啦~
遞歸存在的問(wèn)題
- 遞歸調(diào)用層級(jí)太多，導(dǎo)致棧溢出問(wèn)題
- 遞歸重復(fù)計(jì)算，導(dǎo)致效率低下
棧溢出問(wèn)題
- 每一次函數(shù)調(diào)用在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧容量是有限的。
- 當(dāng)遞歸調(diào)用的層級(jí)太多時(shí)，就會(huì)超出棧的容量，從而導(dǎo)致調(diào)用棧溢出。
- 其實(shí)，我們?cè)谇懊嫘」?jié)也討論了，遞歸過(guò)程類似于出棧入棧，如果遞歸次數(shù)過(guò)多，棧的深度就需要越深，最后棧容量真的不夠咯
「代碼例子如下：」
- /**
- * 遞歸棧溢出測(cè)試
- */
- 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è)棧溢出問(wèn)題?首先需要「優(yōu)化一下你的遞歸」，真的需要遞歸調(diào)用這么多次嘛?如果真的需要，先稍微「調(diào)大JVM的?？臻g內(nèi)存」，如果還是不行，那就需要棄用遞歸，「優(yōu)化為其他方案」咯~
重復(fù)計(jì)算，導(dǎo)致程序效率低下
我們?cè)賮?lái)看一道經(jīng)典的青蛙跳階問(wèn)題：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
絕大多數(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提交一下，就有問(wèn)題啦，超出時(shí)間限制了
為什么超時(shí)了呢?遞歸耗時(shí)在哪里呢?先畫出「遞歸樹」看看：
要計(jì)算原問(wèn)題 f(10)，就需要先計(jì)算出子問(wèn)題 f(9) 和 f(8)
然后要計(jì)算 f(9)，又要先算出子問(wèn)題 f(8) 和 f(7)，以此類推。
一直到 f(2) 和 f(1)，遞歸樹才終止。
我們先來(lái)看看這個(gè)遞歸的時(shí)間復(fù)雜度吧，「遞歸時(shí)間復(fù)雜度 = 解決一個(gè)子問(wèn)題時(shí)間*子問(wèn)題個(gè)數(shù)」
- 一個(gè)子問(wèn)題時(shí)間 = f(n-1)+f(n-2)，也就是一個(gè)加法的操作，所以復(fù)雜度是「O(1)」;
- 問(wèn)題個(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ù)級(jí)別的，爆炸增長(zhǎng)的，「如果n比較大的話，超時(shí)很正常的了」。
回過(guò)頭來(lái)，你仔細(xì)觀察這顆遞歸樹，你會(huì)發(fā)現(xiàn)存在「大量重復(fù)計(jì)算」，比如f(8)被計(jì)算了兩次，f(7)被重復(fù)計(jì)算了3次...所以這個(gè)遞歸算法低效的原因，就是存在大量的重復(fù)計(jì)算!
「那么，怎么解決這個(gè)問(wèn)題呢?」
既然存在大量重復(fù)計(jì)算，那么我們可以先把計(jì)算好的答案存下來(lái)，即造一個(gè)備忘錄，等到下次需要的話，先去「?jìng)渫洝共橐幌拢绻?，就直接取就好了，備忘錄沒有才再計(jì)算，那就可以省去重新重復(fù)計(jì)算的耗時(shí)啦!這就是「帶備忘錄的解法」
我們來(lái)看一下「帶備忘錄的遞歸解法」吧~
一般使用一個(gè)數(shù)組或者一個(gè)哈希map充當(dāng)這個(gè)「?jìng)渫洝埂?/p>
假設(shè)f(10)求解加上「?jìng)渫洝梗覀冊(cè)賮?lái)畫一下遞歸樹：
「第一步」，f(10)= f(9) + f(8)，f(9) 和f(8)都需要計(jì)算出來(lái)，然后再加到備忘錄中，如下：
「第二步，」 f(9) = f(8)+ f(7)，f(8)= f(7)+ f(6), 因?yàn)?f(8) 已經(jīng)在備忘錄中啦，所以可以省掉，f(7),f(6)都需要計(jì)算出來(lái)，加到備忘錄中~
「第三步，」 f(8) = f(7)+ f(6),發(fā)現(xiàn)f(8)，f(7),f(6)全部都在備忘錄上了，所以都可以剪掉。
所以呢，用了備忘錄遞歸算法，遞歸樹變成光禿禿的樹干咯，如下：
帶「?jìng)渫洝沟倪f歸算法，子問(wèn)題個(gè)數(shù)=樹節(jié)點(diǎn)數(shù)=n，解決一個(gè)子問(wèn)題還是O(1),所以「帶「?jìng)渫洝沟倪f歸算法的時(shí)間復(fù)雜度是O(n)」。接下來(lái)呢，我們用帶「?jìng)渫洝沟倪f歸算法去擼代碼，解決這個(gè)青蛙跳階問(wèn)題的超時(shí)問(wèn)題咯~，代碼如下：
- public class Solution {
- //使用哈希map，充當(dāng)備忘錄的作用
- Map<Integer, Integer> tempMap = new HashMap();
- public int numWays(int n) {
- // n = 0 也算1種
- if (n == 0) {
- return 1;
- }
- if (n <= 2) {
- return n;
- }
- //先判斷有沒計(jì)算過(guò)，即看看備忘錄有沒有
- if (tempMap.containsKey(n)) {
- //備忘錄有，即計(jì)算過(guò)，直接返回
- return tempMap.get(n);
- } else {
- // 備忘錄沒有，即沒有計(jì)算過(guò)，執(zhí)行遞歸計(jì)算,并且把結(jié)果保存到備忘錄map中，對(duì)1000000007取余（這個(gè)是leetcode題目規(guī)定的）
- tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
- return tempMap.get(n);
- }
- }
- }
去leetcode提交一下，如圖，穩(wěn)了：
還有沒有其他方案解決這個(gè)問(wèn)題呢?只有「帶備忘錄的遞歸解法」?其實(shí)吧，還可以用「動(dòng)態(tài)規(guī)劃」去解決
本文轉(zhuǎn)載自微信公眾號(hào)「 撿田螺的小男孩」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系 撿田螺的小男孩公眾號(hào)。
