一、递归介绍

1、什么是递归

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

    public static void foo() {
		//...
		foo();//方法调用自身
		//...
	}

2、递归用于什么场景

递归是一种常见的算法设计方法，特别适用于解决那些可以分解为相似子问题的问题。常见的递归问题包括阶乘计算、斐波那契数列、树和图的遍历等。

3、递归包含部分

一个递归方法通常由两部分组成：

1. 基准情况（Base Case）：递归过程中终止递归的条件。如果没有基准情况，递归将进入无限循环。
2. 递归步骤（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、汉诺塔

1. 目标：将所有圆盘从源柱（源杆，通常称为A）移动到目标柱（目标杆，通常称为C），并遵守以下规则。
2. 圆盘：有𝑛n个圆盘，所有圆盘大小不一，且初始状态下所有圆盘都按照从大到小的顺序叠放在源柱上。
3. 柱子：有三根柱子，分别称为源柱（A）、辅助柱（B）和目标柱（C）。
4. 移动规则：
   • 每次只能移动一个圆盘。
   • 圆盘只能放置在另一根柱子的顶部。
   • 不能将大圆盘放在小圆盘上方。

具体解释可以看我之前的文章《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）回溯算法的基本思想

回溯算法的基本思想可以概述为以下几点：

1. 尝试构建解决方案：从初始状态开始，逐步构建候选解。
2. 检测约束条件：在每一步选择后，检测当前候选解是否满足问题的约束条件。
3. 递归探索：如果当前候选解部分满足约束条件，则递归地尝试下一步选择。
4. 回溯及尝试其他选择：如果当前候选解不满足约束条件或无法继续构建有效解，则回溯到上一步，尝试其他可能的选择。
5. 终止条件：当找到一个完整且有效的解时，记录或输出解；当所有可能的选择都尝试完毕且无解时，终止搜索。

2）回溯算法的应用场景

回溯算法适用于许多经典的计算问题，包括但不限于：

• 组合问题：如八皇后问题、数独、组合和排列生成等。
• 路径查找问题：如迷宫问题、骑士巡逻问题等。
• 约束满足问题：如图着色问题、N皇后问题等。
• 子集和问题：如背包问题、部分和问题等。

3）回溯算法的一般框架

回溯算法的一般框架通常包括以下步骤：

1. 定义解空间：明确问题的解空间，以及解空间的结构。
2. 选择和约束条件：定义每一步选择的规则和约束条件。
3. 递归结构：通过递归函数构建解空间树，并在每一步选择后递归地继续尝试。
4. 回溯过程：在递归函数中进行选择、检测约束条件、递归探索、回溯及尝试其他选择。

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个解，这里只截取部分）：