方法递归详解

递归是一种在程序设计中非常常见的技术，它通过让一个方法调用自身来解决问题。递归通常用于那些可以分解成相同子问题的任务，如树形结构遍历、阶乘计算、斐波那契数列、深度优先搜索等。

在 Java 中，递归方法是指一个方法直接或间接地调用自己。递归必须具备两个基本要素：

递归条件：停止递归的条件。
递归过程：方法调用自己并逐步解决问题。

递归的基本结构

public returnType methodName(parameters) {
    // 递归终止条件
    if (terminationCondition) {
        return result;
    }
    
    // 递归调用
    return methodName(newParameters);
}

✅ 1. 递归的经典示例

1.1 计算阶乘（Factorial）

阶乘是指一个正整数及其所有小于它的正整数的积。比如，5! = 5 * 4 * 3 * 2 * 1。

递归实现阶乘

public class RecursionExample {

    // 递归计算阶乘
    public static int factorial(int n) {
        // 递归终止条件
        if (n == 0) {
            return 1;
        }
        // 递归过程
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5)); // 输出 120
    }
}

解释：

递归终止条件：当 n == 0 时，返回 1，这是阶乘的基本情况。
递归调用：通过 n * factorial(n - 1) 来逐步求解。

1.2 斐波那契数列（Fibonacci Sequence）

斐波那契数列是由 0 和 1 开始，之后的每个数都是前两个数的和。例如：0, 1, 1, 2, 3, 5, 8, 13, ...

递归实现斐波那契数列

public class RecursionExample {

    // 递归计算斐波那契数列
    public static int fibonacci(int n) {
        // 递归终止条件
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        // 递归过程
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci(5) = " + fibonacci(5)); // 输出 5
    }
}

解释：

递归终止条件：当 n == 0 或 n == 1 时，返回对应的值。
递归调用：通过 fibonacci(n - 1) + fibonacci(n - 2) 来计算当前斐波那契数。

1.3 计算数组的总和

递归也可以用来解决数组的处理问题，比如计算数组中所有元素的总和。

递归计算数组的总和

public class RecursionExample {

    // 递归计算数组的总和
    public static int sum(int[] arr, int n) {
        // 递归终止条件
        if (n <= 0) {
            return 0;
        }
        // 递归过程
        return arr[n - 1] + sum(arr, n - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println("数组总和 = " + sum(arr, arr.length)); // 输出 15
    }
}

解释：

递归终止条件：当数组长度为 0 时，返回 0。
递归调用：通过 arr[n - 1] + sum(arr, n - 1) 来逐步计算数组的总和。

✅ 2. 递归的注意事项

递归深度限制：每次递归调用都会占用栈空间，如果递归太深，可能会导致 StackOverflowError。对于一些问题，可以通过 尾递归 或迭代来避免栈溢出。
递归的性能问题：某些递归问题（如斐波那契数列）可以通过 动态规划 或 记忆化递归 来优化，避免重复计算。

✅ 3. 递归的优化：尾递归

尾递归是指递归调用出现在函数的最后一步，而且其返回值直接是递归调用的返回值。尾递归可以优化为迭代，避免占用过多的栈空间。

3.1 尾递归示例

假设我们要计算阶乘，如果实现是尾递归的，它就可以减少递归调用的栈空间占用。

public class RecursionExample {

    // 尾递归计算阶乘
    public static int factorialTailRecursion(int n, int accumulator) {
        // 递归终止条件
        if (n == 0) {
            return accumulator;
        }
        // 递归过程，直接在递归调用中传递结果
        return factorialTailRecursion(n - 1, n * accumulator);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorialTailRecursion(5, 1)); // 输出 120
    }
}