Java 递归

1. 递归介绍

递归是指在一个函数的定义中，直接或间接地调用函数自身的一种编程技巧。递归的核心思想是将一个复杂的问题分解为与原问题相似的子问题，通过递归的方式一步步解决。

在 Java 中，递归通常通过方法调用自身来实现。递归的关键在于如何设计递归的终止条件，防止程序进入无限递归。

2. 递归的特点

自调用：递归的特点是函数在执行过程中会直接或间接地调用自己，直到满足某个条件时才停止。
递归出口：每个递归问题都需要有一个退出条件，否则会导致无限递归和栈溢出错误。这个条件称为递归出口。
栈空间：每次递归调用都会在调用栈上占用一块空间，因此递归过深时，可能会因为栈空间耗尽而导致栈溢出异常。

3. 认识递归的形式

递归的基本形式包括：

递归调用自身：一个方法可以调用自己来解决问题，通常用于解决问题的分解。
递归的基准情况：递归函数必须有一个终止条件，以避免无限递归。

递归函数的结构通常包含：

递归出口：明确当什么条件满足时递归结束。
递归调用：通过递归调用函数自身来继续处理子问题。

4. 递归算法的流程

递归算法通常遵循以下流程：

确定递归出口：先确定何时停止递归，避免进入死循环。递归出口是每次递归时必定会到达的条件。
分解问题：将原问题拆解成一个或多个更小、更简单的子问题，递归的调用则处理这些子问题。
递归回溯：当子问题解决后，递归开始回溯，并返回结果。

递归调用通常具有两种形式：

直接递归：函数直接调用自身。
间接递归：函数通过其他函数间接调用自己。

5. 猴子吃桃问题（经典递归问题）

猴子吃桃问题是递归中的经典问题。题目描述如下：

第一日，猴子摘下若干个桃子，吃了一半，再多吃一个。
第二天，猴子又吃了一半，继续吃掉一个。
以此类推，第 N 天，猴子吃掉一半再多一个，直到最后一天只剩下一个桃子。

我们可以通过递归来解决这个问题。假设第 N 天剩下的桃子为 1，则前一天剩下的桃子数是 2 * (剩下的桃子 + 1)，通过递归可以得到总的桃子数。

public class MonkeyPeach {
    // 递归函数，计算桃子的总数
    public static int getPeachCount(int day) {
        // 递归出口：当天只剩下1个桃子
        if (day == 1) {
            return 1;
        }
        // 递归调用：根据规律，前一天的桃子数为2倍加1
        return 2 * (getPeachCount(day - 1) + 1);
    }

    public static void main(String[] args) {
        int days = 10; // 设定总天数
        System.out.println("猴子第一天摘的桃子数是: " + getPeachCount(days));
    }
}

6. 文件搜索问题（递归应用）

递归广泛应用于目录和文件的搜索中。通过递归方式，可以遍历目录及其子目录，查找特定的文件。

假设我们有一个文件目录，我们想要递归地搜索该目录及其子目录中所有的 .txt 文件。我们可以通过递归方法来遍历目录结构。

import java.io.File;

public class FileSearch {
    public static void searchFiles(File directory, String fileExtension) {
        // 获取该目录下的所有文件和子目录
        File[] files = directory.listFiles();
        
        if (files != null) {
            for (File file : files) {
                // 如果是文件且符合扩展名条件，打印文件路径
                if (file.isFile() && file.getName().endsWith(fileExtension)) {
                    System.out.println(file.getAbsolutePath());
                } else if (file.isDirectory()) {
                    // 如果是目录，递归调用搜索
                    searchFiles(file, fileExtension);
                }
            }
        }
    }

    public static void main(String[] args) {
        File directory = new File("C:/Users/YourUsername/Documents"); // 指定目录路径
        searchFiles(directory, ".txt"); // 搜索所有 .txt 文件
    }
}