递归解题三部曲

前言

递归算法解题容易让人随着递归而递归（也就是说容易在想本次递归的时候想到了下一次递归的事情）一定要走出这种递归误区！ 我们只有注意本次递归做什么即可 我们需要关心的主要是以下三点：

整个递归的终止条件。

本地递归需要做什么？

应该返回给上一级的返回值是什么？

因此，也就有了我们递归解题的三部曲：

递归终止条件：递归应该在什么时候结束？

本次递归做什么操作：在这一级递归中，应该完成什么任务？

返回什么：应该给上一级返回什么信息？

接下来介绍一下《算法图解》里面对递归的说明

每个递归函数都有两部分：基线条件 （base case）和递归条件 （recursive case）。

递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

算法4

这几天开始看了《算法》这本书，里面第一章就对递归做出了归纳 编写递归代码时最重要的有以下三点

1.递归总有一个最简单的情况----方法的第一条语句总是一个包含return的条件语句

2.递归调用总是尝试去解决一个规模更小的子问题，这样额递归才能收敛到最简单的情况

3.递归调用的父问题和尝试解决的子问题之间不应该有交集

违背其中任意一条都可能得到错误结果或者时低效的代码 我觉得第一点正式我们三部曲的第一步，第二点就是第二步，而第三点我觉得非常重要，因为递归的过程我总想着这一层是不是要判断一下上一层的情况，这么明显就时错误，容易越考虑越复杂。所以我觉得第三点非常重要!

1.必须有一个基本的结束条件（最小规模问题的直接解决）

2.必须能改变状态向基本结束条件演进（缩小问题规模）

3.递归算法必须调用自身（解决缩小规模的相同问题）

例1：求二叉树的最大深度

​​Leetcode 104. 二叉树的最大深度​​

直接上模版：

递归终止条件。什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。

本次递归做什么操作。首先，还是强调要走出之前的思维误区，本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。

返回什么。应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。

class Solution:
def maxDepth(self, root: TreeNode) -> int:
# 结束条件
if root == None: return 0
# 下面的三行代码都是 本次递归做什么
left_deep = self.maxDepth(root.left)
right_deep = self.maxDepth(root.right)
# 返回值
return max(left_deep, right_deep) + 1

例2：翻转一棵二叉树

​​Leetcode 226 翻转二叉树​​

1.递归终止条件：节点为空就结束了，这里注意题目运行为 None 的左右节点交换

2.本次递归做什么操作：交换root的左右节点

3.返回什么：当然是返回root节点啦

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
# 结束条件
if root == None: return root
tem = root.left
# 交换左右节点
root.left = self.invertTree(root.right)
root.right = self.invertTree(tem)
# 返回根节点
return root

例3：两两交换链表中的节点

​​Leetcode 24. 两两交换链表中的节点​​

找终止条件：没得交换的时候，只剩一个节点或者没有节点的时候，自然递归就终止了。

本次递归做什么操作： 只考虑本级递归，也就是只要交换两个节点：head 和 head.next 而head的next交给递归来处理

返回什么：已经处理好的链表。

class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 结束条件
if head == None or head.next == None: return head
# head 和 head.next
next = head.next
# 把之前的next位置 用递归来解决，啥都不要想， 并且把下一次需要交换的节点传入
head.next = self.swapPairs(next.next)
next.next = head
# 交换好的链表
return next