Java中的递归 | Baeldung中文网

1. 递归基础概念

递归是编程语言中的核心概念之一。本文将深入探讨递归函数的特性，并通过Java示例展示如何用递归解决实际问题。

2.1 递归的定义

在Java中，方法调用自身的机制称为递归。例如计算从0到n的整数和：

public int sum(int n) {
    if (n >= 1) {
        return sum(n - 1) + n;
    }
    return n;
}

递归函数必须满足两个核心要求：

终止条件：当满足特定条件时直接返回值，不再递归
递归调用：函数调用自身，且每次调用都更接近终止条件

⚠️ 每次递归调用都会在JVM栈内存中创建新帧，若递归深度过大可能引发内存溢出（OOM）。可通过尾递归优化规避此风险。

2.2 尾递归 vs 头递归

尾递归：递归调用是函数执行的最后一个操作
头递归：递归调用后仍有其他操作需执行

将前例改造为尾递归：

public int tailSum(int currentSum, int n) {
    if (n <= 1) {
        return currentSum + n;
    }
    return tailSum(currentSum + n, n - 1);
}

尾递归中，递归调用后无需保留当前栈帧，理论上可优化内存。但Java编译器目前不支持尾递归优化，这点需特别注意。

2.3 递归 vs 迭代

递归的优势： ✅ 代码更简洁清晰 ✅ 天然适合树形结构等问题（如二叉树遍历）

递归的劣势： ❌ 内存消耗随递归深度增加 ❌ 可能存在性能损失

迭代实现示例：

public int iterativeSum(int n) {
    int sum = 0;
    if(n < 0) {
        return -1;
    }
    for(int i=0; i<=n; i++) {
        sum += i;
    }
    return sum;
}

选择建议：

简单逻辑用迭代（性能更优）
复杂树形结构用递归（代码更简洁）
尾递归在支持优化的语言中是理想选择

3. 递归实战案例

3.1 计算10的n次方

递归思路：

计算10的(n-1)次方
结果乘以10
终止条件：n=0时返回1

public int powerOf10(int n) {
    if (n == 0) {
        return 1;
    }
    return powerOf10(n-1) * 10;
}

3.2 斐波那契数列第n项

数列规律：0, 1, 1, 2, 3, 5, 8...（每个数是前两数之和）

递归实现：

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

⚠️ 此实现存在重复计算问题，实际开发中建议用动态规划优化。

3.3 十进制转二进制

递归思路：

除2取余
递归处理商
倒序拼接余数

public String toBinary(int n) {
    if (n <= 1 ) {
        return String.valueOf(n);
    }
    return toBinary(n / 2) + String.valueOf(n % 2);
}

3.4 二叉树高度计算

树高定义：根节点到最深叶节点的边数

递归解法：

public int calculateTreeHeight(BinaryNode root){
    if (root!= null) {
        if (root.getLeft() != null || root.getRight() != null) {
            return 1 + 
              max(calculateTreeHeight(root.left), 
                calculateTreeHeight(root.right));
        }
    }
    return 0;
}

4. 总结

递归是解决复杂问题的利器，但使用时需注意：

确保有明确的终止条件
控制递归深度避免栈溢出
权衡递归与迭代的适用场景

本文所有代码示例可在GitHub仓库获取。

Persistence

REST

Security