Java——递归

Stewie Lee 2024-08-29 08:35:01 阅读 61

一、递归介绍

1、什么是递归

递归在Java编程中是指一个方法调用自身的编程技巧。

<code> 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

下面为具体代码:

<code>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……

下面为具体代码:

<code>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、用递归解决猴子吃桃子

猴子每天吃一半数目的桃子,再吃一个桃子,已知第十天还没有吃,就只剩下一个桃子了。求第一天有几个桃子。

这里的规律就是前一天的桃子是后一天的桃子数加一再乘二。

<code>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博客》。

<code>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 个盘的情况

只要盘数等于一,就直接移动。最终得到以下代码:

<code>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}

以下是具体代码:

<code>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函数都会打印依次地图,会依次打印以下地图情况:

可以发现与我们分析的一致。

下面我们将地图改成以下这样,来测试回溯现象:

<code>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个解。

以下是具体代码:

<code>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个解,这里只截取部分):



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。