每日一问之什么是递归

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 3.1k | 阅读时长 ≈ 3 分钟

最近在刷 LeetCode 的时候，发现很多题用递归的方法来解会方便很多，解题过程中也加深了对递归方法的印象。今天正好可以重新整理一下关于递归的相关知识。

  • 什么是递归
  • 递归的条件是什么
  • 递归的使用例子

什么是递归

简单的说，递归就是函数自己调用自己。根据我自己的理解，我觉得是不同于像 for，while 这种函数内的循环，递归可以说是一种函数外的循环。如下面的方程所示，就是一种典型的递归函数：

1
2
3
def countdown(i):
    print(i)
    return countdown(i-1)

递归的条件

在写递归函数的时候，需满足两个条件，一个是 基线条件，一个是 递归条件。像上面的代码就不是严格意义上的递归函数，因为其不满足基线条件和递归条件，而且该函数会陷入死循环。

说白了，递归条件 就是函数调用自己；基线条件 就是函数不再调用自己。所以，递归函数会包含基线条件和递归条件这两部分。现在可以将上面的代码改成正确形式：

1
2
3
4
5
6
def countdown(i):
    print(i)
    if i <= 1:  # 基线条件 
        return
    else:      # 递归条件
        countdown(i-1)

这时候函数就不会陷入死循环而无穷尽的执行下去了。

递归的使用例子

下面来举两个递归的使用例子，例子都来自最近刷的 LeetCode 的 Easy 级别的题目。

1. Same Tree

题目：给定两个二叉树，编写一个函数来检查它们是否相同。 如果两个二叉树在结构上相同并且节点具有相同的值，则认为它们是相同的，否则是不同的。例子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:
Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true
Example 2:
Input:     1         1
          /           \
         2             2
        [1,2],     [1,null,2]
Output: false
Example 3:
Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
Output: false

解法如下，当 p，q 两个二叉树都为空的时候，直接返回 True；当 p，q 中其中一个为 空，则直接返回 False；当 p，q 的值不相等也直接返回 False。这些都是基线条件，其余的是递归条件。判断完 p，q 的值，再继续判断 p 和 q 的子根的两个值，如果都相等，这两个二叉树就是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
#class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False

        return Solution.isSameTree(self, p.left, q.left) and
                   \ Solution.isSameTree(self, p.right, q.right)
2. Symmetric Tree

题目：给定二叉树，检查它是否是自身的镜像（即，围绕其中心对称）。例子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

解法如下，为了方面解题，另外写了一个递归函数 fileAndCheck()。该函数的递归条件是两个根均为非空，即均存在。如果两个根都存在的话，那么就返回判断两个根的值是否相等，且一个根的两个子根是否与另一个根的对应两个子根的翻转相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if root is None:
            return True

        return filpAndCheck(root.left, root.right)

# 此处使用递归
# 1. 先确保两个根的值是否相等
# 2. 再确保一个根的两个子根是否与另一根的对应的两个子根的翻转相同
def filpAndCheck(root1, root2):
    if root1 and root2:
        return root1.val == root2.val and filpAndCheck(root1.left, root2.right) and filpAndCheck(root1.right,
                                                                                                 root2.left)
    # 如果其中一个为 null，则返回 False
    # 如果两个都为 null，则返回 True
    return not (root1 or root2)

P.S：文中有错欢迎指出，互相学习。