[[346111]]

前言

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

• 什么是遞歸?
• 遞歸的特點
• 遞歸與棧的關系
• 遞歸應用場景
• 遞歸解題思路
• leetcode案例分析
• 遞歸可能存在的問題以及解決方案

什么是遞歸?

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

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

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

public int sum(int n) { 
    if (n <= 1) { 
        return 1; 
    }  
    return sum(n - 1) + n;  
} 

遞歸的特點

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

• 自身調用：原問題可以分解為子問題，子問題和原問題的求解方法是一致的，即都是調用自身的同一個函數。
• 終止條件：遞歸必須有一個終止的條件，即不能無限循環地調用本身。

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

 

遞歸與棧的關系

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

 

 

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

 

• 計算sum(5)時，先sum(5)入棧，然后原問題sum(5)拆分為子問題sum(4)，再入棧，直到終止條件sum(n=1)=1，就開始出棧。
• sum(1)出棧后，sum(2)開始出棧，接著sum(3)。
• 最后呢,sum(1)就是后進先出，sum(5)是先進后出，因此遞歸過程可以理解為棧出入過程啦~

遞歸的經典應用場景

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

• 階乘問題
• 二叉樹深度
• 漢諾塔問題
• 斐波那契數列
• 快速排序、歸并排序(分治算法體現遞歸)
• 遍歷文件，解析xml文件

遞歸解題思路

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

• 第一步，定義函數功能
• 第二步，尋找遞歸終止條件
• 第二步，遞推函數的等價關系式

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

1.定義函數功能

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

//n的階乘（n為大于0的自然數） 
int factorial (int n){ 
 
} 

2.尋找遞歸終止條件

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

//n的階乘（n為大于0的自然數） 
int factorial (int n){ 
    if(n==1){ 
      return 1; 
    } 
} 

3.遞推函數的等價關系式

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

int factorial (int n){ 
    if(n==1){ 
      return 1; 
    } 
    return n * factorial(n-1); 
} 

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

leetcode案例分析

來分析一道leetcode遞歸的經典題目吧~

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

「題目：」 翻轉一棵二叉樹。

輸入：

  4 
   /   \ 
  2     7 
 / \   / \ 
1   3 6   9 

輸出：

     4 
   /   \ 
  7     2 
 / \   / \ 
9   6 3   1 

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

「1. 定義函數功能」

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

//翻轉一顆二叉樹 
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.尋找遞歸終止條件」

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

//翻轉一顆二叉樹 
public TreeNode invertTree(TreeNode root) { 
    if(root==null || (root.left ==null && root.right ==null)){ 
       return root; 
    } 
} 

「3. 遞推函數的等價關系式」

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

 

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

 

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

 

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

 

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

 

顯然，「遞推關系式」就是：

invertTree（root）= invertTree（root.left） + invertTree（root.right）; 

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

//翻轉一顆二叉樹 
public TreeNode invertTree(TreeNode root) { 
    if(root==null || (root.left ==null && root.right ==null){ 
       return root; 
    } 
    //翻轉左子樹 
    TreeNode left = invertTree(root.left); 
    //翻轉右子樹 
    TreeNode right= invertTree(root.right); 
} 

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

root.left = right; 
 root.right = left; 

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

class Solution { 
    public TreeNode invertTree(TreeNode root) { 
         if(root==null || (root.left ==null && root.right ==null)){ 
           return root; 
         } 
         //翻轉左子樹 
         TreeNode left = invertTree(root.left); 
         //翻轉右子樹 
         TreeNode right= invertTree(root.right); 
         //左右子樹交換位置~ 
         root.left = right; 
         root.right = left; 
         return root; 
    } 
} 

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

 

遞歸存在的問題

• 遞歸調用層級太多，導致棧溢出問題
• 遞歸重復計算，導致效率低下

棧溢出問題

• 每一次函數調用在內存棧中分配空間，而每個進程的棧容量是有限的。
• 當遞歸調用的層級太多時，就會超出棧的容量，從而導致調用棧溢出。
• 其實，我們在前面小節也討論了，遞歸過程類似于出棧入棧，如果遞歸次數過多，棧的深度就需要越深，最后棧容量真的不夠咯

「代碼例子如下：」

/** 
 * 遞歸棧溢出測試 
 */ 
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; 
    } 
} 

「運行結果:」

Exception in thread "main" java.lang.StackOverflowError at recursion.RecursionTest.sum(RecursionTest.java:13)

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

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

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

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

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提交一下，就有問題啦，超出時間限制了

 

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

 

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

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

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

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

• 一個子問題時間 = f(n-1)+f(n-2)，也就是一個加法的操作，所以復雜度是「O(1)」;
• 問題個數 = 遞歸樹節點的總數，遞歸樹的總結點 = 2^n-1，所以是復雜度「O(2^n)」。

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

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

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

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

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

一般使用一個數組或者一個哈希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) 已經在備忘錄中啦，所以可以省掉，f(7),f(6)都需要計算出來，加到備忘錄中~

 

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

 

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

 

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

public class Solution { 
    //使用哈希map，充當備忘錄的作用 
    Map<Integer, Integer> tempMap = new HashMap(); 
    public int numWays(int n) { 
        // n = 0 也算1種 
        if (n == 0) { 
            return 1; 
        } 
        if (n <= 2) { 
            return n; 
        } 
        //先判斷有沒計算過，即看看備忘錄有沒有 
        if (tempMap.containsKey(n)) { 
            //備忘錄有，即計算過，直接返回 
            return tempMap.get(n); 
        } else { 
            // 備忘錄沒有，即沒有計算過，執行遞歸計算,并且把結果保存到備忘錄map中，對1000000007取余（這個是leetcode題目規定的） 
            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007); 
            return tempMap.get(n); 
        } 
    } 
} 

去leetcode提交一下，如圖，穩了：

 

 

還有沒有其他方案解決這個問題呢?只有「帶備忘錄的遞歸解法」?其實吧，還可以用「動態規劃」去解決

本文轉載自微信公眾號「 撿田螺的小男孩」，可以通過以下二維碼關注。轉載本文請聯系 撿田螺的小男孩公眾號。