Java方法递归调用

1. 递归基础概念

递归是方法调用自身的过程，必须包含终止条件和递归步骤

学习目标

理解递归调用栈，掌握递归三要素：终止条件、递归调用、返回值合并

递归执行过程图解

main() → factorial(5)

→ factorial(4)

→ factorial(3)

→ factorial(2)

→ factorial(1)

返回 1

    public class RecursionBasic {
    public static void main(String[] args) {
    System.out.println("递归开始...");
    int result = recursiveMethod(3);
    System.out.println("最终结果: " + result);
    }

    public static int recursiveMethod(int n) {
    if (n <= 0) { // 终止条件
    System.out.println("到达终止条件");
    return 0;
    }
    System.out.println("当前n值: " + n);
    return n + recursiveMethod(n - 1); // 递归调用
    }
    }

2. 阶乘案例：5! = 120

通过阶乘计算理解递归的数学基础

1

数学定义

5! = 5 × 4 × 3 × 2 × 1
n! = n × (n-1)!
0! = 1（终止条件）

2

代码实现

	    public class FactorialExample {
	    public static void main(String[] args) {
	    int number = 5;
	    long result = factorial(number);
	    System.out.printf("%d! = %d%n", number, result);
	    }

	    
		/**
		* 计算阶乘的递归方法
		* @param n 非负整数
		* @return n的阶乘
		*/
	    
	    public static long factorial(int n) {
	    if (n < 0) {
	    throw new IllegalArgumentException("负数没有阶乘");
	    }
	    if (n == 0 || n == 1) { // 终止条件
	    return 1;
	    }
	    System.out.printf("计算 %d × factorial(%d)%n", n, n-1);
	    return n * factorial(n - 1); // 递归调用
	    }
	    }
	

调用栈可视化（factorial(5)）：
factorial(5) → 5 * factorial(4)
    factorial(4) → 4 * factorial(3)
        factorial(3) → 3 * factorial(2)
            factorial(2) → 2 * factorial(1)
                factorial(1) → 1
                    返回 1
            返回 2 * 1 = 2
        返回 3 * 2 = 6
    返回 4 * 6 = 24
返回 5 * 24 = 120

3. 斐波那契数列：1, 1, 2, 3, 5, 8...

经典递归案例，展示指数级复杂度问题

1

递归定义

F(1) = 1, F(2) = 1
F(n) = F(n-1) + F(n-2) (n > 2)

2

基础实现（低效）

	    public class FibonacciBasic {
	    public static int fibonacci(int n) {
	    if (n <= 0) return 0;
	    if (n == 1 || n == 2) return 1;
	    return fibonacci(n-1) + fibonacci(n-2);
	    }

	    public static void main(String[] args) {
	    int n = 8;
	    System.out.println("F(" + n + ") = " + fibonacci(n));
	    }
	    }
	

3

优化实现（带缓存）

	    import java.util.*;

	    public class FibonacciOptimized {
	    private static Map
		cache = new HashMap<>();

		public static long fibonacci(int n) {
		if (n <= 0) return 0;
		if (n == 1 || n == 2) return 1;

		if (cache.containsKey(n)) {
		return cache.get(n);
		}

		long result = fibonacci(n-1) + fibonacci(n-2);
		cache.put(n, result);
		return result;
		}
		}
	

4. 目录递归遍历

实际应用：递归遍历文件夹及其子文件

1

问题描述

统计指定目录下所有Java文件的数量和总大小

2

完整实现

	    import java.io.*;

	    public class DirectoryCounter {
	    private static int javaFileCount = 0;
	    private static long totalSize = 0;

	    public static void main(String[] args) {
	    String path = "./src";
	    File directory = new File(path);

	    if (!directory.exists() || !directory.isDirectory()) {
	    System.out.println("目录不存在！");
	    return;
	    }

	    countJavaFiles(directory);
	    System.out.printf("找到 %d 个Java文件，总大小 %.2f KB%n",
	    javaFileCount, totalSize / 1024.0);
	    }

	    private static void countJavaFiles(File dir) {
	    File[] files = dir.listFiles();
	    if (files == null) return;

	    for (File file : files) {
	    if (file.isDirectory()) {
	    // 递归处理子目录
	    countJavaFiles(file);
	    } else if (file.getName().endsWith(".java")) {
	    javaFileCount++;
	    totalSize += file.length();
	    System.out.println("发现: " + file.getAbsolutePath());
	    }
	    }
	    }
	    }
	

5. 常见递归错误

90%的递归问题源于这些错误

错误1：缺少终止条件（StackOverflowError）

	// 错误代码：无限递归
	public static int badFactorial(int n) {
	return n * badFactorial(n - 1); // 无终止条件！
	}
    

错误信息：Exception in thread "main" java.lang.StackOverflowError

错误2：终止条件设置不当

	// 错误：终止条件过早
	public static int wrongFibonacci(int n) {
	if (n == 0) return 0;
	return wrongFibonacci(n-1) + wrongFibonacci(n-2);
	// 缺少n=1的终止条件，导致F(1)计算错误
	}
    

错误3：参数未收敛

	// 错误：参数未减小
	public static void printNumbers(int n) {
	if (n <= 0) return;
	printNumbers(n); // 参数未变化！
	}
    

调试技巧

添加日志打印调用栈深度
使用IDE的调试器单步执行
设置断点观察参数变化
绘制递归树理解流程

性能陷阱

指数级复杂度（如斐波那契）
重复计算相同子问题
过深的调用栈
大量内存消耗

6. 递归优化技巧

将递归转换为更高效的形式

1

尾递归优化

	    public class TailRecursion {
	    public static long factorialTail(int n) {
	    return factorialHelper(n, 1);
	    }

	    private static long factorialHelper(int n, long accumulator) {
	    if (n == 0) return accumulator;
	    return factorialHelper(n - 1, n * accumulator); // 尾递归
	    }
	    }
	

2

迭代替代方案

	    public static long factorialIterative(int n) {
	    long result = 1;
	    for (int i = 2; i <= n; i++) {
	    result *= i;
	    }
	    return result;
	    }
	

动手练习

实现汉诺塔问题的递归解法
编写二分查找的递归实现
用递归判断回文字符串
实现快速排序算法
比较递归和迭代的性能差异

递归设计口诀

"找重复、找变化、找出口"：先找到重复子问题，明确变化的参数，最后确定终止条件。

Day 5 Java方法递归调用