17370845950

递归方法在Java中通过方法自身调用解决可分解的子问题，包含终止条件和递归调用两部分，适用于阶乘、斐波那契数列、树遍历等场景，但需注意栈溢出、重复计算及效率问题，可通过记忆化或迭代优化。

递归方法在Java中是指一个方法调用自身来解决问题的编程技术。它适用于可以分解为相同类型但规模更小的子问题的场景，比如计算阶乘、斐波那契数列、遍历树结构等。

基本结构

一个有效的递归方法通常包含两个核心部分：

• 终止条件（基准情况）： 防止无限调用，必须存在一个或多个不需要再次递归就能返回结果的情况。
• 递归调用： 方法调用自身，并传入变化后的参数，逐步逼近终止条件。

例如，计算n的阶乘：

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

执行过程分析

当调用factorial(5)时，方法会依次展开为：

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1
             = 120

每层调用都等待下一层返回结果，最终从最深层开始逐层回溯计算值。

常见应用场景

• 数学计算： 如斐波那契数列、幂运算、最大公约数等。
• 数据结构遍历： 二叉树的前序、中序、后序遍历天然适合递归实现。
• 分治算法： 归并排序、快速排序通过递归划分和合并数据。
• 路径搜索： 在图或迷宫中查找路径时常用递归回溯。

示例：二叉树的前序遍历

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public void preorder(TreeNode root) {
if (root == null) return; // 终止条件
System.out.println(root.val);
preorder(root.left);  // 递归左子树
preorder(root.right); // 递归右子树
}

注意事项与优化

递归虽然简洁，但也存在潜在问题：

• 栈溢出： 深度太大会导致StackOverflowError，应避免无限制递归。
• 重复计算： 如朴素斐波那契递归会产生大量重复调用，可用记忆化（缓存中间结果）优化。
• 效率问题： 递归涉及多次方法调用开销，必要时可改写为循环（迭代）方式提升性能。

带记忆化的斐波那契实现：

public static int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

基本上就这些。只要把握好终止条件和递归逻辑，递归就是一种强大而直观的工具。