概念

递归算法是一种通过函数调用自身将问题分解为同类型的子问题来求解的算法。核心在于通过重复缩小问题规模直至达到可解的基线条件，在逐层返回结果完成原问题的求解。

基本原理

-【递去】与【归来】：通过将问题拆解成更小的相同结构的子问题，最终通过基线条件终止递归并逐层返回结果；

• 终止条件【基线条件】：必须明确的定义递归结束的边界条件，否则会导致无限递归和栈溢出（StackOverflowError）问题；

关键特征

• 简洁性：用少量代码描述复杂逻辑，如阶乘函数可通过n! = n*(n-1)!的递归定义简洁实现。
• 效率问题：可能因重复计算导致时间复杂度过高，例如斐波那契数列的递归解法效率低于迭代方法。
• 栈空间消耗：每次递归调用占用栈帧，深度过大时可能引发栈溢出。

递归的重要规则

• 递归在每次进入执行一个方法时，就会创建一个独立的受保护的栈空间
• 方法的局部变量是独立的，不会相互影响
• 如果方法中使用的是引用类型变量（如数组等）就会共享该引用类型的数据
• 递归必须向退出递归的条件靠近，否则就会无限递归（StackOverflowError）
• 当一个方法执行完毕或者执行了return，就会返回；遵守谁调用就将结果返回给谁的逻辑

应用场景

1. 数学问题

• 阶乘计算：factorial(n) = n * factorial(n-1)，基线条件为n=0时返回1。
• Ackermann函数：展示复杂递归关系，其增长速率极快。

2. 算法与数据结构

• 汉诺塔问题：通过递归实现圆盘移动的逻辑分解，时间复杂度为O(2n)。
• 文件系统遍历：递归处理嵌套目录结构，如统计文件数或搜索特定文件。

3. 组合问题

• 全排列生成：通过交换元素位置递归生成所有可能的排列组合。
• 八皇后问题：递归试探棋盘位置并回溯，寻找所有合法布局。

优化策略

• 尾递归优化：通过改写递归函数使调用成为最后一步操作，编译器可优化为迭代以避免栈溢出。
• 记忆化技术：缓存已计算子问题的结果（如使用哈希表），减少重复计算，提升效率。
• 使用递归时需平衡代码简洁性与执行效率，优先选择分治策略明显的问题场景。例如快速排序和二叉树遍天然适合递归实现，而数值计算类问题可能更适合迭代方法。

回溯算法

回溯算法是一种通过穷举和剪枝策略解决问题的通用方法，核心思想是通过试错和回退在解空间中搜索可行解或最优解。该算法通常采用深度优先搜索策略，结合剪枝函数减少无效搜索，适用于组合、排列、子集等复杂问题

代码案例

• 八皇后问题

package com.algorithm;

/**
 * 八皇后问题
 * 在 8 * 8的目标棋盘上放置8个皇后，使她们不能相互攻击（皇后可以攻击同一列、同一对角线上的其他棋子）
 * 解决思路：
 * 1. 初始化 8 * 8的棋盘，设置所有格子为空（0 替代 ）
 * 2. 放置第一个皇后，在第一行开始放置皇后位置，依次拜访第N行的皇后，保证已摆放的换后不能相互攻击
 * 3. 逻辑判断（冲突判断）
 *   if 摆放的皇后和之前的皇后相互攻击
 *      if 第N行还有后续位置，则尝试第N行的下一个位置进行摆放
 *      if 第N行的所有位置都尝试过摆放并且产生冲突，则返回第N-1行，继续处理下一个摆放位置
 *   else 摆放到第N行后，摆放的所有皇后没有冲突（不能互相攻击），则为一组解
 */
public class EightQueens {
    static int count = 0;
    static int checkCount = 0;
    int size = 8;
    //初始化棋盘
    boolean [][]board = new boolean[size][size];
    //记录皇后位置
    int []queens = new int[size];

    public static void main(String[] args) {

        EightQueens queensSolver = new EightQueens();
        queensSolver.placeQueen(0); // 开始解决八皇后问题
        System.out.println("检查："+checkCount+"次");
        System.out.println("共有："+count+"种放置方式");
    }

    /**
     * 皇后冲突检查
     * 同一列、同一对角线（左右）
     * 右对角线检查 两个皇后位置的坐标和相等： col + row
     * 左对角线检查 两个皇后位置的坐标差相等： col - row
     */
    private boolean isSafe(int row, int col) {
        checkCount ++;
        for (int i = 0; i < row; i++) {
            if (queens[i] == col //列检查
                    || queens[i] + i == col + row   //右对角线检查
                    || queens[i] - i == col - row)  //左对角线检查
            {
                return false;
            }
        }
        return true;
    }

    /**
     * 递归放置皇后
     */
    private boolean placeQueen(int row) {
        //皇后放置完毕检查
        if( row == size){
            printBoard();
            count++;
            return true;
        }
        //在第row行循环方式皇后，并检查冲突
        for (int col = 0; col < size; col++) {
            if(isSafe(row, col)){
                //记录皇后位置
                queens[row] = col;
                //放置皇后
                board[row][col] = true;
                //递归下一个放置皇后的位置
                if(placeQueen(row + 1)){
                    //未检查出冲突 placeQueen() 开始下一次尝试
                    continue;
                }
            }
            //检查到冲突，重置棋盘皇后标记
            board[row][col] = false;
        }

        return false;   //没找到合适的位置摆放皇后，回溯到上一级
    }

    /**
     * 打印棋盘
     */
    private void printBoard() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (board[i][j]) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

}