递归是利用问题自相似性简化逻辑的思路，适用于树遍历、分治、回溯等场景；需满足明确终止条件、规模递减、无外部状态依赖三要素。
递归不是循环的“高级替代品”，而是用问题自身结构来简化逻辑的思路。它适合那些天然具有“自相似性”的场景，比如树遍历、分治计算、回溯搜索等。盲目用递归替换循环反而会让代码更难懂、更易栈溢出。
什么时候该考虑递归？
核心判断标准：当前问题能否自然拆解为“规模更小的同类问题 + 一个简单合并步骤”。
- 树/图结构操作：遍历二叉树的前序、中序、后序，不需要手动维护栈或状态变量。
- 数学定义明确的函数：如阶乘（n! = n × (n−1)!）、斐波那契（F(n) = F(n−1) + F(n−2)）——但注意后者直接递归效率低，需记忆化。
- 回溯类问题：全排列、N皇后、组合总和等，递归天然表达“尝试→进入下一层→回退”的流程。
- 分治算法：归并排序、快速排序的核心逻辑用递归写更贴近思想本质。
怎么写一个安全可用的递归方法？
三个要素缺一不可：明确的终止条件、向终止靠近的参数变化、不依赖外部可变状态。
-
必须有 base case：比如遍历链表时，
node == null就返回；计算阶乘时，n == 0返回 1。 -
每次递归调用都要缩小问题规模：传入
n-1、node.next、array[left..mid]等，确保最终能触达 base case。 -
避免在递归中修改共享变量：比如用全局
List收集结果时，要在递归调用前 add，调用后 remove（回溯），而不是在方法外累积。
常见坑与应对方式
递归写错，往往不是逻辑错，而是控制错。
- 栈溢出：深度过大（如 10 万层链表）。对策：改迭代（手动模拟栈），或确认是否真需要那么深——很多场景其实可以用 BFS 或尾递归优化（Java 不支持自动尾调用，需手动转成迭代）。
-
重复计算：朴素斐波那契递归时间复杂度 O(2ⁿ)。对策：加缓存（
Map<integer integer></integer>记录已算结果），即记忆化递归。 - 逻辑绕晕：别盯着“自己调自己”想。专注两件事：① 当前这层要做什么（比如打印当前节点值）；② 下一层交给谁做（比如让左子树和右子树各自递归处理）。
一个实用对比示例：反转单链表
迭代写法需要三个指针翻转链接；递归写法则聚焦“我只管头结点，后面都反转好了，我再把原来的头连到新尾巴上”：
// 递归版本（简洁体现思路）
Node reverse(Node head) {
if (head == null || head.next == null) return head; // base case
Node newHead = reverse(head.next); // 后面已反转，返回新头
head.next.next = head; // 把原头接到新尾巴（即原 head.next）
head.next = null;
return newHead;
}
这段代码没有循环变量、没有 while，但清晰表达了“先翻后面，再接前面”的分治思想——这才是递归真正发力的地方。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
