2. 递归

宋涛收录于 Python

2020-07-02 约 1079 字预计阅读 3 分钟

递归

1. 如何写递归

递归是一种应用非常广泛的算法（或者编程技巧），搞懂递归非常重要。基本上，所有的递归问题都可以用递推公式来表示。要想使用递归解决问题，必需满足三个前提条件:

一个问题的解可以分解为几个子问题的解，子问题就是规模更小的问题
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件

关键是如何编写递归代码呢？写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再找出终止条件，最后将递推公式和终止条件翻译成代码。

千万要注意递归代码的核心是发现问题分解的规律，并将其抽象为递推公式，千万不要想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。在编写递归代码的时候，我们可以按照如下的思路，按骥索图:

思考问题的分解规律，写出递推公式
- 有的问题分解很简单，比如二叉树的遍历，直接可以分解成左子树和右子树两个遍历
- 有的问题分解很难，比如动态规划
假设子问题已解决，并在此基础上，将递推公式翻译成代码，对问题进行求解
根据需要的值，思考递归函数的参数和返回值
思考边界，找出终止条件

我们以二叉树的序列化反序列化为例来看看，如何写递归代码。下面是使用先序遍历实现的二叉树的序列化反序列化:

 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
30
31
32
33


from collections import deque

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            return "null"
        return str(root.val) + "," + self.serialize(root.left) + "," + self.serialize(root.right)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        collect = deque(data.split(","))
        def dfs():
            if len(collect) == 0:      # 片段 2
                return None
            node = collect.popleft()
            if node == "null":         # 片段 2
                return None
            root = TreeNode(int(node))  # 片段 1
            root.left = dfs()
            root.right = dfs()
            return root
        return dfs()

二叉树反序列化的思考过程:

先序遍历是先输出父节点，在输出左子节点，最后右子节点
所以 collect.popleft() 第一输出的是父节点，第二次输出的左子树，第三次输出的是右子树
因为我们要知道父节点的子节点，因此我们可以先假设 dfs() 返回的是树的一个节点，即return root
按照左右子节点的输出顺序，就有上述代码"片段1"
最后我们来思考终止条件
- 如果已经遍历完输入，则退出，即代码"片段2"
- 如果当前输入为 null，说明为空，其不会有左右子节点，退出，即代码"片段3"

当然如果你不清楚树的先序遍历，自然不可能写出上面的代码。递归代码真正的难点其实就在于如何找出递归公式，特别是对于动态规划而言。

2. 递归存在的问题

使用递归时会存在很多问题，最常见的两个是:

递归代码要警惕堆栈溢出
递归代码要警惕重复计算

为了避免重复计算，我们可以通过一个数据结构比如散列表来保存已经求解的函数调用 f(k)。当递归调用 f(k) 时先看下是否已经求解过了，如果是则直接返回，无须重复计算。

目录

2. 递归

1. 如何写递归

2. 递归存在的问题