一、递归的概念
递归就是方法自己调用自己,每次调用时传入不同的变量。
递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。
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表示墙//上下全部置为1for (i <- map(0).indices) {map(0)(i) = 1map(7)(i) = 1}//左右全部置为1for (i <- map.indices) {map(i)(0) = 1map(i)(6) = 1}//设置挡板map(3)(1) = 1map(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()}}
方法
使用递归回溯来给小球找路
说明:
- map表示地图
- i,j表示从那个位置开始(1,1)
- 如果小球能到map[6,5]则表示小球通路找到
- 约定:当map[i,j]
为 0 表示该点没有走过
为 1 表示墙
为 2 表示通路可以走
为 3 表示该点已经走过,但是走不通- 在走迷宫时,需要确定一个策略(方法) 下=>右=>上=>左 // 如果该点走不通,再回溯
/**** @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) = 3false}}} else { //如果map(i)(j) != 0,可能是1,2,3false}}}
最短路径
说明:
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()}
判断皇后是否和之前的冲突
//查看当我们放置第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}
放置第n个皇后
//编写一个方法,放置第n个皇后//注意:check 是 每一次递归时,进入到check中都有 for (i <- 0 until max)def check(n: Int): Unit = {if (n == max) { //n=8,8个皇后已经放好count += 1print()return}//依次放入皇后,并判断是否冲突for (i <- 0 until max) {//先把当前皇后n放到该行的第1列array(n) = i//判断是否冲突if (judge(n)) {check(n + 1) //不冲突,开始递归//如果冲突,就继续执行arr(n)=i,即将第n个皇后 放置在本行的后移的一个位置}}}
主函数
//定义一个max表示共有多少个皇后val max = 8//定义数组array,保存皇后放置位置的结果,比如 arr={0,4,7,5,2,6,1,3}val array: Array[Int] = new Array[Int](max)var count = 0def main(args: Array[String]): Unit = {check(0)println(s"一共有 ${count} 种解法")}