9.6 方法递归（入门）

递归的概念

递归（Recursion）是指方法调用自身的过程。在 Java 中，递归是一种强大的编程技术，用于解决可以分解为相同子问题的问题。

递归的工作原理

递归方法的工作原理是将一个复杂问题分解为规模更小的相同问题，直到问题变得足够简单，可以直接解决。递归方法通常包含两个部分：

1. 基本情况（Base Case）：递归的终止条件，当满足这个条件时，递归停止
2. 递归情况（Recursive Case）：递归调用自身，处理规模更小的问题

递归的示例

示例 1：计算阶乘

阶乘是一个经典的递归问题。n 的阶乘定义为 n! = n × (n-1) × (n-2) × ... × 2 × 1，其中 0! = 1。

public class FactorialExample {
    public static void main(String[] args) {
        int n = 5;
        int result = factorial(n);
        System.out.println(n + "! = " + result); // 输出 5! = 120
    }
    
    public static int factorial(int n) {
        // 基本情况
        if (n == 0 || n == 1) {
            return 1;
        }
        // 递归情况
        return n * factorial(n - 1);
    }
}

示例 2：计算斐波那契数列

斐波那契数列的定义是：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（n ≥ 2）。

public class FibonacciExample {
    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci sequence up to " + n + " terms:");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        System.out.println();
    }
    
    public static int fibonacci(int n) {
        // 基本情况
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        // 递归情况
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

示例 3：计算最大公约数

最大公约数（GCD）是指两个或多个整数共有约数中最大的一个。可以使用欧几里得算法（辗转相除法）通过递归来计算。

public class GCDExample {
    public static void main(String[] args) {
        int a = 48;
        int b = 18;
        int result = gcd(a, b);
        System.out.println("GCD of " + a + " and " + b + " is " + result); // 输出 6
    }
    
    public static int gcd(int a, int b) {
        // 基本情况
        if (b == 0) {
            return a;
        }
        // 递归情况
        return gcd(b, a % b);
    }
}

递归的应用场景

1. 数学问题：阶乘、斐波那契数列、最大公约数等
2. 数据结构：树的遍历、图的搜索等
3. 分治算法：快速排序、归并排序等
4. 回溯算法：八皇后问题、迷宫求解等

递归的优缺点

优点

1. 代码简洁：递归可以用简洁的代码解决复杂问题
2. 可读性强：递归代码通常更接近问题的数学描述
3. 易于理解：对于某些问题，递归解法更容易理解

缺点

1. 性能问题：递归可能导致重复计算，影响性能
2. 栈溢出：递归深度过大可能导致栈溢出
3. 内存消耗：递归需要额外的栈空间

递归的优化

1. 记忆化（Memoization）

记忆化是一种优化技术，用于存储已经计算过的结果，避免重复计算。

示例：优化斐波那契数列计算

public class FibonacciMemoizationExample {
    public static void main(String[] args) {
        int n = 40;
        long[] memo = new long[n + 1];
        long result = fibonacci(n, memo);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
    
    public static long fibonacci(int n, long[] memo) {
        // 基本情况
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        
        // 检查是否已经计算过
        if (memo[n] != 0) {
            return memo[n];
        }
        
        // 递归计算并存储结果
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
        return memo[n];
    }
}

2. 迭代替代递归

对于某些递归问题，可以使用迭代（循环）来替代递归，以提高性能和避免栈溢出。

示例：使用迭代计算阶乘

public class FactorialIterativeExample {
    public static void main(String[] args) {
        int n = 5;
        int result = factorial(n);
        System.out.println(n + "! = " + result); // 输出 5! = 120
    }
    
    public static int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

递归的注意事项

1. 确保有终止条件：递归必须有一个基本情况作为终止条件，否则会导致无限递归
2. 注意递归深度：递归深度过大可能导致栈溢出
3. 避免重复计算：对于重复计算的问题，使用记忆化技术
4. 考虑性能：对于性能敏感的场景，考虑使用迭代替代递归
5. 理解递归过程：在编写递归代码前，先手动模拟递归过程，确保逻辑正确

示例：递归的综合应用

示例 1：二分查找

二分查找是一种高效的搜索算法，用于在有序数组中查找目标值。

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 11;
        int index = binarySearch(array, target, 0, array.length - 1);
        if (index != -1) {
            System.out.println("Target found at index: " + index);
        } else {
            System.out.println("Target not found");
        }
    }
    
    public static int binarySearch(int[] array, int target, int low, int high) {
        // 基本情况：目标未找到
        if (low > high) {
            return -1;
        }
        
        // 计算中间索引
        int mid = low + (high - low) / 2;
        
        // 基本情况：找到目标
        if (array[mid] == target) {
            return mid;
        }
        
        // 递归情况：在左半部分查找
        if (array[mid] > target) {
            return binarySearch(array, target, low, mid - 1);
        }
        
        // 递归情况：在右半部分查找
        return binarySearch(array, target, mid + 1, high);
    }
}

示例 2：打印文件系统

递归可以用于遍历文件系统，打印目录结构。

import java.io.File;

public class FileSystemExample {
    public static void main(String[] args) {
        String path = ".";
        printFileSystem(new File(path), 0);
    }
    
    public static void printFileSystem(File file, int indent) {
        // 打印缩进
        for (int i = 0; i < indent; i++) {
            System.out.print("  ");
        }
        
        // 打印文件名
        System.out.println(file.getName());
        
        // 如果是目录，递归打印子文件和子目录
        if (file.isDirectory()) {
            File[] files = file.listFiles();
            if (files != null) {
                for (File f : files) {
                    printFileSystem(f, indent + 1);
                }
            }
        }
    }
}

常见问题

1. 无限递归

症状：运行时错误：StackOverflowError

解决方案：确保递归有明确的终止条件

2. 栈溢出

症状：运行时错误：StackOverflowError

解决方案：减少递归深度，或使用迭代替代递归

3. 性能问题

症状：递归执行速度慢

解决方案：使用记忆化技术，或使用迭代替代递归

4. 逻辑错误

症状：递归结果不正确

解决方案：手动模拟递归过程，确保逻辑正确

总结

递归是一种强大的编程技术，用于解决可以分解为相同子问题的问题。递归方法通常包含基本情况和递归情况两个部分。

递归的优点包括代码简洁、可读性强和易于理解，缺点包括性能问题、栈溢出和内存消耗。

在使用递归时，需要注意确保有终止条件、注意递归深度、避免重复计算、考虑性能和理解递归过程。

通过合理使用递归，可以解决许多复杂的问题，使代码更加简洁和易于理解。