Java案例怎么实现递归算法？

wen java案例 2026-06-12 11

Java递归算法案例详解与实战应用

📖 目录导读

递归算法核心概念与Java实现原理
经典递归案例一：阶乘计算
经典递归案例二：斐波那契数列
经典递归案例三：文件目录树遍历
递归的陷阱：栈溢出与性能优化
递归 vs 迭代：何时选择递归？
常见问题问答（FAQ）
写出优雅递归代码的黄金法则

递归算法核心概念与Java实现原理

递归（Recursion）是计算机科学中一种通过函数调用自身来解决问题的编程技术，在Java中，递归实现需满足两个基本要素：终止条件（Base Case）和递归步骤（Recursive Step）。

Java案例怎么实现递归算法？

终止条件：当问题规模缩小到可以直接求解时停止递归。
递归步骤：将原问题分解为更小的子问题，并通过调用函数自身求解子问题。

Java实现模板：

public ReturnType methodName(Parameters) {
    // 1. 终止条件
    if (baseCondition) {
        return baseResult;
    }
    // 2. 递归调用
    ReturnType result = methodName(smallerParameters);
    // 3. 组合结果（如果需要）
    return combineResult(result);
}

为什么Java能实现递归？因为每次函数调用都会在栈（Stack）上分配新的栈帧（Stack Frame），保存局部变量、参数和返回地址，当函数返回时，栈帧被销毁，控制权回到上层调用处。

经典递归案例一：阶乘计算

问题描述：计算n!（n的阶乘），其中n! = n × (n-1) × ... × 1，且0! = 1。

递归思路：

终止条件：当n=0或n=1时，返回1。
递归关系：n! = n × (n-1)!

Java代码实现：

public class Factorial {
    public static long factorial(int n) {
        // 终止条件
        if (n <= 1) {
            return 1;
        }
        // 递归步骤
        return n * factorial(n - 1);
    }
    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5)); // 输出120
        System.out.println("10! = " + factorial(10)); // 输出3628800
    }
}

执行过程分析（以n=3为例）：

factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1 (终止)
向上回溯：2 * 1 = 2 → 3 * 2 = 6

注意事项：int类型在n>12时溢出，建议使用long或BigInteger。

经典递归案例二：斐波那契数列

问题描述：斐波那契数列定义为F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

递归实现（最简形式，但效率低下）：

public class Fibonacci {
    public static long fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
    public static void main(String[] args) {
        System.out.println("F(10) = " + fib(10)); // 输出55
    }
}

问题所在：上述代码存在大量重复计算，例如计算fib(5)时，fib(3)被计算了两次，时间复杂度为O(2^n)，当n=50时计算量天文数字。

优化方案一：记忆化递归（Memoization）

public class FibonacciMemo {
    private static long[] cache;
    public static long fib(int n) {
        cache = new long[n + 1];
        return fibMemo(n);
    }
    private static long fibMemo(int n) {
        if (n <= 1) {
            return n;
        }
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fibMemo(n - 1) + fibMemo(n - 2);
        return cache[n];
    }
}

时间复杂度降为O(n)，空间复杂度O(n)。

优化方案二：尾递归（需借助辅助函数）

public class FibonacciTail {
    public static long fib(int n) {
        return fibHelper(n, 0, 1);
    }
    private static long fibHelper(int n, long a, long b) {
        if (n == 0) return a;
        if (n == 1) return b;
        return fibHelper(n - 1, b, a + b);
    }
}

Java编译器不自动优化尾递归，但该写法更接近循环逻辑。

经典递归案例三：文件目录树遍历

业务场景：统计指定目录下所有文件的总大小，或查找所有.java文件。

递归实现：

import java.io.File;
public class DirectoryTraversal {
    public static long getTotalSize(File directory) {
        long total = 0;
        if (directory.isFile()) {
            return directory.length();
        }
        File[] files = directory.listFiles();
        if (files == null) {
            return 0;
        }
        for (File file : files) {
            if (file.isDirectory()) {
                total += getTotalSize(file); // 递归调用
            } else {
                total += file.length();
            }
        }
        return total;
    }
    public static void main(String[] args) {
        File dir = new File("/path/to/directory");
        System.out.println("总大小: " + getTotalSize(dir) + " bytes");
    }
}

关键点：

终止条件：遇到文件时直接返回文件大小。
递归步骤：遍历子目录，累加所有子文件/子目录的大小。
防御性编程：务必检查listFiles()返回是否为null（权限问题或空目录）。

递归的陷阱：栈溢出与性能优化

1 栈溢出（StackOverflowError）

当递归深度过大时,栈帧数量超过JVM栈的容量限制。

public static void infiniteRecursion(int n) {
    System.out.println(n);
    infiniteRecursion(n + 1); // 没有终止条件
}

默认栈深度约10,000层（取决于JVM参数）。

解决方案：

增加栈大小：JVM参数 -Xss512k 或 -Xss1m。
改用迭代（循环）：递归本质上可用栈+循环模拟。
限制递归深度：添加防御性检查。

2 性能优化原则

避免重复计算：使用缓存（记忆化）。
减少参数传递开销：尽量使用全局变量或类成员。
考虑尾递归写法：虽然Java不优化，但代码逻辑更清晰。

递归 vs 迭代：何时选择递归？

特性	递归	迭代
代码可读性	树形/分治问题更自然	线性问题更直观
性能	有栈帧开销	高效，无额外函数调用
内存使用	O(n) 栈空间	O(1) 或 O(n) 堆空间
适用场景	树/图遍历、分治算法、回溯	简单循环、线性计算