递归
1. 含义
递归：函数（方法）直接或间接调用自身
2. 调用过程
如果递归调用没有终止，将会一直消耗栈空间 最终导致栈内存溢出（Stack Overflow） 所以必需要有一个明确的结束递归的条件 也叫作边界条件、递归基
3. 基本思想
1. 拆解
把规模大的问题变成规模较小的同类型问题
规模较小的问题又不断变成规模更小的问题
规模小到一定程度可以直接得出它的解
2.求解
由最小规模问题的解得出较大规模问题的解
由较大规模问题的解不断得出规模更大问题的解
最后得出原来问题的解
3.总结
凡是可以利用上述思想解决问题的，都可以尝试使用递归
很多链表、二叉树相关的问题都可以使用递归来解决因为链表、二叉树本身就是递归的结构
4. 使用套路
① 明确函数的功能
首先搞清楚这个函数的干嘛用的，能完成什么功能？
② 明确原问题与子问题的关系
先不要去思考里面代码怎么写
寻找 f(n) 与 f(n – 1) 的关系
③ 明确递归基（边界条件）
递归的过程中，子问题的规模在不断减小，当小到一定程度时可以直接得出它的解
寻找递归基，相当于是思考：问题规模小到什么程度可以直接得出解？
5.练习题目
练习1 - 斐波那契数列
斐波那契数列：1、1、2、3、5、8、13、21、34、······ 发现： F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n≥3） int fib(int n) {
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}缺点：出现了特别多的重复计算
优化一：记忆化
用数组存放计算过的结果，避免重复计算 int fib(int n) {
if (n <= 2) return 1;
int[] array = new int[n + 1];
array[1] = array[2] = 1;
for (int i = 3; i <= n; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}优化二：变量存储
用两个变量存储值，第二个即为结果
int fib5(int n) {
if (n <= 2) return 1;
int first = 1,second = 1;
for(int i = 3; i <= n; i++) {
second = first + second;
first = second - first;
}
return second;
}练习2 - 上楼梯
楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？
假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法
✓ 如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法
✓ 如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法
所以 f(n) = f(n – 1) + f(n – 2)
递推式与跟斐波那契数列几乎一样，但边界条件不同
int climbStairs(int n) {
if (n <= 2) return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}练习3 - 汉诺塔
把 A 的 n 个盘子移动到 C（盘子编号是 [1, n] ） 每次只能移动1个盘子 大盘子只能放在小盘子下面
有 2 种情况：
当 n == 1时，直接将盘子从 A 移动到 C
当 n > 1时，可以拆分成3大步骤
① 将 n – 1 个盘子从 A 移动到 B ② 将编号为 n 的盘子从 A 移动到 C ③ 将 n – 1 个盘子从 B 移动到 C✓ 步骤 ① ③ 明显是个递归调用
// 将 n 个盘子从 A 挪动到 C
void hanoi(int n, String A, String B, String C) {
if (n == 1) {
move(n, A, C);
return;
}
// 将n上面的n - 1个盘子从A挪到B
hanoi(n - 1, A, C, B);
// 把第n个盘子从A挪到C
move(n, A, C);
// 最后将B的n - 1个盘子挪到C上
hanoi(n - 1, B, A, C);
}
void move(int no, String from, String to) {
System.out.println("将" + no + "号盘子从" + from + "移动到" + to);
}回溯
1. 含义
通过选择不同的岔路口来通往目的地（找到想要的结果）
每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试
2. 练习 - 八皇后问题
在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击：任意两个皇后都不能处于同一行、同一列、同一斜线上请问有多少种摆法？
回溯 + 剪枝
// 数组索引是行号，数组元素是列号
int[] cols;
// 一共有多少种摆法
int ways;
// 放置n个皇后
void placeQueens(int n) {
if (n < 1) return;
cols = new int[n];
place(0);
System.out.println(n + "皇后一共有" + ways + "种摆法");
}
// 从第row行开始摆放皇后
void place(int row) {
// 到达最后一行的下一行
if (row == cols.length) {
ways++;
return;
}
// 遍历每一行的所有格子，在循环中发生回溯
for (int col = 0; col < cols.length; col++) {
if (isValid(row, col)) {
// 在第row行第col列摆放皇后
cols[row] = col;
place(row + 1);
// 回溯发生在这
}
}
}
// 判断第row行第col列是否可以摆放皇后
boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
// 第col列已经有皇后
if (cols[i] == col) {
return false;
}
// 第i行的皇后跟第row行第col列格子处在同一斜线上
if (row - i == Math.abs(col - cols[i])) {
return false;
}
}
return true;
}
}51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[["Q"]]提示：
1 <= n <= 9
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();//[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
List<Integer> path = new ArrayList<>();//[1,3,0,2] 存储第i行的皇后在第path.get(i)列
int[] chessboard = new int[n];//[1,3,0,2] 存储第i行的皇后在第chessboard[i]列
Arrays.fill(chessboard, -1);
dfs(res, path, n, 0, chessboard);
return res;
}
//棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度
public void dfs(List<List<String>> res, List<Integer> path, int n, int row, int[] chessboard) {
if(row == n) {
List<String> list = helper(path);//[1,3,0,2]->[".Q..","...Q","Q...","..Q."]
res.add(list);
return;
}
//对于index行，遍历每一列
for(int cols = 0; cols < n; cols++) {
if(!isValid(row, cols, chessboard)) continue;//判断(row,cols)能否放皇后，不能放皇后，则越过。
path.add(cols);
chessboard[row] = cols;
dfs(res, path, n, row + 1, chessboard);
path.remove(path.size() - 1);
chessboard[row] = -1;
}
}
//[1,3,0,2]->[".Q..","...Q","Q...","..Q."]
public List<String> helper(List<Integer> path) {
List<String> board = new ArrayList<>();
int n = path.size();
for(int i = 0; i < n; i++) {
char[] temp = new char[n];
Arrays.fill(temp, '.');//"...."
temp[path.get(i)] = 'Q';//".Q.."
board.add(new String(temp));
}
return board;
}
//判断(row,col)能否放皇后
public boolean isValid(int row, int col, int[] chessboard) {
//从chessboard中，取出每一个皇后，判断是否与(row,col)的皇后冲突
for(int i = 0; i < row; i++) {
//同一列
if(chessboard[i] == col) {
return false;
}
//同"/"方向
if(i + chessboard[i] == row + col) {
return false;
}
//同"\"方向
if(i - chessboard[i] == row - col) {
return false;
}
}
return true;//没有任何冲突，(row,col)可以放皇后
}
}标签：递归,int,chessboard,cols,回溯,皇后,col,row From： https://blog.csdn.net/2301_80395772/article/details/141173007