首页 > 基础资料 博客日记
Java——递归
2024-09-15 23:00:07基础资料围观110次
一、递归介绍
1、什么是递归
递归在Java编程中是指一个方法调用自身的编程技巧。
public static void foo() {
//...
foo();//方法调用自身
//...
}2、递归用于什么场景
递归是一种常见的算法设计方法，特别适用于解决那些可以分解为相似子问题的问题。常见的递归问题包括阶乘计算、斐波那契数列、树和图的遍历等。
3、递归包含部分
一个递归方法通常由两部分组成：
- 基准情况（Base Case）：递归过程中终止递归的条件。如果没有基准情况，递归将进入无限循环。
- 递归步骤（Recursive Step）：将问题分解为一个或多个子问题，并调用自身处理这些子问题。
4、递归的优点和缺点
优点：
- 代码简洁：递归可以使代码更简洁和易读，特别是对于那些自然递归的问题（如树遍历）。
- 自然性：某些问题（如组合数学中的问题）自然适合递归解决。
缺点：
- 性能问题：递归可能导致较大的栈消耗，特别是在递归深度较深时，可能引发栈溢出错误（StackOverflowError）。
- 复杂性：对于某些问题，递归可能导致重复计算，效率较低；需要进行优化（如使用记忆化或动态规划）。
二、递归详细解释
1、递归详细解释
下面我们用以下例子来介绍递归：
public class Test {
public static void test(int n) {
if(n > 0) {
test(n - 1);
}
System.out.println(n);
}
public static void main(String[] args) {
test(2);
}
}首先是主函数调用 test 方法，传入的参数是 2。这时就会开辟一个 test 函数栈帧，这里的参数 n 值为 2。
然后这里的 test 函数开始依次执行它的方法体的语句，首先就是判断 n > 0，如果 n > 0 为真就调用 test(2 - 1)，可以发现这里 n > 0 为真，所以接着调用 test(2 - 1)，即调用 test(1)， 然后就是开辟下一个 test 函数的栈帧，这里的参数为 1。
然后这里的 test 函数还是要开始依次执行它的方法体的语句，首先还是判断 n > 0，如果 n > 0 为真就调用 test(1 - 1)，可以发现这里 n > 0 为真，所以接着调用 test(1 - 1)，即调用 test(0)， 然后就是开辟下一个 test 函数的栈帧，这里的参数为 0。
然后这个参数为 0 的 test 方法还是依次执行方法体的语句，这次 n > 0 为假，所以不再调用 test 方法，执行后面的语句 System.out.println(n); 显示这时 n 的值，我们将在左下角显示。
在这个语句执行完毕后，这个参数为 0 的 test 方法就完成了调用，这个方法就会返回，
然后这个函数栈帧就会被销毁：
然后上面的函数返回就到了参数为 1 的 test 方法方法体内，接下来还会接着执行后面未执行的语句 System.out.println(n); 会打印这时 n 的值，为 1。
在执行过这个语句后，参数为 1 的 test 方法就完成了调用，它也将返回，然后栈帧被销毁。然后就返回到参数为 2 的 test 方法方法体内，接着执行未执行的语句，打印这时的 n 的值，打印 2。
在执行完成这个语句后，参数为 2 的 test 方法也会返回，然后它的栈帧也会被销毁。
最终 main 函数也返回，最终程序结束。
最终的运行结果为：
这张图中的粉色箭头就代表递进，蓝色箭头就代表归来，所以合称递归。
2、递归求阶乘
一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。
例如：
5! = 5 * 4 * 3 * 2 * 1 = 120
下面为具体代码：
public class Test {
public static int factorial(int n) {
if(n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
System.out.println("5! = " + factorial(5));
}
}运行结果：
下面我们详细解释一下：
显然，阶乘是可以一点点将较为复杂的问题转换为一个个较基础的问题的。
可以发现这个递归方法求阶乘就是将数字依次递减一，当数字减到 1 时，函数归来，从 1 依次乘到这个数字，最终得到阶乘的结果。
3、递归注意事项
我们可以看到递归会在栈区开辟很多空间，如果递归没有结束条件，就会一直开辟空间，最终会造成栈溢出（Stack Overflow），导致程序崩溃。
所以递归一定要有结束条件，二且要不断逼近结束条件。
三、递归使用实例
1、使用递归求斐波那契数列
斐波那契数列（Fibonacci sequence）是一个著名的数列，其定义基于以下递推关系：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
这一数列由意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）在研究兔子的繁殖问题时引入，因此也被称为“兔子数列”。
其数值为：1、1、2、3、5、8、13、21、34……
下面为具体代码：
public class Test {
public static int fibonacci(int n) {
if(n == 0) {
return 0;
} else if(n == 1) {
return 1;
}else {
return (fibonacci(n - 2) + fibonacci(n - 1));
}
}
public static void main(String[] args) {
for(int i = 1; i <= 10; i++) {
System.out.println("第" + i + "项为 " + fibonacci(i));
}
}
}运行结果：
下面为图解，用以 4 为参数调用 fibonacci 方法为例：
2、用递归解决猴子吃桃子
猴子每天吃一半数目的桃子，再吃一个桃子，已知第十天还没有吃，就只剩下一个桃子了。求第一天有几个桃子。
这里的规律就是前一天的桃子是后一天的桃子数加一再乘二。
public class Test {
//day为还剩1个桃子的天数，n是要求有几个桃子的天数
public static int foo(int day,int n) {
if(n == day) {
return 1;
}
return (foo(day,n + 1) + 1) * 2;
}
public static void main(String[] args) {
System.out.println(foo(10,1));//第10天还有1个桃子，要求第1天有几个桃子
}
}运行结果：
下面为具体图解：
3、汉诺塔
- 目标：将所有圆盘从源柱（源杆，通常称为A）移动到目标柱（目标杆，通常称为C），并遵守以下规则。
- 圆盘：有𝑛n个圆盘，所有圆盘大小不一，且初始状态下所有圆盘都按照从大到小的顺序叠放在源柱上。
- 柱子：有三根柱子，分别称为源柱（A）、辅助柱（B）和目标柱（C）。
- 移动规则：
- 每次只能移动一个圆盘。
- 圆盘只能放置在另一根柱子的顶部。
- 不能将大圆盘放在小圆盘上方。
具体解释可以看我之前的文章《C语言——递归-CSDN博客》。
public class Test {
public static void hanoiTower(int num, String col1, String col2, String col3) {
if(num == 1) {//如果只有一个盘，直接移动
System.out.println(col1 + "->" + col3);
} else {
hanoiTower(num - 1, col1, col3, col2);
System.out.println(col1 + "->" + col3);
hanoiTower(num - 1, col2, col1, col3);
}
}
public static void main(String[] args) {
hanoiTower(3, "源柱", "辅助柱", "目的柱");
}
}运行结果：
可以发现这是最佳解法，与下面的步骤图一致。
对于上面的代码，我们开始详细介绍一下：
就是汉诺塔可以逐步拆解成一个个小问题：
就像上面的三个盘的情况，我们可以拆解成先将最上面的两个盘移动到辅助柱（中间步骤省略），然后将最底下的盘移动到目的柱，然后再将辅助柱上的两个盘移动到目的柱上（中间步骤省略）。
可以发现这里的三个盘的情况就分解成了
一个盘的情况就可以直接移动到目标盘了。
然后我们看两个盘的情况：
可以发现两个盘的情况就变成了三个一个盘的情况：
这里我们就发现了规律，只要盘数 n 大于一，就将它分解成：
一次 n - 1 个盘的情况
一次 1 个盘的情况
一次 n - 1 个盘的情况
只要盘数等于一，就直接移动。最终得到以下代码：
public class Test {
public static void hanoiTower(int num, String col1, String col2, String col3) {
if(num == 1) {//如果只有一个盘，直接移动
System.out.println(col1 + "->" + col3);
} else {
//借助col3，将col1上面的n-1个盘移动到col2
hanoiTower(num - 1, col1, col3, col2);
//将col1最底的一个盘移动到col3
System.out.println(col1 + "->" + col3);
//借助col1，将col2上面的n-1个盘移动到col3
hanoiTower(num - 1, col2, col1, col3);
}
}
public static void main(String[] args) {
hanoiTower(3, "源柱", "辅助柱", "目的柱");
}
}四、回溯算法
1、回溯算法介绍
回溯算法是一种系统化地搜索问题解空间的方法，主要用于解决组合优化问题。它通过递归地构建候选解，并在发现候选解不满足问题条件时回溯，从而尝试其他可能的选择。回溯算法的核心思想是不断尝试和撤销选择，直到找到所有可能的解决方案或者确认无解。
1）回溯算法的基本思想
回溯算法的基本思想可以概述为以下几点：
- 尝试构建解决方案：从初始状态开始，逐步构建候选解。
- 检测约束条件：在每一步选择后，检测当前候选解是否满足问题的约束条件。
- 递归探索：如果当前候选解部分满足约束条件，则递归地尝试下一步选择。
- 回溯及尝试其他选择：如果当前候选解不满足约束条件或无法继续构建有效解，则回溯到上一步，尝试其他可能的选择。
- 终止条件：当找到一个完整且有效的解时，记录或输出解；当所有可能的选择都尝试完毕且无解时，终止搜索。
2）回溯算法的应用场景
回溯算法适用于许多经典的计算问题，包括但不限于：
- 组合问题：如八皇后问题、数独、组合和排列生成等。
- 路径查找问题：如迷宫问题、骑士巡逻问题等。
- 约束满足问题：如图着色问题、N皇后问题等。
- 子集和问题：如背包问题、部分和问题等。
3）回溯算法的一般框架
回溯算法的一般框架通常包括以下步骤：
- 定义解空间：明确问题的解空间，以及解空间的结构。
- 选择和约束条件：定义每一步选择的规则和约束条件。
- 递归结构：通过递归函数构建解空间树，并在每一步选择后递归地继续尝试。
- 回溯过程：在递归函数中进行选择、检测约束条件、递归探索、回溯及尝试其他选择。
2、回溯算法实例
回溯算法本质上是一种深度优先搜索（DFS）。
1）老鼠走迷宫
老鼠走迷宫，起点为左上角，终点为右下角，老鼠上下左右走动。0 代表空地，1 代表墙。
{1,1,1,1,1,1,1},
{1,0,0,0,0,0,1},
{1,0,0,0,0,0,1},
{1,1,1,1,0,0,1},
{1,0,0,1,0,0,1},
{1,0,0,1,0,0,1},
{1,0,0,0,0,0,1},
{1,1,1,1,1,1,1}
以下是具体代码：
public class Test {
//假设1是障碍，0可走，2为找到的通路，3为走过不通
public static boolean findWay(int[][] map, int row, int col) {
if(map[6][5] == 2) {//终点为2则可达到终点
return true;
} else {//终点不是2则接着找路
if(map[row][col] == 0) {//当前的位置为0才可继续走
map[row][col] = 2;//当前位置是0，现在假设可以通过当前位置，把当前位置设为2
if(findWay(map, row + 1, col)) {//尝试向下走，如果向下走可以，则返回真
return true;
} else if(findWay(map, row, col + 1)) {//尝试向右走，如果向右走可以，则返回真
return true;
} else if(findWay(map, row - 1, col)) {//尝试向上走，如果向上走可以，则返回真
return true;
} else if(findWay(map, row, col - 1)) {//尝试向左走，如果向左走可以，则返回真
return true;
} else {//上下左右都不可以走，将此处设为3，表示走过但走不通，然后回溯
map[row][col] = 3;
return false;
}
} else {//当前位置不是0，则回溯
return false;
}
}
}
public static void printMap(int[][] map) {
for(int i = 0; i < map.length; i++) {
for(int j = 0; j < map[i].length; j++) {
if(map[i][j] == 1) {
System.out.printf("\033[48;5;19m \033[0m");
} else if(map[i][j] == 2) {
System.out.printf("\033[48;5;22m \033[0m");
} else {
System.out.printf(" ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] map = {
{1,1,1,1,1,1,1},
{1,0,0,0,0,0,1},
{1,0,0,0,0,0,1},
{1,1,1,1,0,0,1},
{1,0,0,1,0,0,1},
{1,0,0,1,0,0,1},
{1,0,0,0,0,0,1},
{1,1,1,1,1,1,1}
};
boolean res = findWay(map, 1, 1);
if(res) {
printMap(map);
} else {
System.out.println("未找到");
}
}
}运行结果：
可以发现路径是正确的，下面我们进行详细解释：
首先第一步在主函数调用的 findWayj(map, 1, 1)，执行到 map[row][col] = 2 这句时，（1,1）位置就被设为了2，
当这个函数执行到上图绿色箭头所指的语句时就会调用 findWay(map, 2, 1)，然后 findWay(map, 2, 1) 会接着执行下面的语句，执行到 map[row][col] = 2 这句时，也会将（2,1）的值设为 2，
然后 findWay(map, 2, 1) 执行到上图中绿色箭头所指的语句时，又会调用 findWay(map, 3, 1)：
然后 findWay(map, 3, 1) 执行内部代码块，发现执行到上图中的绿色箭头指向的语句，发现条件不满足，就会跳到淡蓝色箭头指向的else语句，然后return false；
这时 findWay(map, 3, 1) 函数就返回了，且返回值为false，
然后 findWay(map, 2, 1) 接着执行，因为 findWay(map, 3, 1) 返回的是false，所以 if 后括号的条件语句为假，所以接着尝试else if 中的语句，所以接着调用 findWay(map, 2, 2)，
然后 findWay(map, 2, 2) 接着执行语句，执行到 map[row][col] = 2 语句时，（2,2）的值会被设为2，执行到下图中的绿色箭头指向的语句时，
又会调用 findWay(map, 3, 2) ，然后会发现又会执行else 中的语句块，因为（3,2）这个位置是墙，然后这个函数返回，
接着就是 findWay(map, 2, 2) 接着尝试向右走，调用 findWay(map, 2, 3)，
然后执行的 map[row][col] = 2 语句让（2,3）的值设为2，然后执行到上图的绿色箭头指向的位置时，又会调用 findWay(map, 3, 3)，但是因为（3,3）位置是墙，所以 findWay(map, 3, 3) 又会返回false ：
由于返回的是false，所以 findWay(map, 2, 3) 会接着尝试向右走，则会调用 findWay(map, 2, 4)，然后执行到 map[row][col] = 2 语句让（2,4）的值设为2，
然后 findWay(map, 2, 4) 会执行语句，到上图中绿色箭头指的语句时，又会调用 findWay(map, 3, 4)，由于接下来向下走会连续几次，这里稍微跳跃一下，接下来会依次调用 findWay(map, 4, 4) ，findWay(map, 5, 4) ，findWay(map, 6, 4)，
然后直到 findWay(map, 7, 4) 就会再次返回，因为（7,4）这里是墙，这时 findWay(map, 6, 4) ，就会尝试向右走， 就会调用 findWay(map, 6, 5)，然后执行到 map[row][col] = 2 语句让（6,5）的值设为2，
然后执行到上图的绿色箭头指向的语句，就会调用 findWay(map, 7, 5)，
可以发现 findWay(map, 7, 5) 在执行第一个语句时，会判断 map[6][5] == 2 这个条件，可以发现这个条件是满足的，所以 findWay(map, 7, 5) 会返回 true ，
由于 findWay(map, 7, 5) 返回的是 true ，所以 if 中的条件表达式为真，所以 findWay(map, 6, 5) 会执行return true，也就是返回 true ，
由于 findWay(map, 6, 5) 返回的是 true 所以 findWay(map, 6, 4) 这里的else if 的条件表达式为真，所以 findWay(map, 6, 4) 也会返回 true，后面的函数会依次返回true，然后导致前一个函数也返回true，到最后 findWay(map, 1, 1) 返回true 这个递归就结束了，然后
res 的值为 true 所以打印具体的路径。
如果我们将打印语句放到findWay函数的第一个语句处，也就是每次调用findWay函数都会打印依次地图，会依次打印以下地图情况：
可以发现与我们分析的一致。
下面我们将地图改成以下这样，来测试回溯现象：
public class Test {
//假设1是障碍，0可走，2为找到的通路，3为走过不通
public static boolean findWay(int[][] map, int row, int col) {
if(map[6][5] == 2) {//终点为2则可达到终点
return true;
} else {//终点不是2则接着找路
if(map[row][col] == 0) {//当前的位置为0才可继续走
map[row][col] = 2;//当前位置是0，现在假设可以通过当前位置，把当前位置设为2
if(findWay(map, row + 1, col)) {//尝试向下走，如果向下走可以，则返回真
return true;
} else if(findWay(map, row, col + 1)) {//尝试向右走，如果向右走可以，则返回真
return true;
} else if(findWay(map, row - 1, col)) {//尝试向上走，如果向上走可以，则返回真
return true;
} else if(findWay(map, row, col - 1)) {//尝试向左走，如果向左走可以，则返回真
return true;
} else {//上下左右都不可以走，将此处设为3，表示走过但走不通，然后回溯
map[row][col] = 3;
return false;
}
} else {//当前位置不是0，则回溯
return false;
}
}
}
public static void printMap(int[][] map) {
for(int i = 0; i < map.length; i++) {
for(int j = 0; j < map[i].length; j++) {
if(map[i][j] == 1) {
System.out.printf("\033[48;5;19m \033[0m");
} else if(map[i][j] == 2) {
System.out.printf("\033[48;5;22m \033[0m");
} else if(map[i][j] == 3){
System.out.printf("\033[48;5;160m \033[0m");
} else{
System.out.printf(" ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] map = {
{1,1,1,1,1,1,1},
{1,0,0,0,0,0,1},
{1,0,1,0,0,0,1},
{1,1,1,1,0,0,1},
{1,0,0,1,0,0,1},
{1,0,0,1,0,0,1},
{1,0,0,0,0,0,1},
{1,1,1,1,1,1,1}
};
boolean res = findWay(map, 1, 1);
if(res) {
printMap(map);
} else {
System.out.println("未找到");
}
}
}再次运行代码的结果为：
这里的红色方块就是回溯导致的，就是当走到（2,1）的位置时，会依次尝试向下，向右，向上，向左走，
就是图中的四个绿色箭头所指的，但是发现这四个方位都不能走通，然后就会执行else中的语句：
将（2,1）这个位置的值设为3，然后返回false，这个现象就是回溯。
2）八皇后问题
八皇后问题（Eight Queens Problem）是一个经典的组合优化问题。该问题的目标是在一个8×8的国际象棋棋盘上放置8个皇后，使得任何两个皇后都不能互相攻击。根据国际象棋的规则，皇后可以在水平、垂直和对角线上移动，因此放置的皇后不能位于同一行、同一列或同一对角线上。
八皇后问题总共有92个解。
以下是具体代码：
public class EightQueen {
private int count;//计数，第几个解法
//求解方法，会依次找到每一个方法，找到一个方法后，会返回然后接着找其他方法
public void solve(int[][] arr, int row) {
if(row == 8) {//行数等于8则代表完成了摆放
printArr(arr);//打印摆放的解法，这里每次找到解都会打印，总计会打印92个解
return ;//row为8的这个函数栈帧返回，接下来还会再其它的函数栈帧中接着寻找其他解法
}
for(int col = 0; col < arr[row].length; col++) {
if(isValid(arr, row, col)) {//检查当前位置是否合法
arr[row][col] = 1;//当前位置合法，将皇后放下
solve(arr, row + 1);//尝试下一行的放法
}
arr[row][col] = 0;//将此位置设为0，重置状态，后面无论上面的尝试下一行能不能找到结果，都会重置，
//找到结果还会重置，则是实现了可以将92个解依次找出的情形
}
}
//检查是否合法，也就是检查是否与前面的棋子冲突
public boolean isValid(int[][] arr, int row, int col) {
//
//
//
// *
// | | |
// | | |
// | | |
//| |
// *为当前位置，*上面的是没有放置的行，不用检查，
// |为需要检查的位置，检查是否有同列的，检查是否有同一个主对角线的，检查是否有同一个副对角线的
//检查是否有同列的
for(int i = 0; i < row; i++) {//遍历之前行的当前列，查找是否有同列的皇后
if(arr[i][col] == 1) {//如果有同列的皇后，则返回false
return false;
}
}
//检查是否有同一个主对角线的
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(arr[i][j] == 1) {
return false;
}
}
//检查是否有同一个副对角线的
for(int i = row - 1, j = col + 1; i >= 0 && j < 8; i--, j++) {
if(arr[i][j] == 1) {
return false;
}
}
return true;//上面的都满足，则不与前面的皇后冲突
}
//打印解法，即打印这个二维数组
public void printArr(int[][] arr) {
count++;
System.out.println("第" + count +"种解法为：");
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr[i].length; j++) {
if(arr[i][j] == 1) {
System.out.print("\033[48;5;160m \033[0m");
} else {
System.out.print("\033[48;5;39m \033[0m");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] arr = new int[8][8];//创建一个二维数组，默认初始化为0
EightQueen eightQueen = new EightQueen();
eightQueen.solve(arr,0);
}
}运行结果（因为会打印整整92个解，这里只截取部分）：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！
标签：
上一篇：后端之路——阿里云OSS云存储
下一篇：左叶子之和-404
相关文章
最新发布
点击排行
本站推荐
