S01-08 基础-递归

[TOC]

概述

什么是递归

~~递归（Recursion）~~：是指方法在执行过程中直接或间接调用自身的编程方式，用于解决满足以下条件的问题：

问题可拆解为规模更小的同类子问题（子问题与原问题逻辑一致）；
存在终止条件（当问题规模缩小到一定程度时，无需递归直接返回结果）。

~~递归能解决的问题~~：

数学问题：阶乘、斐波那契数列、汉诺塔、八皇后、球和篮子问题。
算法问题：快排、归并排序、二分查找、分治算法。
栈相关问题：迷宫路径查找。

本质：分治思想

~~递归的核心~~：是 “分而治之”：将大问题拆解为多个小问题，逐个解决小问题后，合并结果得到原问题的解。例如：

计算 n!（n 的阶乘）：n! = n * (n-1)!，子问题是 (n-1)!，终止条件是 0! = 1；
遍历二叉树：先递归遍历左子树，再处理当前节点，最后递归遍历右子树，终止条件是 “节点为 null”。

工作原理

Java 中方法调用通过方法栈（栈帧） 实现，~~递归调用的本质~~是栈帧的 “压栈” 与 “出栈” 过程：

压栈（递归调用）：每次调用方法时，JVM 会创建新的栈帧（存储方法的参数、局部变量、返回地址），并压入栈顶；
出栈（递归返回）：当方法执行到终止条件或完成逻辑时，栈帧弹出，返回结果给上一层调用者，直到栈为空（回到最初的调用方法）。

~~示例：阶乘递归的栈帧变化~~

以 factorial(3) 为例，逐步解析栈的变化：

java

// 阶乘递归方法
public static int factorial(int n) {
    if (n == 0) return 1; // 终止条件
    return n * factorial(n-1); // 递归调用
}

内存流程图与栈帧变化：

ℹ️步骤 1/20:

优缺点

优点：

代码简洁：无需手动管理循环逻辑，直接映射问题的数学模型或逻辑结构（如树遍历）；
逻辑清晰：符合人类 “分治” 思维，便于理解和维护；
适用场景广：天然适配树、图、分治算法（如归并排序、快速排序）。

缺点：

栈溢出风险：递归深度过大时，方法栈会不断压栈，超出 JVM 栈容量（默认约 1MB），抛出 StackOverflowError；
重复计算：如原生斐波那契数列递归，会重复计算大量子问题（如 fib(5) 需计算 fib(4) 和 fib(3)，fib(4) 又需计算 fib(3)，导致时间复杂度 O (2ⁿ)）；
效率较低：方法调用有额外的栈帧开销（压栈、出栈、参数传递），比迭代效率低。

注意事项

必须明确终止条件：且终止条件需能被触发（如 n 逐步递减到 0，而非递增）；
控制递归深度：避免深度过大（如超过 1000 层），优先用迭代或记忆化搜索；
避免重复计算：复杂递归问题优先考虑缓存（记忆化搜索）；
处理非法输入：如阶乘的 n<0、斐波那契的 n，需抛出异常或返回默认值；
警惕对象引用共享：递归方法中若使用全局变量或共享对象，需注意线程安全和状态污染（优先用局部变量传递状态）。

核心要素

递归的正确执行依赖两个不可缺少的要素，缺少任何一个都会导致程序异常（死循环、栈溢出）：

终止条件：当问题规模缩小到某个临界值时，直接返回结果，不再递归调用。
递归步骤：将原问题拆解为规模更小、逻辑相同的子问题，通过调用自身解决子问题。

终止条件

~~终止条件~~：当问题规模缩小到某个临界值时，直接返回结果，不再递归调用；

作用：阻止方法无限调用自身，避免栈溢出（StackOverflowError）；

示例：阶乘的 n==0、斐波那契数列的 n==1 || n==2、树遍历的 node==null。

错误示例（无终止条件）：

java

// 无终止条件，会无限递归导致栈溢出
public static int badRecursion(int n) {
    return n + badRecursion(n-1);
}

递归步骤

~~递归步骤~~：将原问题拆解为规模更小、逻辑相同的子问题，通过调用自身解决子问题；

要求：子问题必须 “逐步逼近” 终止条件（否则仍会无限递归）；

示例：n! = n * (n-1)!（子问题 (n-1)! 的规模比 n! 小 1，逐步逼近 n=0）。

常见应用场景

递归适用于 “问题可分治、结构有自相似性” 的场景，以下是 Java 中最典型的应用：

数学问题

打印问题

java

/** 打印问题 */
public void test(int n) { 
    if (n > 2) {
        test(n - 1); // 递归调用
    }
    System.out.println("n=" + n);
}

test(4); // 输出：n=2，n=3，n=4

~~内存流程图~~：

ℹ️步骤 1/18:

阶乘计算

java

public class FactorialDemo {
    public static int factorial(int n) {
        // 终止条件：n<0抛异常，n=0返回1
        if (n < 0) throw new IllegalArgumentException("n不能为负数");
        if (n == 0) return 1;
        // 递推关系
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 120
    }
}

~~内存流程图~~：

ℹ️步骤 1/20:

斐波那契数列

java

/**
 * 斐波那契数列：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)
 * 注意：原生递归存在大量重复计算，下文会优化
 */
public static int fibonacci(int n) {
    if (n <= 0) throw new IllegalArgumentException("n 必须大于 0");
    // 终止条件
    if (n == 1 || n == 2) return 1;
    // 递归步骤
    return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(5) // 1 1 2 3 5

~~内存流程图~~：

ℹ️步骤 1/24:

数据结构操作

二叉树的前序遍历

java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

/**
 * 二叉树前序遍历：递归版
 */
public static void preOrderTraversal(TreeNode node) {
    // 终止条件：节点为 null 时返回
    if (node == null) return;
    // 处理当前节点
    System.out.print(node.val + " ");
    // 递归遍历左子树
    preOrderTraversal(node.left);
    // 递归遍历右子树
    preOrderTraversal(node.right);
}

// 调用：preOrderTraversal(root) → 输出根、左子树、右子树节点值

数组翻转

思路分析：

代码实现：

链表反转

java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

/**
 * 链表反转：递归版
 */
public static ListNode reverseList(ListNode head) {
    // 终止条件：空链表或只有一个节点，直接返回自身
    if (head == null || head.next == null) return head;
    // 递归反转后续链表，得到反转后的头节点
    ListNode newHead = reverseList(head.next);
    // 调整当前节点与下一个节点的指向
    head.next.next = head;
    head.next = null;
    // 返回反转后的头节点
    return newHead;
}

文件目录遍历

java

import java.io.File;

/**
 * 递归遍历指定目录下的所有文件（包括子目录）
 */
public static void traverseDirectory(File dir) {
    // 终止条件：不是目录或目录不存在
    if (!dir.exists() || !dir.isDirectory()) return;
    // 获取目录下的所有文件/子目录
    File[] files = dir.listFiles();
    if (files == null) return; // 防止权限问题导致的 null
    // 遍历每个文件/子目录
    for (File file : files) {
        if (file.isDirectory()) {
            // 子目录：递归遍历
            traverseDirectory(file);
        } else {
            // 文件：输出路径
            System.out.println("文件路径：" + file.getAbsolutePath());
        }
    }
}

// 调用：traverseDirectory(new File("D:/test")) → 遍历 D:/test 下所有文件

经典递归问题

猴子吃桃

问题：猴子第一天吃了桃子的一半多 1 个，以后每天吃剩下的一半多 1 个，第 5 天剩 1 个桃子。求最初桃子总数。

思路（逆推）：

第 5 天：1 个
第 4 天：(1+1)×2=4 个
第 3 天：(4+1)×2=10 个
规律：前一天桃子数 = (后一天桃子数 + 1)×2

java

public class RecursionExercise01 {
    public int peach(int day) {
        if (day == 5) {
            return 1; // 终止条件（第5天剩1个）
        } else if (day >= 1 && day <= 9) {
            return (peach(day + 1) + 1) * 2; // 递归调用（逆推）
        } else {
            System.out.println("day必须在[1,10]之间");
            return -1;
        }
    }

    public static void main(String[] args) {
        int day = 1;
        int peachNum = peach(day);
        if (peachNum != -1) {
            System.out.println("第" + day + "天有" + peachNum + "个桃子"); // 输出1534
        }
    }
}

~~内存流程图~~：

ℹ️步骤 1/17:

迷宫问题

问题：用二维数组表示迷宫，0 表示可走，1 表示障碍物，2 表示已走通，3 表示死路。使用递归回溯找通路。

java

public class MazeRecursion {
    // 1. 构建迷宫：8行7列，1=墙，0=通路
    public static int[][] createMaze() {
        int[][] maze = new int[8][7];
        // 初始化所有位置为0（通路）
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                maze[i][j] = 0;
            }
        }
        // 构建上下边界（墙）
        for (int j = 0; j < 7; j++) {
            maze[0][j] = 1; // 第一行
            maze[7][j] = 1; // 第八行
        }
        // 构建左右边界（墙）
        for (int i = 0; i < 8; i++) {
            maze[i][0] = 1; // 第一列
            maze[i][6] = 1; // 第七列
        }
        // 构建内部墙
        maze[3][1] = 1;
        maze[3][2] = 1;
        return maze;
    }

    // 2. 打印迷宫：直观展示路径
    public static void printMaze(int[][] maze) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 3. 递归找迷宫路径
     * @param maze 迷宫数组
     * @param i 当前行
     * @param j 当前列
     * @param endI 终点行
     * @param endJ 终点列
     * @return 是否找到通路
     */
    public static boolean findPath(int[][] maze, int i, int j, int endI, int endJ) {
        // 递归终止条件：到达终点
        if (maze[endI][endJ] == 2) {
            return true;
        }

        // 合法性检查：当前位置在范围内，且是未走的通路（0）
        if (i >= 0 && i < maze.length && j >= 0 && j < maze[0].length && maze[i][j] == 0) {
            // 标记当前位置为已走的通路（2）
            maze[i][j] = 2;

            // 按优先级尝试方向：下 → 右 → 上 → 左
            // 1. 尝试向下走
            if (findPath(maze, i + 1, j, endI, endJ)) {
                return true;
            }
            // 2. 向下走不通，尝试向右走
            else if (findPath(maze, i, j + 1, endI, endJ)) {
                return true;
            }
            // 3. 向右走不通，尝试向上走
            else if (findPath(maze, i - 1, j, endI, endJ)) {
                return true;
            }
            // 4. 向上走不通，尝试向左走
            else if (findPath(maze, i, j - 1, endI, endJ)) {
                return true;
            }
            // 5. 所有方向都走不通，标记为死路（3），回溯
            else {
                maze[i][j] = 3;
                return false;
            }
        }

        // 当前位置不合法（墙/死路/越界），返回false
        return false;
    }

    // 主方法测试
    public static void main(String[] args) {
        // 1. 创建迷宫
        int[][] maze = createMaze();
        System.out.println("=== 初始迷宫 ===");
        printMaze(maze);

        // 2. 递归找路径：起点(1,1)，终点(6,5)
        boolean hasPath = findPath(maze, 1, 1, 6, 5);

        // 3. 输出结果
        System.out.println("\n=== 路径查找结果 ===");
        if (hasPath) {
            System.out.println("找到通路！迷宫路径如下：");
            printMaze(maze);
        } else {
            System.out.println("未找到通路！");
        }
    }
}

~~内存流程图~~：

ℹ️步骤 1/33:

汉诺塔

规则：3 根柱子（A、B、C），n 个圆盘从 A 移到 C，每次只能移 1 个，小圆盘不能放大圆盘下。

java

public class HanoiTower {
    // num：要移动的圆盘数；a：源柱子；b：辅助柱子；c：目标柱子
    public void move(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println(a + "->" + c); // 1个圆盘直接移
        } else {
            // 如果有多个圆盘，可以看成2个圆盘：最下面的和上面的所有盘
            // 1. 把num-1个圆盘从A移到B，借助C
            move(num - 1, a, c, b);
            // 2. 把最下面的1个圆盘从A移到C
            System.out.println(a + "->" + c);
            // 3. 把num-1个圆盘从B移到C，借助A
            move(num - 1, b, a, c);
        }
    }

    public static void main(String[] args) {
        move(3, 'A', 'B', 'C'); // 3个圆盘，从A移到C，借助B
    }
}

~~内存流程图~~：

ℹ️步骤 1/47:

八皇后

问题：在 8×8 棋盘上摆放 8 个皇后，任意两个皇后不能同行、同列、同斜线，求摆法总数。

思路（回溯法）：

用一维数组arr[8]表示，arr[i]表示第 i 行皇后的列号。
逐行摆放皇后，每放一个皇后，检查是否与已摆放的皇后冲突。
冲突则回溯，更换列号；无冲突则继续摆下一行，直到 8 个皇后全部摆放完毕（找到一个解）。

数组求和

java

/**
 * 递归求和：数组 arr 从索引 start 到末尾的和
 */
public static int sumArray(int[] arr, int start) {
    // 终止条件：start 超出数组长度，和为 0
    if (start >= arr.length) return 0;
    // 递归步骤：当前元素 + 后续元素的和
    return arr[start] + sumArray(arr, start + 1);
}

sumArray(new int[]{1,2,3,4}, 0) // 调用：→ 10

优化方案

记忆化搜索

针对重复计算问题，用数组、HashMap 等缓存已计算的子问题结果，避免重复计算。

优化斐波那契数列（记忆化搜索）：

java

import java.util.HashMap;
import java.util.Map;

public class FibonacciOptimized {
    // 缓存已计算的结果：key = n，value = F(n)
    private static Map cache = new HashMap

    public static int fib(int n) {
        if (n ) throw new IllegalArgumentException("n 必须大于 0");
        // 终止条件
        if (n == 1 || n == 2) return 1;
        // 检查缓存：已计算则直接返回
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        // 递归计算并缓存结果
        int result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);
        return result;
    }

    // 时间复杂度优化为 O(n)，空间复杂度 O(n)（缓存 + 栈）
}

迭代改写

将递归逻辑改为循环，手动管理计算过程，避免栈溢出和方法调用开销。

迭代改写斐波那契数列：

java

public static int fibIterative(int n) {
    if (n  throw new IllegalArgumentException("n 必须大于 0");
    if (n == 1 || n == 2) return 1;
    int a = 1, b = 1; // a = F(n-2), b = F(n-1)
    int result = 0;
    for (int i = 3; i ; i++) {
        result = a + b;
        a = b; // 更新 F(n-2) 为原 F(n-1)
        b = result; // 更新 F(n-1) 为当前结果
    }
    return result;
}

// 时间复杂度 O(n)，空间复杂度 O(1)（无栈开销，无缓存）

尾递归

尾递归是指递归调用是方法的最后一个操作，无后续计算（如 return fibTail(n-1, a, b)）。理论上，编译器可优化尾递归，复用栈帧（无需压栈新帧），避免栈溢出。

但 Java 编译器不支持尾递归优化（JVM 未实现），即使写尾递归，仍会压栈导致栈溢出。示例如下（仅作理论参考）：

java

/**
 * 尾递归版斐波那契数列（Java 不优化，仍可能栈溢出）
 * @param n 目标项
 * @param a F(n-2)
 * @param b F(n-1)
 */
public static int fibTail(int n, int a, int b) {
    if (n == 1) return a;
    if (n == 2) return b;
    // 递归调用是最后一个操作（尾递归）
    return fibTail(n - 1, b, a + b);
}

// 调用：fibTail(5, 1, 1) → 5

增加 JVM 栈容量

通过 JVM 参数 -Xss 增大栈容量（如 -Xss2m 表示栈容量为 2MB），可缓解栈溢出，但不根本解决问题（递归深度过大仍会溢出），不推荐依赖。

S01-08 基础-递归 ​

概述 ​

什么是递归 ​

本质：分治思想 ​

工作原理 ​

优缺点 ​

注意事项 ​

核心要素 ​

终止条件 ​

递归步骤 ​

常见应用场景 ​

数学问题 ​

打印问题 ​

阶乘计算 ​

斐波那契数列 ​

数据结构操作 ​

二叉树的前序遍历 ​

数组翻转 ​

链表反转 ​

文件目录遍历 ​

经典递归问题 ​

猴子吃桃 ​

迷宫问题 ​

汉诺塔 ​

八皇后 ​

数组求和 ​

优化方案 ​

记忆化搜索 ​

迭代改写 ​

尾递归 ​

增加 JVM 栈容量 ​

S01-08 基础-递归

概述

什么是递归

本质：分治思想

工作原理

优缺点

注意事项

核心要素

终止条件

递归步骤

常见应用场景

数学问题

打印问题

阶乘计算

斐波那契数列

数据结构操作

二叉树的前序遍历

数组翻转

链表反转

文件目录遍历

经典递归问题

猴子吃桃

迷宫问题

汉诺塔

八皇后

数组求和

优化方案

记忆化搜索

迭代改写

尾递归

增加 JVM 栈容量