Leetcode题解 | 三步学会所有递归

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

但其实，这种可以将一个问题拆解为多个重复子问题的算法

只要我们掌握了其中的 “套路” ，便可以游刃有余的解决所有递归类问题。

下面我们就开始吧～

一、青蛙跳台阶

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

剑指 Offer 10- II. 青蛙跳台阶问题【超级简单】 https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

问题定义：

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

第一步：明确递归关系

当我们确定了一个问题是可以使用递归思想解决的时候，我们一定可以明确其中的递归关系，即该问题的子问题之间存在的函数关系。

在本题中，我们要 求解青蛙跳上一个 n 级的台阶总共有多少种跳法；

我们知道青蛙一次只可以跳1级或2级的台阶，那么在小蛙🐸跳上第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. 二叉树的最大深度【简单】 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

问题定义：

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

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

# 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 个重复字符的最长子串【中等】 https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/

问题定义：

给你一个字符串 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 个重复字符的最长子串

怎么样，是不是很简单

快去试一试更多递归问题吧

leetcode-递归问题-传送门： https://leetcode-cn.com/tag/recursion/problemset/​