Contents

1. 1. 单纯递归
   1. 1.1. 主要思想
   2. 1.2. 典型运用
   3. 1.3. 实例
2. 2. 分治
   1. 2.1. 主要思想
   2. 2.2. 典型运用
   3. 2.3. 实例
3. 3. 回溯
   1. 3.1. 主要思想
   2. 3.2. 典型运用
4. 4. 动态规划
   1. 4.1. 主要思想
   2. 4.2. 典型运用
   3. 4.3. 实例
5. 5. 递归构建最终解
   1. 5.1. 单个数据
   2. 5.2. 多个数据

单纯递归

主要思想

递归是各类算法的基本动作，递归要注意以下几点：

• 递归算法能设计成不返回值就不返回值，因为递归的出口一般不止一个，设计成返回值会增加复杂度
• 如果设计成参数，那么要注意：参数如果传值，那么是每个被递归函数的私有数据，如果是传引用，那么是每个被递归函数的公有数据

单纯的递归动作，每递归一次，问题规模进一步缩小（有时可能是放大），直到问题规模到达下界（或上界），停止递归，原路返回

典型运用

斐波纳契数列

实例

单纯的递归易于编码实现，但容易造成重复计算子问题（可以通过记录子问题的解来避免），比如“斐波纳契数列”的递归解法：

public int f(int n){
      if (n == 1 ){
            return 1;
      }else if(n == 2){
            return 2;
      }else{
            return f(n - 1) + f(n - 2);
      }
}

避免重复计算子问题改进后的斐波纳契数列：

public int f(int n){
      
      //如果之前计算过那么直接返回
      if (resultArray[n - 1] != 0){
            return resultArray[n - 1];
      }

      if (n == 1 ){
            resultArray[0] = 1;
            return 1;
      }else if(n == 2){
            resultArray[1] = 2;
            return 2;
      }else{
            //记录每次计算的解
            resultArray[n - 1] = f(n - 1) + f(n - 2);
            return resultArray[n - 1];
      }
      
}

分治

主要思想

分治基本动作是递归，但它是把问题空间用递归的方法分为各个不相关的子问题，然后计算每个小问题，最后合并各个解,

分治消除了重复计算子问题的问题，所以比较高效,分治和单纯的递归的根本区别在于解空间的划分是否有重复

典型运用

归并排序，快速排序

实例

分治法有两个类型:
所有操作都在一组数据上进行，如下，

mergeSort方法的“合并一”与“合并二”没有数据交流，如归并排序

public static void mergeSort(int[] data, int start, int end) {

      if (start < end) {

            int middle = (start + end) / 2;
            mergeSort(data, start, middle);
            mergeSort(data, middle + 1, end);

            merge(data, start, end);
      }
}

如新search方法的“合并一”与“合并二”有数据交流

“合并一”得到的数据要返回给”合并二”，如求数组的最大值与最小值

public Result search(int start, int end) {

      if (start == end) {
            Result r = new Result(data[start], data[start]);
            return r;
      }

      int mid = (start + end) / 2;

      Result rLeft = search(start, mid);
      Result rRight = search(mid + 1, end);
      
      return Result.cmpResult(rLeft, rRight);
}

回溯

主要思想

回溯的基本动作是递归，把问题解想象成一个树状空间，

用递归的方法，深度搜索遍历整棵树；最适合使用回溯法的是在整个树状空间中，存在从根节点到某叶子节点的完整路径的解；回溯法会先完成整个左子树递归后，再进行右子树递归，当对第一个右子树进行递归的时候，整个函数完整的执行了一遍**

利用剪枝技术，回溯法可以得到较好的效果

回溯法和单纯的递归区别在于：

• “单纯的递归”递归到叶子节点时候就进行原路返回
• “回溯法”递归到叶子节点时返回到叶子节点的父节点，如果该父节点还有其他分支，那么对其他分支依次进行递归操作

所以回溯法中有一个操作要注意，

即是由叶子节点时返回到该叶子节点的父节点时，要把状态恢复到父节点将要递归到子节点前的状态

典型运用

八皇后问题

动态规划

主要思想

动态规划虽然在语言层面上没有用到递归，但是其最优子结构的公式是通过递归的思想构建的，其递归用在解空间上，适合于解有公共子问题的问题，把公共子问题的解保存在一个表中，解其他子问题时候需要时进行查询

对于“斐波纳契数列”，其迭代的解法近似可以看成是一种动态规划，相对于递归解法，没有重复计算一些子问题，有更高的效率；动态规划通过遍历已计算出的最优子问题的表，来构建最优解

因为动态规划的每一步都需要遍历全部或者部分的子空间解，递归只是对上一步解的固定模式的应用

典型运用

0-1背包，最长非连续公共子序列

实例

“斐波纳契数列”的迭代解法只是单纯的读表，所以只能说是近似的动态规划：

public int f(int n) {
      if (n == 1) {
            return 1;
      } else if (n == 2) {
            return 2;
      } else {
            resultArray[0] = 1;
            resultArray[1] = 2;

            for (int i = 2; i < n; i++) {
                  resultArray[i] = resultArray[i - 1] + resultArray[i - 2];
            }
            return resultArray[n - 1];
      }
}

递归构建最终解

单个数据

• 全局变量:八皇后问题，计算解的数量
• 函数参数：最长非连续公共子序列，计算最长非连续公共子序列
• 返回值：斐波纳契数，计算总和

多个数据

需要对递归的各个分支得到数据进行对比来构建最终的解，把各个分支得到的解放进一个列表中，然后根据最优判断条件对这个列表进行遍历，判断出最优解。比如“最长连续公共子序列问题”