数据结构与算法（三）——递归

一、递归的概念

递归就是方法自己调用自己，每次调用时传入不同的变量。
递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

1.1 递归机制

递归调用规则：
1>当程序执行到一个方法时，就会开辟一个独立的空间（栈）
2>每个空间的数据（局部变量）是独立的

打印问题

阶乘问题

1.2 递归需要遵守的重要规则

1、执行一个方法时，就创建一个新的受保护的独立空间（栈空间）
2、方法的局部变量是独立的，不会相互影响
3、如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据
4、递归必须向推出递归的条件逼近，否则就是无限递归
5、当一个方法执行完毕，或者遇到 return， 就会返回。谁调用就将结果返回给谁，同事当方法执行完毕或者返回时，该方法也就执行完毕。

二、 递归应用实例

1、各种数学问题，如 8皇后问题、汉诺塔、阶乘、迷宫等
2、各种算法中也会使用到递归，如快排、归并排序、二分查找、分治算法等
3、将用栈解决的问题 -> 递归代码比较简洁

2.1 迷宫回溯问题

主函数

def main(args: Array[String]): Unit = {
    //先创建一个二维数组模拟迷宫
    //地图
    val map = Array.ofDim[Int](8, 7)
    new Array[Int](2)
    //使用1表示墙
    //上下全部置为1
    for (i <- map(0).indices) {
      map(0)(i) = 1
      map(7)(i) = 1
    }
    //左右全部置为1
    for (i <- map.indices) {
      map(i)(0) = 1
      map(i)(6) = 1
    }
    //设置挡板
    map(3)(1) = 1
    map(3)(2) = 1

    //输出地图
    for (i <- map.indices) {
      for (j <- map(i).indices) {
        print(s"${map(i)(j)}\t")
      }
      println()
    }

    //使用递归回溯给小球找路
    setWay(map, 1, 1)

    //输出新的地图，小球走过，并标识过的递归
    println("======小球走过，并标识过的地图======")
    for (i <- map.indices) {
      for (j <- map(i).indices) {
        print(s"${map(i)(j)}\t")
      }
      println()
    }
  }
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

方法

使用递归回溯来给小球找路

说明：

1. map表示地图
2. i,j表示从那个位置开始(1,1)
3. 如果小球能到map[6,5]则表示小球通路找到
4. 约定：当map[i,j]
   为 0 表示该点没有走过
   为 1 表示墙
   为 2 表示通路可以走
   为 3 表示该点已经走过，但是走不通
5. 在走迷宫时，需要确定一个策略（方法） 下=>右=>上=>左 // 如果该点走不通，再回溯

  /**
   *
   * @param map 地图
   * @param i   从哪个位置开始找
   * @param j   从哪个位置开始找
   * @return 如果找到通路，就返回true，否则返回false
   */
  def setWay(map: Array[Array[Int]], i: Int, j: Int): Boolean = {
    if (map(6)(5) == 2) true //通路已经找到
    else {
      if (map(i)(j) == 0) { //如果当前这个点还没有走过
        //按照策略 下=>右=>上=>左 走
        map(i)(j) = 2 //假定该点可以走通
        map(i)(j) match {
          case _ if setWay(map, i + 1, j) => true //向下走
          case _ if setWay(map, i, j + 1) => true //向右走
          case _ if setWay(map, i - 1, j) => true //向上走
          case _ if setWay(map, i, j - 1) => true //向左走
          case _ => { //说明该点走不通，是死路
            map(i)(j) = 3
            false
          }
        }
      } else { //如果map(i)(j) != 0，可能是1，2，3
        false
      }
    }
  }
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

最短路径

说明：
1、小球得到的路径，和设置的找路策略有关。即 找路的上下左右顺序有关。
2、修改找路的策略，改成 上=>右=>下=>左
3、那么得到最短路径，我们可以把所有的策略用数组的方式表示出来，把每一个策略得到的节点进行统计，最少的集合就是最短的路径。

2.2 八皇后问题（回溯问题）

问题介绍：

在 8 × 8 格的国际象棋上摆放8个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或者统一斜线上，问有多少种摆法。

思路分析：

1、第一个皇后先放第一行第一列
2、第二个皇后放在第二行第一列、然后判断是否ok，如果不ok，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
3、继续第三个皇后，第一列、第二列……直到第8个皇后也能放在一个不冲突的位置
4、得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到。
5、然后回头继续第一个皇后放第二列，继续循环执行1，2，3步骤
【说明】理论上应该创建一个二维数组来表示棋盘，但是实际上用一个一维数组即可解决问题。

输出皇后摆放位置

  //写一个方法，可以将皇后摆放的位置输出
  def print(): Unit = {
    for (i <- array.indices) {
      printf(s"${array(i)}\t")
    }
    println()
  }
1
2
3
4
5
6
7

判断皇后是否和之前的冲突

//查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
  /**
   *
   * @param n 表示第n个皇后
   * @return
   */
  def judge(n: Int): Boolean = {
    for (i <- 0 until n) {
      //说明
      //1. array(n) == array(i) 表示判断 第n个皇后是否和前面的n-1个皇后在同一列
      //2. Math.abs(n - i) == Math.abs(array(n) - array(i)) 表示判断第n个皇后是否和第i皇后在同意斜线
      //3. 判断是否在同一行，没有必要，n每次都在递增
      if (array(n) == array(i) || Math.abs(n - i) == Math.abs(array(n) - array(i)))
        return false
    }
     true
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

放置第n个皇后

//编写一个方法，放置第n个皇后
  //注意：check 是 每一次递归时，进入到check中都有 for (i <- 0 until  max)
  def check(n: Int): Unit = {
    if (n == max) { //n=8,8个皇后已经放好
      count += 1
      print()
      return
    }
    //依次放入皇后，并判断是否冲突
    for (i <- 0 until max) {
      //先把当前皇后n放到该行的第1列
      array(n) = i
      //判断是否冲突
      if (judge(n)) {
        check(n + 1) //不冲突，开始递归
        //如果冲突，就继续执行arr(n)=i，即将第n个皇后 放置在本行的后移的一个位置
      }
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

主函数

  //定义一个max表示共有多少个皇后
  val max = 8
  //定义数组array，保存皇后放置位置的结果，比如 arr={0,4,7,5,2,6,1,3}
  val array: Array[Int] = new Array[Int](max)
  var count = 0

  def main(args: Array[String]): Unit = {
    check(0)
    println(s"一共有 ${count} 种解法")
  }
1
2
3
4
5
6
7
8
9
10