遞歸算法實戰(zhàn)

本節(jié)將會以 3 個有意思的 leetcode 編程題來實踐遞歸算法，幫助大家更加深刻理解和掌握遞歸算法。

1. 常規(guī)的遞歸算法

這道題是 leetcode 的第 70 題，題目名稱為爬樓梯。題目內(nèi)容如下：

假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個正整數(shù)。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1.  1 階 + 1 階
2.  2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階

使用前面的遞歸三套件來解答這個基礎(chǔ)的遞歸問題，即函數(shù) f(n) 為 n 階樓梯的爬樓總方法數(shù)，則有：

終止條件：很明顯，當樓梯階數(shù)為 1 時，我們知道答案肯定為 1，即 f(1) = 1；此外 n = 2時，也知 f(2) = 2；

遞歸公式：遞歸指的是用前面計算出來的 f(n-1), f(n-2)，~，f(1) 等等的值遞推得到 f(n)。

這里思考下，首先我們的臺階往上減一級，即到達 n-1 級臺階的方法一共有 f(n-1) 種，然后只能跨 1 級到達第 n 級臺階，這是一種爬到樓頂?shù)姆椒ǎ挥捎谖颐看慰梢耘?1 個或者 2 個臺階，那么另一種爬到樓頂?shù)姆椒ㄊ窃?n-2 級臺階，然后爬 2 級就到了樓頂，而到達 n-2 級臺階的方法正好有 f(n-2) 種。綜合得到遞推公式為：

f(n) = f(n-1) + f(n-2)

返回預定結(jié)果：每個函數(shù)返回的結(jié)果是爬到 n 級臺階樓頂?shù)目偡椒ā?/p>

綜合這三步，我們就可以得到如下的函數(shù)：

def climb_stairs(n):
    # 終止條件
    if n <= 2:
        return n
    
    # 遞推公式和返回預定結(jié)果
    return climb_stairs(n - 1) + climb_stairs(n - 2) 

但是這樣的遞歸算法在 leetcode 上時無法通過的，原因就是我們前面提到的遞歸算法的可能會導致的一個問題：冗余計算，這樣會使得遞歸算法的時間復雜度隨著問題規(guī)模呈指數(shù)級上升，非常低效。

我們來分析下這個遞歸算法造成冗余計算的原因，參考下圖：

可以看到，在上面的遞歸分解計算圖中可以看到，計算 f(5) 時，f(3) 會被重復遞歸計算。如果是計算 f(6) 時，f(5)、f(4) 以及 f(3) 都會被重復計算，具體的圖就不畫了。而且隨著輸入的值越大，冗余的數(shù)越多，會導致一個 f(k) 可能被重復計算好多次。這也就造成了該算法無法通過題解的原因。改進方法當然比較簡單，我們有了遞推式，不用遞歸即可：

def climbStairs(self, n: int) -> int:
    if n <= 2:
        return n

    s = [1, 2]
    for _ in range(3, n + 1):
        s[0], s[1] = s[1], s[0] + s[1]
        return s[1]

因此，有時候遞歸算法看起來美好但需要慎用，特別對于遞推關(guān)系式中用到前面多個值時，要小心分析，避免出現(xiàn)冗余計算情況。

2. 二叉樹中的遞歸算法應(yīng)用

在二叉樹的問題中，幾乎處處用著遞歸。最經(jīng)典的例子就是二叉樹的前中后序的遍歷，使用遞歸算法較為簡單和明了，而使用非遞歸算法實現(xiàn)時會顯得十分復雜，尤其是后序遍歷，非常難寫。今天我們來看二叉樹中的幾個非常簡單的問題，全部使用遞歸方法解決這些問題。

給定兩個二叉樹，編寫一個函數(shù)來檢驗它們是否相同。如果兩個樹在結(jié)構(gòu)上相同，并且節(jié)點具有相同的值，則認為它們是相同的。

示例 1：

輸入:      1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

輸出: true

示例 2：

輸入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

輸出: false

示例 3：

輸入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

輸出: false

問題也比較簡單，leetcode 官方給我們定義了二叉樹類：

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

繼續(xù)我們的遞歸三要素：終止條件，遞推公式，預定輸出。首先看看遞歸函數(shù)的輸出：相同的樹(True) 和不同的樹(False)，輸入是兩個待比較二叉樹的根節(jié)點，那么遞歸函數(shù)這樣寫：

def is_same_tree(p, q):
    # ...
    
    reture False

然后來看看終止條件，對于二叉樹的終止條件就是到輸入的兩個根節(jié)點只要有一個為空即可。當兩個根節(jié)點都為空是，返回 True；當只有其中一個根節(jié)點為空而另一個根節(jié)點不為空時，明顯兩個樹不是相同的樹，故返回 False：

def is_same_tree(p, q):
    ################### 終止條件   ########################
    if not p and not q:
        return True
    if not p or not q:
        return False
    #####################################################
    # 遞歸比較
    # ...
    reture False

來看遞歸公式，判斷一棵二叉樹是否相同，我們首先是比較根節(jié)點的值，如果根節(jié)點的值不相同，那就直接返回 False；如果根節(jié)點相同，我們遞歸比較左子樹和右子樹，左子樹或者右子樹都相同時，那么這棵二叉樹才是相同的：

def is_same_tree(p, q):
    # 終止條件
    # ...
    # 遞歸比較，返回True/False
    return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

看看這個遞歸的方法是不是非常簡潔？那么這種寫法會不會存在冗余的計算呢？答案時不會的，因為我們可以看到這里遞歸計算的左子樹和右子樹時完全沒有重疊的部分，所以不存在冗余計算。因此，對于該問題而言，遞歸是一種非常優(yōu)美的寫法。完整的遞歸代碼如下：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def isSameTree(p, q):
    if not p and not q:
    return True

    if not p or not q:
        return False

    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

3. 遞歸窮舉

我們來看 leetcode 的第 15 題：三數(shù)之和。該題的難度為中等，題目內(nèi)容如下：

給你一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組。**注意：**答案中不可以包含重復的三元組。

示例：

給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

我們今天并不打算通過這道題的題解，因為這道題用遞歸算法是無法通過題解的，原因和之前一樣，算法的時間復雜度高，最后會超出時間限制。另外我們?nèi)サ艉竺娴淖⒁獠糠质马棧试S答案包含重復的三元組，我們使用遞歸算法相當于窮舉出所有可能的情況，判斷三元組的值是否能為 0。首先繼續(xù)我們的解題三部曲：

函數(shù)定義，輸入和輸出：

def three_sum(nums, target, count):
    """
    輸入: 
       num: 輸入的數(shù)組
       target: 目標值
       count: 在數(shù)組中找到幾個數(shù)之和滿足target
    輸出：
       []或者[[1,2,3], [-1,4,3]] 這樣的滿足條件的全部結(jié)果
    """
    
    res = []
    # ...
    
    return res

注意： 定義這樣的遞歸函數(shù)是經(jīng)過思考的，因為后續(xù)遞歸調(diào)用時需要依賴目標值 (target) 或元素個數(shù) (count) 這樣兩個參數(shù)。返回的參數(shù)要么為空，要么是所有找到的滿足條件的三元組的集合。

接下來是遞歸方法的終止條件，首先考慮以下幾個終止條件：

• 如果輸入的 nums 列表為空，那么直接返回 []；
• 如果輸入的 count 等于1，就要開始判斷了，因為這個時候只需要判斷 target 是否在列表中存在即可；

綜上，我們寫出終止條件的代碼：

def three_sum(nums, target, count):
    """
    輸入: 
       num: 輸入的數(shù)組
       target: 目標值
       count: 在數(shù)組中找到幾個數(shù)之和滿足target
    輸出：
       []或者[[1,2,3], [-1,4,3]] 這樣的滿足條件的全部結(jié)果
    """
    res = []
    ######################  終止條件  ######################################
    if not nums:
        return res
    if count == 1 and target in nums:
        return [[ target ]]
    elif count == 1 and target not in nums:
        # count等于1時，如果target沒有出現(xiàn)在剩余的nums中，說明不存在滿足條件的數(shù)組元素
        return res
    #######################################################################
    
    # 返回值
    return res

接下來最重要的，就是遞歸的公式了，遞歸的方向一定要朝著減小目標函數(shù)規(guī)模進行。

很明顯，我們的遞歸應(yīng)該是這樣子：以 nums 的第一個元素為遞歸點，整個 nums 列表中和為 target 的 count 個元素的結(jié)果可以分為包含 nums[0] 和不包含 nums[0] 的結(jié)果組成，簡單點說就是：

• 如果包含 nums[0]，那么接下來的 nums[1:] 列表中我們就要找值為 target - nums[0] 的 count - 1 個元素，也即 three_sum(nums[1:], target - nums[0], count -1)，然后我們還需要在得到的元組集中的最前面位置加上 nums[0]；
• 如果不包含 nums[0]，那么就是在 nums[1:] 列表中找值為 target 的 count 個元素，用遞歸函數(shù)表示就是 three_sum(nums[1:], target, count)；這樣找到的結(jié)果正是 count 個元素。

組合上述兩個遞歸得到的結(jié)果，就得到了函數(shù) three_sum(nums, target, count) 的結(jié)果，代碼如下：

res = []
# 包含nums[0]
t1 = three_sum(nums[1:], target - nums[0], count - 1)
# 不包含nums[0]
t2 = three_sum(nums[1:], target, count)
if t1:
    for i in range(len(t1)):
        t = [nums[0]]
        t.extend(t1[i])
        # 每個得到的結(jié)果前面加上 nums[0]
        res.append(t)
if t2:
    for j in range(len(t2)):
        res.append(t2[j]) 
        
# 此時得到的res就是遞歸的最后結(jié)果

綜合就可以得到遞歸遍歷所有三個元素和的情況并最終找出所有滿足條件結(jié)果的三元集：

def three_sum(nums, target, count):
    res = []

    # 終止條件
    if not nums:
        return res

    if count == 1 and target in nums:
        # 一定要這樣寫
        return [[ target ]]
    elif count == 1 and target not in nums:
        return res
    
    # 包含nums[0]
    t1 = three_sum(nums[1:], target - nums[0], count - 1)
    # 不包含nums[0]
    t2 = three_sum(nums[1:], target, count)
    if t1:
        for i in range(len(t1)):
            # 犯了一個巨大的錯誤，extend() 方法的使用，它無返回，只會擴充原數(shù)組
            # res.append([nums[0]].extend(t1[i]))
            t = [nums[0]]
            t.extend(t1[i])
            res.append(t)
    if t2:
        for j in range(len(t2)):
            res.append(t2[j])
     
    return res

調(diào)用該函數(shù)的方式如下：

nums = [-1, 0, 1, 2, -1, -4]
# 0 為目標值，3為多少個元素和為target
res = three_sum(nums, 0, 3)

這樣的遞歸遍歷思想在窮舉中用的比較多，因為它以非常優(yōu)雅的方式簡化了窮舉代碼。不過這道題使用遞歸算法等價于窮舉法，時間復雜度為 $O(n^3)$，因此顯得并不高效。對于最優(yōu)的解法讀者可以自行思考下然后解決它。

4. 小結(jié)

今天我們用 3 道編程題來體驗了一把遞歸算法，可以看到遞歸算法在編寫時會使得代碼整體看起來簡潔優(yōu)雅，但是有時候也會存在美麗的陷阱。例如第一個算法題中，使用遞歸算法會導致大量的冗余計算，使得算法的復雜度呈指數(shù)級增長。對于是否會存在冗余計算是在使用遞歸算法時一定要慎重考慮的，它會極大地影響算法的復雜度，如果存在的話，盡量不要使用遞歸算法或者想辦法避免它。