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

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

一、青蛙跳臺階

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

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

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

第一步：明確遞歸關(guān)系

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

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

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

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

為了避免這種情況的發(fā)生，設(shè)定一個嚴(yán)謹(jǐn)?shù)倪f歸結(jié)束條件是十分必要的。

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

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

當(dāng)臺階數(shù) n 為 2 時，小蛙?可以 一次跳兩個臺階 或 一次跳一個臺階一共跳兩次，可以有兩種跳法。

則我們可以得到函數(shù)停止條件

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

第三步：校驗(yàn)整體邏輯

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

為了題目更嚴(yán)謹(jǐn)（不僅本題，所有題目都要記得最后校驗(yàn)），我們最后補(bǔ)全可能存在的所有情況；

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

又因?yàn)轭}目示例中給到：

所以得到最后的函數(shù)：

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

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

想必，前面的內(nèi)容過于簡單

大家都已經(jīng)躍躍欲試了吧

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

二、二叉樹的最大深度

「樹?是一種常見的遞歸問題的應(yīng)用」

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

問題定義：

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

首先我們要明確樹的數(shù)據(jù)結(jié)構(gòu)

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

第一步：明確遞歸關(guān)系

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

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

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

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

第三步：校驗(yàn)整體邏輯

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

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

三、滿足條件的最長子串

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

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

第一步：明確遞歸關(guān)系

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

當(dāng)本身字符串 s 的長度 ＜ k 時，即永遠(yuǎn)不可能有滿足題目要求的子串，所以直接返回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）

第三步：校驗(yàn)整體邏輯

判斷邊界條件，驗(yàn)證該函數(shù)進(jìn)入遞歸時的返回結(jié)果 與 未進(jìn)入遞歸時的返回結(jié)果。

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

＊ 本文涉及題目 ＊ ：

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

104． 二叉樹的最大深度

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

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