# 2. 递归


递归

<!-- more -->

## 1. 如何写递归
递归是一种应用非常广泛的算法（或者编程技巧），搞懂递归非常重要。基本上，所有的递归问题都可以用递推公式来表示。要想使用递归解决问题，必需满足三个前提条件:
1. 一个问题的解可以分解为几个子问题的解，子问题就是规模更小的问题
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件

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

千万要注意递归代码的核心是发现问题分解的规律，并将其抽象为递推公式，千万不要想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。在编写递归代码的时候，我们可以按照如下的思路，按骥索图:
1. **思考问题的分解规律，写出递推公式**
    - 有的问题分解很简单，比如二叉树的遍历，直接可以分解成左子树和右子树两个遍历
    - 有的问题分解很难，比如动态规划
2. **假设子问题已解决**，并在此基础上，将递推公式翻译成代码，对问题进行求解
3. **根据需要的值，思考递归函数的参数和返回值**
4. **思考边界，找出终止条件**

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


```python
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()
```

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

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

## 2. 递归存在的问题
使用递归时会存在很多问题，最常见的两个是:
1. 递归代码要警惕堆栈溢出
2. 递归代码要警惕重复计算

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