算法知识： 三步学会所有递归

「递归」在算法初学者眼中总是一个令人头疼的问题

但其实，这种可以将一个问题拆解为多个重复子问题的算法只要我们掌握了其中的 “套路” ，便可以游刃有余的解决所有递归类问题。下面我们就开始吧～

一、青蛙跳台阶

我们首先以最简单的「青蛙跳」为例子来拆解递归问题

剑指 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）

第二步：明确递归退出条件

做为一个递归函数，其最容易犯的错误就是一猛子扎进死循环中再也出不来；

为了避免这种情况的发生，设定一个严谨的递归结束条件是十分必要的。

在本题中我们得到「一只青蛙一次可以跳上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）

（当然，该题最好的解法是使用动态规划方法～ 但我们本篇文章着重在于递归思想的拆解，因此暂时不讲这种解法）

想必，前面的内容过于简单

大家都已经跃跃欲试了吧

接下来，我们使用树?的问题来验证这三步方法

二、二叉树的最大深度

「树?是一种常见的递归问题的应用」

104． 二叉树的最大深度【简单】

问题定义：

让我们使用刚才的方法，小试牛刀吧～

首先我们要明确树的数据结构

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

第一步：明确递归关系

我们想要得到一棵二叉树的最大深度，对于树中的一个node节点n，我们已知其深度关系为该节点的左右孩子的最大深度加一，则我们可得到：def f（n）：  return max（ f（n．left）， f（n．right） ） ＋ 1

第二步：明确递归退出条件

在本题中我们可以看到，树的深度是指最深的叶子节点到树的根节点之间的距离。因此，我们在判断递归的停止条件时，需要考虑叶子节点的结束条件。此时需要明确的是，对于没有左／右孩子的树节点要如何计算？这里需要我们制定统一的标准：我们认为所有的 有值节点 都是有左右孩子的，比如对于左下角值为15的节点来说，他的左右孩子均为None。然后我们将递归结束条件设置为：当 当前节点 为None时，深度为0。即可得到：

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

第三步：校验整体逻辑

判断边界条件，验证该函数的输入节点为根节点root时，是否依然符合以上逻辑。

（当然，该题目也可以使用深度优先遍历等方法，可以通过leetcode传送门去实战哦～）

三、满足条件的最长子串

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传送门去实战哦～）

＊ 本文涉及题目 ＊ ：

剑指 Offer 10－ II． 青蛙跳台阶问题

104． 二叉树的最大深度

395． 至少有 K 个重复字符的最长子串

怎么样，是不是很简单快去试一试更多递归问题吧