递归？递归！我该如何学递归和回溯算法！

2020-04-01 15:16 435人阅读评论(0)

递归作为回溯算法的核心逻辑，是学习回溯法等其他算法的先遣知识。本文从递归的概念开始,举例说明什么是递归。然后介绍回溯算法的概念和理解，最后介绍具体应用并给出Java版本的示例代码。
学习方法：遇到某一个不理解的点时需要暂时跳过，理解算法时需要认真看代码和注释（有些还需要一步步调试才能看懂）。先完成整体阅读，然后多读几遍相互启发。

1 搞懂递归

1.1 什么是递归

简单来说就是方法自己调用自己，每次调用时传入不同的参数变量。而且一般能从传入的参数变量处得到结束条件(我们在设计递归参数时要参照这一点）。
递归一般包含 递归结束条件(用来结束递归）和递归方法体(用来完成问题求解）。通过例子来感受下。

public class Main {
    public static void main(String[] args) {
        System.out.println(recrusion(4));
    }
    //递归方法
    private static int recrusion(int n) {
        if (n == 1) return 1;    //递归结束条件
        int res = recrusion(n - 1) * n;  //递归体
        return res;  
    }
}

1.2 递归的运行方式

递归方法在执行时会创建一个栈空间。（jvm运行机制决定）
栈空间相互之间独立，局部变量不会相互影响。（体现在参数n）
引用类型变量存在堆空间里（jvm运行机制决定），各方法共享同一引用变量。
递归体必须不断逼近递归结束条件（这是我们在设计递归体需要考虑的,否则就是无限递归)

递归运行图解：

2 回溯算法

2.1 简介

回溯算法是一种很重要也比较基础的算法，在面试或算法题中都有涉及。其适用于诸如迷宫问题、N皇后问题，背包问题等复杂问题的求解，有通用解法的美称。回溯算法是类似于深度优先搜索的试探算法。在构造解的过程中，如果发现不满足条件的解时，就“回溯”（其实就是递归返回）。博主个人理解是回溯算法其实就是一种穷举法，因为他会尝试遍历所有解（这是回溯法的最坏情况）。

2.2 设计回溯算法一般方法

根据题意，尝试思考一种穷举法来完成该问题。
思考某种特定的步骤来完成穷举，这种特定步骤有一般是可重复的（可重入递归）。
回溯算法构建解时是一步步构建的，所以我们要思考选用一种合适的数据结构存储中间得出来的不完全解。让递归函数可以根据前面的已经递归得到的信息（这些信息包括传进入的参数，构建中间的解和限制条件），选择继续递归或者回溯（就是递归返回）。
根据题目给出的限制条件，设计一个解的评估算法，及时排除不符合限制条件的解。
提取遍历结束条件和递归逻辑，开始编写回溯算法。

启发：

回溯法一般是先把第一步的第一种情况遍历完了之后，在遍历第一步的第二种情况。请根据例子理解。

调用递归函数时参数的变化趋势是要逼近结束条件的。

3 八皇后问题

3.1 定义

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯●贝瑟尔于1848年提出。在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即:任意两个皇后都不能处于同一行、同一列或同-斜线上。问有多少种摆法(92)。

3.2 设计回溯算法

根据2.2 设计回溯算法一般方法进行分析设计算法。

穷举法 (参照上图）
1. 我们首先在[0,0]点（第一行第一列）放置一个皇后。
2. 第二个皇后放在第二行第一列、然后判断是否0K。如果ok,则进行下一步；如果不0K, 继续放在第二列、第三列、依次把所有列都放完。
3. 继续第三个皇后，还是第一列、第二列…直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解。
4. 当栈开始进行递归返回时，就开始回溯，最终会返回到第一次调用的栈，即得到第一一个皇后，放到第一列的所有正确解。（此时所有在[0，0]的解都已经找到，开始找[0，1]点出的解）
5. 然后回头继续第- 一个皇后放第二列，后面继续循环执行1,2,3,4 的步骤,则可以找到所有的解。
此题的特定步骤即为每一层都从0开始放，放到7。重复8层即可遍历所有解。（满足重入递归）
选择合适的数据结构观察在 【1】 中我们使用[0,0]来表示放置的一个点。但进一步我们发现第一个数仅表示第几层，所以可以使用一个一维数据来表示所有解，而用数组的下标来表示在第几层。如上图的解法可表示为array[3,6,2,7,1,4,0,5]。
解的评估算法 题目限制条件，不能在同一行、同一列、同一斜线。

    //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
    /**
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        judgeCount++;
        for(int i = 0; i < n; i++) {
            // 说明
            //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
            // n = 1  放置第 2列 1 n = 1 array[1] = 1
            // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
            //3. 判断是否在同一行, 没有必要，n 每次都在递增
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
                return false;
            }
        }
        return true;
    }

编写核心的递归代码

    //编写一个方法，放置第n个皇后
    private void check(int n) {
        if(n == max) {  // 递归终止条件    当n = 8 , 其实8个皇后就已经放好（从0开始的）
            print();  //如果8个都放好了，则打印正确解（待完成）
            return;
        }
        //依次放入皇后，并判断是否冲突
        for(int i = 0; i < max; i++) {
            //先把当前这个皇后 n , 放到该行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if(judge(n)) { // 不冲突
                //接着放n+1个皇后,即开始递归
                check(n+1); //  递归参数要不断靠近终止条件， 这里n一直变大
            }
            //如果冲突，就下一步执行循环 array[n] = i+1; 即将第n个皇后，放置在本行的后一个位置，这里产生回溯。
            //特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
        }
    }

3.3 完整代码

package stack;

/**
 * created by hbl on 2020/3/18.
 */
public class Queue8 {

    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[max];
    static int count = 0;
    static int judgeCount = 0;
    public static void main(String[] args) {
        //测试一把 ， 8皇后是否正确
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法", count);
        System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w

    }



    //编写一个方法，放置第n个皇后
    private void check(int n) {
        if(n == max) {  // 递归终止条件    当n = 8 , 其实8个皇后就已经放好（从0开始的）
            print();  //如果8个都放好了，则打印正确解（待完成）
            return;
        }
        //依次放入皇后，并判断是否冲突
        for(int i = 0; i < max; i++) {
            //先把当前这个皇后 n , 放到该行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if(judge(n)) { // 不冲突
                //接着放n+1个皇后,即开始递归
                check(n+1); //  递归参数要不断靠近终止条件， 这里n一直变大
            }
            //如果冲突，就下一步执行循环 array[n] = i+1; 即将第n个皇后，放置在本行的后一个位置，这里产生回溯。
            //特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
        }
    }

    //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
    /**
     *
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        judgeCount++;
        for(int i = 0; i < n; i++) {
            // 说明
            //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
            // n = 1  放置第 2列 1 n = 1 array[1] = 1
            // Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
            //3. 判断是否在同一行, 没有必要，n 每次都在递增
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
                return false;
            }
        }
        return true;
    }

    //写一个方法，可以将皇后摆放的位置输出
    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}

4 回溯算法的其他典型应用

以下给出三个应用回溯算法的典型应用题，要掌握回溯算法，还需要积累一定的使用经验。

4.1 括号的排列组合问题

题目：给出n对括号，求括号排列的所有可能性。
如 n=3 时：有如下情况：
()()()
()(())
(())()
(()())
((()))
思路分析
1. 理解题意和给出示例，在思考时我们需要考虑暴力穷举法。首先应该画一个左括号，因为没有画左括号则不能画右括号。从数量上来说，当右括号比左括号多时，就能画一个左括号。
2. 每一步我们都尝试画一个括号，当把所有括号都用完时就结束了。
```
    if (leftNum == 0 && rightNum == 0)//结束
        results.add(sbTemp.toString());
```
1. 中间结果就是一个括号数组。可以使用StringBuffer进行存储(也可以使用String，因为当时想着可能会进行拼接，但后来发现每次都需要new ,这里涉及到引用类型的共享性问题，需要仔细体会）。（ps:用了一个ArrayList存放所有的解，一般我们都会把算好的所有正确结果存放到一个容器里，便于传递和解耦。当学习算法时其实可以直接打印出来：如八皇后的print()方法）
2. 并不是所有的算法都需要单独的评估算法，这里进入的不同if进行递归，当所有递归返回时，算法就完成了,结合1。
我们所有正确的解都是在第一次运行递归时第二个if里递归迭代出来的，因为最开始只能画一个左括号。有些题目if的顺序还有关系，但是这道题，两个if条件倒换一下，也能得出正确解。
```
    if (rightNum > leftNum)//选择和条件。 就是我们每一步选择写一个括号的逻辑。
        recrusion(new StringBuffer(sbTemp).append(')'), leftNum, rightNum - 1);
    if (leftNum > 0) // 第一个if进入后，会进入第二个if,遍历所有可能的情况。因为增加括号时，不是增加"(" 就是增加")" 两者必居其一
        recrusion(new StringBuffer(sbTemp).append('('), leftNum - 1, rightNum);
```
1. 综合分析，写出算法。

/**
* created by hbl on 2020/3/18.
*/
import java.util.ArrayList;
public class BackTracking {
  static ArrayList<String> results = new ArrayList<String>();//用于存放解空间

  public static void main(String[] args) {
      int n = 3;
      int leftNum = n, rightNum = n;//左括号和右括号都各有n个
      recrusion(new StringBuffer(), leftNum, rightNum);
      for (String s : results)
          System.out.println(s);
  }

  /**回溯算法
   * @param sbTemp 不完整解
   * @param leftNum 剩余左括号数
   * @param rightNum 剩余右括号数
   */
  public static void recrusion(StringBuffer sbTemp, int leftNum, int rightNum) {
      if (leftNum == 0 && rightNum == 0)//结束
          results.add(sbTemp.toString());
      if (rightNum > leftNum)//选择和条件。 就是我们每一步选择写一个括号的逻辑。
          recrusion(new StringBuffer(sbTemp).append(')'), leftNum, rightNum - 1);
      if (leftNum > 0) // 第一个if进入后，会进入第二个if,遍历所有可能的情况。因为增加括号时，不是增加"(" 就是增加")" 两者必居其一
          recrusion(new StringBuffer(sbTemp).append('('), leftNum - 1, rightNum);
  }
}

4.2 求给定数组和目标的排列

题目：给出一个不重复大于0数字的数组和一个目标，求数组中数的组合的和得到该目标（数字不同组合顺序当做一个解）。 example: arrays [2,3,7,6] target: 9
solutions:
2 7
7 2
3 6
6 3
这个例题给读者自行分析。

/**
 * Question:给出一个不重复大于0数字的数组和一个目标，求数组中数的组合的和得到该目标（数字不同组合顺序当做一个解）。
 * example:  arrays [2,3,7,6] target: 9
 * solutions:
 * 2 7
 * 7 2
 * 3 6
 * 6 3
 */
public class BackTracking {
    static int[] num = new int[]{2, 3, 7, 6};
    static int target = 9;

    public static void main(String[] args) {
        find(num, "");
    }

    public static void find(int[] num, String temp) {
        if (evaluate(temp, target)) {
            System.out.println(temp);
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (num[i] != -1) {//如果取过这个数字了，就置为-1
                int k = num[i];
                num[i] = -1;
                find(num, temp + k);
                num[i] = k;
            }
        }
    }

    public static boolean evaluate(String temp, int target) {
        int count = 0;
        for (int i = 0; i < temp.length(); i++) {
            count = count + temp.charAt(i) - 48;  //  char类型 '0' 的ascII 为48
        }
        return target == count;
    }
}

如果有什么错误或不足，欢迎交流 !

转载：https://blog.csdn.net/DoSmall/article/details/104943768

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章