第39章 Java递归

面包屑导航章节头部学习目标

学习目标

理解递归的基本概念和工作原理
掌握递归算法的设计思路和实现方法
学会分析递归的时间和空间复杂度
了解递归优化技术（记忆化、尾递归等）
掌握递归在实际问题中的应用
学会递归与迭代的转换技巧
理解递归在数据结构和算法中的重要性

递归概述

Java递归概述

递归是一种强大的编程技术，其中函数调用自身来解决更小规模的相同问题。递归在算法设计、数据结构操作和问题求解中发挥着重要作用。

递归的核心要素基础情况（Base Case）：递归的终止条件，防止无限递归递归情况（Recursive Case）：函数调用自身的情况问题分解：将大问题分解为相同类型的小问题结果合并：将子问题的结果合并得到最终答案

递归执行流程

问题输入→检查基础情况→分解子问题→递归调用→合并结果递归类型详解

递归类型详解

线性递归

public static long factorial(int n) {
    if (n <= 1) {
        return 1; // 基础情况
    }
    return n * factorial(n - 1); // 递归情况
}

每次递归调用产生一个子问题
调用栈深度等于问题规模
适用于序列处理问题
时间复杂度通常为O(n)

二分递归

public static long fibonacci(int n) {
    if (n <= 1) {
        return n; // 基础情况
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

每次递归调用产生两个子问题
形成二叉树状的调用结构
可能存在重复计算问题
需要考虑优化策略

多分递归

public static void hanoi(int n, char from, 
                        char aux, char to) {
    if (n == 1) {
        System.out.println("Move " + from + " to " + to);
        return;
    }
    hanoi(n-1, from, to, aux);
    hanoi(1, from, aux, to);
    hanoi(n-1, aux, from, to);
}

每次递归调用产生多个子问题
问题分解更加复杂
适用于复杂的组合问题
需要仔细设计递归策略

递归 vs 迭代

递归实现

// 递归求和
public static int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n - 1);
}

优点：代码简洁，逻辑清晰
优点：自然表达分治思想
缺点：可能栈溢出
缺点：函数调用开销

迭代实现

// 迭代求和
public static int sum(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}

优点：空间效率高
优点：不会栈溢出
缺点：某些问题实现复杂
缺点：可读性可能较差

复杂度分析

递归复杂度分析

理解递归算法的时间和空间复杂度对于选择合适的算法实现至关重要：

算法	时间复杂度	空间复杂度	特点
阶乘（递归）	O(n)	O(n)	线性递归，调用栈深度为n
斐波那契（朴素递归）	O(2^n)	O(n)	指数时间，存在大量重复计算
斐波那契（记忆化）	O(n)	O(n)	通过缓存避免重复计算
二分查找（递归）	O(log n)	O(log n)	每次递归问题规模减半
快速排序（递归）	O(n log n)	O(log n)	分治算法，平均情况
汉诺塔	O(2^n)	O(n)	指数时间，最优解

递归优化技术

记忆化（Memoization）

private static Map cache = new HashMap<>();

public static long fibonacciMemoized(int n) {
    if (n <= 1) return n;
    
    if (cache.containsKey(n)) {
        return cache.get(n);
    }
    
    long result = fibonacciMemoized(n-1) + fibonacciMemoized(n-2);
    cache.put(n, result);
    return result;
}

尾递归优化

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

private static long factorialHelper(int n, long acc) {
    if (n <= 1) return acc;
    return factorialHelper(n - 1, n * acc);
}

动态规划转换

public static long fibonacciDP(int n) {
    if (n <= 1) return n;
    
    long[] dp = new long[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

在线IDE体验

在线代码体验

点击下面的按钮，在在线IDE中查看和运行完整的递归示例代码：
💻 查看完整代码 - 在线IDE体验最佳实践

递归最佳实践

避免的做法

缺少基础情况会导致无限递归和栈溢出
忽略性能问题不考虑时间和空间复杂度
过度使用递归简单问题不需要递归
不处理边界情况忽略特殊输入的处理
递归深度过大不考虑栈溢出风险

常见应用场景

递归应用场景

递归适用的问题特征问题可以分解为相同类型的子问题子问题的解可以合并为原问题的解存在明确的基础情况问题具有最优子结构性质

数据结构操作

二叉树的遍历（前序、中序、后序）
图的深度优先搜索（DFS）
链表的操作（反转、查找等）
多维数组的处理

算法设计

分治算法（快速排序、归并排序）
回溯算法（N皇后、数独求解）
动态规划（某些子问题重叠的情况）
搜索算法（深度优先搜索）

数学问题

数学递推关系（斐波那契、阶乘）
组合数学问题（排列组合）
数论问题（最大公约数）
几何问题（分形图形）

章节总结

递归是一种强大的编程技术，通过函数调用自身解决问题
递归必须包含基础情况和递归情况，确保算法能够终止
递归的时间和空间复杂度需要仔细分析，避免性能问题
记忆化、尾递归等优化技术可以显著提高递归算法的效率
递归在树、图、分治算法等领域有广泛应用
合理选择递归或迭代实现，考虑问题特点和性能要求
递归思想是理解许多高级算法和数据结构的基础

导航链接上一章：枚举(Enum) 章节测试下一章：反射(Reflection)