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

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

一、青蛙跳臺(tái)階

我們首先以最簡(jiǎn)單的「青蛙跳」為例子來(lái)拆解遞歸問(wèn)題

劍指 Offer 10－ II． 青蛙跳臺(tái)階問(wèn)題【超級(jí)簡(jiǎn)單】

問(wèn)題定義：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。

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

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

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

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

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

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

在本題中我們得到「一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階」；

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

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

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

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

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

在上述函數(shù)中顯然，對(duì)于 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)然，該題最好的解法是使用動(dòng)態(tài)規(guī)劃方法～ 但我們本篇文章著重在于遞歸思想的拆解，因此暫時(shí)不講這種解法）

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

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

接下來(lái)，我們使用樹(shù)?的問(wèn)題來(lái)驗(yàn)證這三步方法

二、二叉樹(shù)的最大深度

「樹(shù)?是一種常見(jiàn)的遞歸問(wèn)題的應(yīng)用」

104． 二叉樹(shù)的最大深度【簡(jiǎn)單】

問(wèn)題定義：

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

首先我們要明確樹(shù)的數(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)系

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

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

在本題中我們可以看到，樹(shù)的深度是指最深的葉子節(jié)點(diǎn)到樹(shù)的根節(jié)點(diǎn)之間的距離。因此，我們?cè)谂袛噙f歸的停止條件時(shí)，需要考慮葉子節(jié)點(diǎn)的結(jié)束條件。此時(shí)需要明確的是，對(duì)于沒(méi)有左／右孩子的樹(shù)節(jié)點(diǎn)要如何計(jì)算？這里需要我們制定統(tǒng)一的標(biāo)準(zhǔn)：我們認(rèn)為所有的 有值節(jié)點(diǎn) 都是有左右孩子的，比如對(duì)于左下角值為15的節(jié)點(diǎn)來(lái)說(shuō)，他的左右孩子均為None。然后我們將遞歸結(jié)束條件設(shè)置為：當(dāng) 當(dāng)前節(jié)點(diǎn) 為None時(shí)，深度為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時(shí)，是否依然符合以上邏輯。

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

三、滿足條件的最長(zhǎng)子串

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

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

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

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

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 的長(zhǎng)度 ＜ k 時(shí)，即永遠(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)入遞歸時(shí)的返回結(jié)果 與 未進(jìn)入遞歸時(shí)的返回結(jié)果。

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

＊ 本文涉及題目 ＊ ：

劍指 Offer 10－ II． 青蛙跳臺(tái)階問(wèn)題

104． 二叉樹(shù)的最大深度

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

怎么樣，是不是很簡(jiǎn)單快去試一試更多遞歸問(wèn)題吧