递归（Recursion）

一、递归概念

递归 指的是：
一个方法在其方法体内部直接或间接地调用自身。

递归常用于解决：

• 具有层级结构的问题
• 问题规模可不断缩小、形式相同的问题

二、递归的形式

1. 直接递归

方法在自身的方法体中调用自己。

void f() {
    f();
}

2. 间接递归

多个方法之间形成调用闭环。

void a() {
    b();
}

void b() {
    a();
}

三、递归的三要素（核心）

正确的递归程序 必须同时满足以下三个条件：

1. 终止条件（出口）

• 递归必须有明确的结束条件
• 否则会导致 栈溢出（StackOverflowError）

2. 递归公式（递归关系）

• 问题如何由 规模 n 递归到 规模 n-1（或更小）
• 是递归逻辑的核心

3. 递归方向

• 每一次递归调用都必须 向终止条件逼近
• 问题规模不断减小

四、递归的执行特点

• 每次递归调用都会在 调用栈 中压入一个栈帧
• 方法返回时，栈帧依次出栈
• 递归层次过深会导致 栈空间耗尽

五、递归搜索文件示例（Java）

1. 需求说明

递归遍历指定目录：

• 如果是文件，输出文件名
• 如果是目录，递归遍历其子目录

2. 示例代码

package FileDemo;

import java.io.File;

public class FileDemo1 {

    public void findFile(File f) {
        if (f.isFile()) {
            System.out.println(f.getName());
        } else {
            System.out.println(
                "文件夹----------------------" 
                + f.getName() 
                + "----------------------文件夹"
            );
            File[] files = f.listFiles();
            if (files != null) {
                for (File f1 : files) {
                    findFile(f1);
                }
            }
        }
    }

    public static void main(String[] args) {
        File f1 = new File("C:\\Users\\yarrow\\Desktop\\Python");
        FileDemo1 fd = new FileDemo1();
        fd.findFile(f1);
    }
}

3. 代码分析

• 终止条件：f.isFile() 为 true
• 递归规则：对目录中的每一个子文件再次调用 findFile
• 递归方向：目录结构不断向下拆分，最终到达文件节点

额外说明：

• listFiles() 可能返回 null（权限或 I/O 问题），需要判空
• 这是递归遍历文件系统的经典示例

六、递归的优缺点

优点

• 代码简洁、逻辑清晰
• 非常适合树形、层级结构问题

缺点

• 性能开销相对较大
• 占用栈空间
• 递归层数过深易导致栈溢出

七、递归与循环的取舍

• 能用循环解决的问题，大多数情况下 循环效率更高
• 当问题结构天然具有递归特征时（如树、目录、分治算法），递归更直观

八、小结

• 递归是一种重要的编程思想
• 核心是 终止条件 + 递归规则 + 正确方向
• 文件遍历是递归的经典应用场景
• 使用递归时要注意性能和栈深度问题