3.2 递归算法

递归算法是一种自我调用的过程，用来解决问题的一部分，直到达到一个基本条件。递归方法通常包括两个主要部分：基础案例（base case）和递归步骤（recursive step）。以下是一些常见的递归算法示例，它们使用 Java 编程语言实现。

示例 1: 计算阶乘

计算一个数的阶乘是递归算法的一个经典例子。阶乘 n! 定义为从 1 到 n 所有整数的乘积。

public class Factorial {

    public static int factorial(int n) {
        if (n == 0) {  // 基础案例
            return 1;
        } else {  // 递归步骤
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int number = 5;  // 计算 5!
        int result = factorial(number);
        System.out.println("Factorial of " + number + " is " + result);
    }
}

示例 2: 斐波那契数列

斐波那契数列是另一个常用递归算法的例子。在斐波那契数列中，每个数字是前两个数字的和，前两个数字分别是 0 和 1。

public class Fibonacci {

    public static int fibonacci(int n) {
        if (n <= 1) {  // 基础案例
            return n;
        } else {  // 递归步骤
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        int index = 9;  // 计算第 9 个斐波那契数
        int result = fibonacci(index);
        System.out.println("Fibonacci number at position " + index + " is " + result);
    }
}

示例 3: 反转字符串

使用递归反转字符串也是一个有趣的例子。在这个示例中，我们将每次递归调用中的首字符移至末尾。

public class ReverseString {

    public static String reverse(String str) {
        if (str.isEmpty()) {  // 基础案例
            return str;
        } else {  // 递归步骤
            return reverse(str.substring(1)) + str.charAt(0);
        }
    }

    public static void main(String[] args) {
        String original = "hello";
        String reversed = reverse(original);
        System.out.println("Original: " + original);
        System.out.println("Reversed: " + reversed);
    }
}

这些示例展示了递归算法如何用于不同的问题。递归算法虽然强大且表达力强，但需要注意的是递归可能导致栈溢出错误，特别是在处理大数据或深递归时。因此，在使用递归时，确保递归的深度不会过大，并且有合适的基本案例来结束递归。对于某些问题，迭代方法可能更加有效。