「遞歸」在算法初學者眼中總是一個令人頭疼的問題

但其實，這種可以將一個問題拆解為多個重復子問題的算法只要我們掌握了其中的 “套路” ，便可以游刃有余的解決所有遞歸類問題。下面我們就開始吧～

一、青蛙跳臺階

我們首先以最簡單的「青蛙跳」為例子來拆解遞歸問題

劍指 Offer 10－ II． 青蛙跳臺階問題【超級簡單】

問題定義：一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階。求該青蛙跳上一個 n 級的臺階總共有多少種跳法。

第一步：明確遞歸關系

當我們確定了一個問題是可以使用遞歸思想解決的時候，我們一定可以明確其中的遞歸關系，即該問題的子問題之間存在的函數關系。在本題中，我們要 求解青蛙跳上一個 n 級的臺階總共有多少種跳法；我們知道青蛙一次只可以跳1級或2級的臺階，那么在小蛙跳上第n 級臺階的前一步時，小蛙跳上第n 級臺階的前一步時，小蛙?一定站在第n－1 級或第n－2 級臺階上。所以如果設「青蛙跳上一個 n 級的臺階」共有 f（n） 種跳法；則我們可以得到其中的函數關系為f（n） ＝ f（n－1） ＋ f（n－2）則可以得到函數

def f（n）：    return f（n－1） ＋ f（n－2）

第二步：明確遞歸退出條件

做為一個遞歸函數，其最容易犯的錯誤就是一猛子扎進死循環(huán)中再也出不來；

為了避免這種情況的發(fā)生，設定一個嚴謹的遞歸結束條件是十分必要的。

在本題中我們得到「一只青蛙一次可以跳上1級臺階，也可以跳上2級臺階」；

可以知道，當臺階數 n 為 1 時，此時不需要進行求解，可以直接知道小蛙?只有一種跳法，一次就可以跳上去。

當臺階數 n 為 2 時，小蛙?可以 一次跳兩個臺階 或 一次跳一個臺階一共跳兩次，可以有兩種跳法。

則我們可以得到函數停止條件

def f（n）：  if n ＝＝ 1：    return 1  if n ＝＝ 2：    return 2  return f（n－1） ＋ f（n－2）

第三步：校驗整體邏輯

在上述函數中顯然，對于 n ，我們只考慮到了n ＞＝ 1的情況；

為了題目更嚴謹（不僅本題，所有題目都要記得最后校驗），我們最后補全可能存在的所有情況；

即根據算法題命題，最后必須要考慮到的邊界條件。

又因為題目示例中給到：

所以得到最后的函數：

def f（n）：  if n ＝＝ 0：    return 1  if n ＝＝ 1：    return 1  return f（n－1） ＋ f（n－2）

（當然，該題最好的解法是使用動態(tài)規(guī)劃方法～ 但我們本篇文章著重在于遞歸思想的拆解，因此暫時不講這種解法）

想必，前面的內容過于簡單

大家都已經躍躍欲試了吧

接下來，我們使用樹?的問題來驗證這三步方法

二、二叉樹的最大深度

「樹?是一種常見的遞歸問題的應用」

104． 二叉樹的最大深度【簡單】

問題定義：

讓我們使用剛才的方法，小試牛刀吧～

首先我們要明確樹的數據結構

＃ class TreeNode（object）：＃     def ＿＿init＿＿（self， val＝0， left＝None， right＝None）：＃         self．val ＝ val＃         self．left ＝ left＃         self．right ＝ right

第一步：明確遞歸關系

我們想要得到一棵二叉樹的最大深度，對于樹中的一個node節(jié)點n，我們已知其深度關系為該節(jié)點的左右孩子的最大深度加一，則我們可得到：def f（n）：  return max（ f（n．left）， f（n．right） ） ＋ 1

第二步：明確遞歸退出條件

在本題中我們可以看到，樹的深度是指最深的葉子節(jié)點到樹的根節(jié)點之間的距離。因此，我們在判斷遞歸的停止條件時，需要考慮葉子節(jié)點的結束條件。此時需要明確的是，對于沒有左／右孩子的樹節(jié)點要如何計算？這里需要我們制定統(tǒng)一的標準：我們認為所有的 有值節(jié)點 都是有左右孩子的，比如對于左下角值為15的節(jié)點來說，他的左右孩子均為None。然后我們將遞歸結束條件設置為：當 當前節(jié)點 為None時，深度為0。即可得到：

def f（n）：  if n is None：    return 0  return max（ f（n．left） ， f（n．right） ） ＋ 1

第三步：校驗整體邏輯

判斷邊界條件，驗證該函數的輸入節(jié)點為根節(jié)點root時，是否依然符合以上邏輯。

（當然，該題目也可以使用深度優(yōu)先遍歷等方法，可以通過leetcode傳送門去實戰(zhàn)哦～）

三、滿足條件的最長子串

395． 至少有 K 個重復字符的最長子串【中等】

問題定義：給你一個字符串 s 和一個整數 k ，請你找出 s 中的最長子串， 要求該子串中的每一字符出現次數都不少于 k 。返回這一子串的長度。

第一步：明確遞歸關系

當輸入字符串 s 中的某一字符 c 不滿足條件時（在該字符串 s 中的出現次數少于 k ），則所求的子串長度為「不包含字符c的其他的滿足條件的子串長度」的最大值。
聽起來可能比較繞，其實拆解出來就是這樣：比如，對于輸入字符串 s ＝ ＂ababcaaabdddcaaa＂ 并要求出現次數 k＝3 來說，對于該字符串中的字符 c ，只出現了一次，所以字符串 s ＝ ＂ababcaaabdddcaaa＂ 中滿足條件的子串必然不包含字符 c ；因此，該字符串 s ＝ ＂ababcaaabdddcaaa＂ 可以被拆解為 s1 ＝ ＂abab＂， s2 ＝ ＂aaabddd＂ 與 s3 ＝ ＂aaa＂ ；接下來對于字符串 s2 ＝ ＂aaabddd＂ ，其中的字符b，只出現了一次；因此，字符串 s2 又可以被分為 s21 ＝ ＂aaa＂ 與 s2 ＝ ＂ddd＂以此類推．．．
因此，我們可以得到子串長度的遞歸關系為：f（s） ＝ max（ f（s1） ， f（s2） ， f（s．．．） ）

def f（s）：   for char in set（s）：     if s．count（char） ＜ k：       sub＿s＿list ＝ s．split（char）       return max（［f（sub） for sub in sub＿s＿list］）

第二步：明確遞歸退出條件

若不存在這樣的字符 c ，則表明字符串 s 直接滿足該條件，可直接返回字符串 s 的長度。

def f（s）：  for char in set（s）：    if s．count（char） ＜ k：      sub＿s＿list ＝ s．split（char）      return max（［f（sub） for sub in sub＿s＿list］）  return len（s）

當本身字符串 s 的長度 ＜ k 時，即永遠不可能有滿足題目要求的子串，所以直接返回0。

def f（s）：  if len（s） ＜ k：     return 0   for char in set（s）：    if s．count（char） ＜ k：      sub＿s＿list ＝ s．split（char）      return max（［f（sub） for sub in sub＿s＿list］）  return len（s）

第三步：校驗整體邏輯

判斷邊界條件，驗證該函數進入遞歸時的返回結果 與 未進入遞歸時的返回結果。

（該題目也可以使用分治法或滑動窗口等方法，可以通過leetcode傳送門去實戰(zhàn)哦～）

＊ 本文涉及題目 ＊ ：

劍指 Offer 10－ II． 青蛙跳臺階問題

104． 二叉樹的最大深度

395． 至少有 K 個重復字符的最長子串

怎么樣，是不是很簡單快去試一試更多遞歸問題吧