17370845950

递归调用是方法在自身内部直接或间接调用自身，必须包含基线条件（终止条件）和递归步骤（缩小规模的子问题），依托调用栈展开与回退执行，常见错误有缺失终止条件、条件设计不当、参数未收敛及深度过大导致性能下降。

递归调用，就是方法在自己的方法体内部直接或间接地调用自身。它不是循环，但能实现重复逻辑；它的本质是函数调用栈的自然展开与回退。

递归必须包含两个核心部分

缺一不可，否则会崩溃或死循环：

• 基线条件（Base Case）：也叫终止条件，是递归停止的“刹车”。比如计算阶乘时，规定 n == 0 或 n == 1 就直接返回 1，不再继续调用。
• 递归步骤（Recursive Case）：把当前问题转化成更小、结构相同的子问题，并调用自己处理。例如 factorial(n) 返回 n * factorial(n - 1)，问题规模每次减 1。

执行原理：调用栈一层层压入，再逐层弹出

Java 每次调用方法，都会在虚拟机栈中创建一个独立的栈帧，保存参数、局部变量和返回地址。递归时这个过程连续发生：

• 第一次调用 factorial(4) → 压入第 1 个栈帧
• 内部调用 factorial(3) → 压入第 2 个栈帧
• 继续调用 factorial(2)、factorial(1) → 分别压入第 3、第 4 个栈帧
• 到达 factorial(1)，满足基线条件，返回 1 → 第 4 个栈帧弹出
• 第 3 帧拿到结果，算出 2 * 1 = 2，返回 → 第 3 帧弹出
• 依此类推，直到最外层得到 4 * 3 * 2 * 1 = 24

常见错误与注意事项

看似简洁，但容易踩坑：

• 忘记写终止条件：程序无限调用自身，栈空间耗尽，抛出 StackOverflowError
• 终止条件设计错误：比如写成 n == 2 却传入负数，可能永远无法命中，照样溢出
• 参数未向基线靠近：如递归调用写成 factorial(n)（没变参数），等于原地打转
• 深度过大影响性能：每层调用都有开销，斐波那契朴素递归时间复杂度是指数级，实际项目中常需优化（如记忆化、尾递归适配、转迭代）

典型应用场景

适合天然具有“自相似”结构的问题：

• 数学计算：阶乘、斐波那契、幂运算、1 到 n 求和
• 数据结构遍历：二叉树前/中/后序遍历、图的 DFS、目录文件递归扫描
• 算法设计：快速排序、归并排序、汉诺塔、回溯类问题（如八皇后）