递归算法详解_递归公式

1. 什么是递归

    相信很多人开始学算法，第一个接触的就是递归，为什么要先学递归呢？这是因为递归是其他算法的基础，像深度优先搜索、分治算法、回溯算法都是在递归的基础上做出一些改进。那到底什么是递归呢？递归 = 递进 + 回归，递进的意思是把复杂的问题逐步的拆解成和原问题类似的子问题，直到我们一眼就能看出子问题的答案为止（也就是递归终止条件）；而回归和递进正好相反，当我们求解了最简子问题后，我们就能求解上一层的子问题，求解了上一层的子问题，就能求解更上一层的子问题，以此类推，最后就能求解原问题的答案。下面以斐波那契数列展示下递归：
    斐波那契数列的定义：$f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)(n\ge 2)$
    求解斐波那契数列就可以用下图来表示，当我们要求$f(n)$，由于$f(n)=f(n-1)+f(n-2)$，于是求解$f(n)$就可以递进分解为求解$f(n-1)$和$f(n-2)$，同样$f(n-1)$也可以递进分解为$f(n-2)$和$f(n-3)$，$f(n-2)$可以递进分解为$f(n-3)$和$f(n-4)$；另外由斐波那契的定义可以直接看出$f(0)=0,f(1)=1$，这就是最简子问题（递归终止条件），有了$f(0)$和$f(1)$的答案后我们就能回归求$f(2)$，同样有了$f(1)$和$f(2)$我们就能回归求$f(3)$，以此类推我们就能求出$f(n)$的值。

2. 递归三要素

    对递归有一个概念以后，下面给出递归的三要素，也就是我们做递归的题目时首先需要考虑的点：
        1. 明确递归函数的定义，先不用管函数内部的代码细节，首先先明确递归函数的功能，函数的输入和输出；
        2. 根据函数的定义找出递归结束的条件，也就是我们一眼就能看出该子问题的答案；
        3. 找出递推关系式，也就是如何将原问题划分为子问题，如何从子问题的答案反求原问题的答案。

3. 递归的优缺点

    递归的优点：递归最重要的优点就是简洁，我们不需要考虑使用循环解决问题时每次循环时的各种细节，也不必考虑递归函数中一层层是如何展开和终止的，我们相信函数并调用函数实现其相应的功能即可，唯一需要考虑的就是拆解子问题，递归终止条件。
    递归的缺点：首要缺点就是递归不好想！！！ 第二归执行过程中，会调用函数本身，编译器会为递归调用分配递归栈存放递归过程中的参数、返回地址以及临时变量；第三递归中会有很多重复计算，当我们把大问题分解成小问题时，很多小问题其实是同一个问题，这样就会重复计算相同的问题，导致效率变低。

4. 递归的优化

    为什么要进行递归优化？前面在递归缺点中谈到了重复计算，所以递归优化就是为了避免重复计算，提高效率。我们可以看一些前面那个斐波那契的例子，可以发现$f(n-2)$计算会两次，$f(n-3)$会计算三次，越往下的子问题重复更严重，于是我们需要设置一个“备忘录”来避免重复，其核心就是利用辅助数组（或者哈希表）存储递归过程中已经计算过的值。在递归时首先先去备忘录查是否有已经计算过的值，如果有就直接取用，不需要重复计算，如果没有就计算当前子问题的值，并将其值存放在备忘录中。斐波那契数列设置备忘录：

    //递归函数
    int recur(vector<int> &aux, int n){
        if(aux[n] != 0) return aux[n]; //先去备忘录找结果
        aux[n] = recur(aux, n-1) + recur(aux, n-2); //找不到以后将递归计算的结果存进备忘录
        return aux[n]; //返回结果
    }
    int fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        vector<int> aux(n+1, 0);
        return recur(aux, n);
    }
1
2
3
4
5
6
7
8
9
10
11

5. 递归的例子

二叉树相关的问题
    二叉树无疑是递归的最好实践，90%的二叉树问题都可以用递归来解决，首先来看解决二叉树问题的三个基本框架：

//二叉树的类型定义
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };

//二叉树的前序遍历
void traverse(TreeNode* root){
    if(root){
        对当前节点的操作
        traverse(root->lchild); //调用左子树
        traverse(root->rchild); //调用右子树
    }
}

//二叉树的中序遍历
void traverse(TreeNode* root){
    if(root){
        traverse(root->lchild); //调用左子树
        ...  //对当前节点的操作
        traverse(root->rchild); //调用右子树
    }
}
//二叉树的后序遍历
void traverse(TreeNode* root){
    if(root){
        traverse(root->lchild); //调用左子树
        traverse(root->rchild); //调用右子树
        ...  //对当前节点的操作
    }
}

//当然这些操作也可以扩展到 N叉树，不过 N叉树没有中序遍历
void traverseN(TreeNode* root){
    if(root){
        ...  //对当前节点的操作
        for(child : root->children)
            traveseN(child);
    }
}
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
34
35
36
37
38
39
40
41
42
43
44

    大部分二叉树的题目都能套用上述的框架来解题。来看一下剑指 Offer 34. 二叉树中和为某一值的路径这题：
题目要求在定二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点 路径总和等于给定目标和的路径。
    题目分析：首先题目要求的是从给定根结点到叶子结点上的路径和，因此就可以确定递归结束的条件就是当前节点为空时，这和上述的三个框架的结束条件是一样的，另外本题需要找到符合条件的路径，因此在遍历的过程中设置一个辅助vector用来记录已经走过的节点值，并且判断当节点为叶子结点时，此时的路径和是否为targetSum。代码如下：

class Solution {
public:
    vector<vector<int>> res;
    void recurTree(TreeNode* root, int target, vector<int>& cur){
        if(root){
            cur.push_back(root->val); //添加当前节点值
            if(root->left == nullptr && root->right == nullptr && target == root->val){
                res.push_back(cur);
            }
            recurTree(root->left, target - root->val, cur); //遍历左子树
            recurTree(root->right, target - root->val, cur); //遍历右子树
            cur.pop_back(); //删除当前节点值，因为要返回上一层，所以当前节点不可能在路径中出现
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> cur; //辅助变量记录已经遍历过的节点
        recurTree(root, target, cur);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    可以看到上面的解题代码就是套用了前序遍历的框架。接着再看另外一题：LeetCode 106.从中序与后序遍历序列构造二叉树
例如，给出中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]，就能构造出如下图所示的二叉树：
    题目分析：我们知道二叉树的后序遍历的顺序是先左子树再右子树最后是根结点，因此二叉树序列中的最后一个元素为根结点，而二叉树的中序遍历结果是先左子树再根结点最后是右子树，因此我们可以从后序序列中确定当前树的根结点，然后找出中序序列中二叉树的根结点位置，并把二叉树分为左右子树。例如对于序列中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]，首先我们从后序遍历中找出根结点3，因此我们可以在中序序列中确定左子树的中序序列为[9]，右子树的中序序列为[15,20,7]，接着在根据相应的后序序列[9]和[15,7,20]确定左右子树的根结点，并确定左右子树的左子树和右子树，以此类推就能完成二叉树的构建。当然本题为了根据后序序列得到的根结点快速定位中序序列中根结点的位置，设置了一个哈希表作为辅助变量，具体实现的代码如下：

class Solution {
public:
    unordered_map<int, int> rootIndex; //辅助的哈希表，记录中序序列中每个元素的位置
    TreeNode* recurTree(vector<int>& inorder, vector<int>& postorder, int in_left, int in_right, int post_left, int post_right){
        if(post_right < post_left) return nullptr; //表示当前序列为空，也就是空树，所以直接返回nullptr
        int inRootIndex = rootIndex[postorder[post_right]]; //获得中序序列中根结点的位置
        int numOfRchild = in_right - inRootIndex; //右子树的元素个数
        TreeNode* root = new TreeNode(postorder[post_right]); //创建根结点
        root->left = recurTree(inorder, postorder, in_left, inRootIndex-1, post_left, post_right-numOfRchild-1); //创建左子树
        root->right = recurTree(inorder, postorder, inRootIndex+1, in_right, post_right-numOfRchild, post_right-1); //创建右子树
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
       for(int i = 0; i < inorder.size(); i++)
            rootIndex[inorder[i]] = i;
        return recurTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    其实不难看出，上述这题也是应用了二叉树的前序遍历的框架，先构造根结点再构造左子树跟右子树。
相似的题目还有：
    LeetCode 104. 二叉树的最大深度
    LeetCode 105. 从前序与中序遍历序列构造二叉树
    LeetCode 226. 翻转二叉树
    LeetCode 236. 二叉树的最近公共祖先
    剑指Offer 26. 树的子结构
    剑指 Offer 54. 二叉搜索树的第k大节点