02.6.1.1 递归三要素与递归树
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.1 递归与回溯框架
02.6.1.1-001 递归是什么?什么场景适合用递归?
一句话结论
递归是函数直接或间接调用自身,把大问题拆解为结构相同、规模更小的子问题,直到命中基准情形(base case)直接返回;适合问题天然可自相似分解、用循环状态机难以表达的场景。
概念解释
- 基准情形:不再递归、直接给出答案的最小子问题。
- 递归情形:当前问题拆成子问题并合并结果。
- 自相似:子问题与原问题类型一致。
原理流程
- 判断当前是否命中基准情形,命中则返回。
- 否则把问题缩小,递归求解子问题。
- 把子问题结果按规则合并为当前结果。
代码 / 示例
// 阶乘:基准 n<=1 返回 1;递归 n*fact(n-1)
long fact(int n) {
if (n <= 1) return 1; // 基准情形
return n * fact(n - 1); // 递归情形
}
常见误区
- 误区:递归就是函数里调用自己;正解:必须有收敛到基准情形的路径,否则无限递归。
- 误区:递归比循环高级所以优先用;正解:可读性优先,深度或性能受限时应改迭代。
追问
- Q:递归一定能改成迭代吗? A:理论上都可以,显式栈模拟调用帧即可,只是可读性可能下降。
- Q:递归适合处理什么样的数据结构? A:树形、分治、回溯等天然分层/分支结构。
02.6.1.1-002 递归三要素是哪三个?
一句话结论
三要素:明确的终止条件(基准情形)、缩小问题规模的递归关系、正确的返回值与合并方式;三者缺一不可,终止条件保证收敛,递归关系保证规模下降,返回值保证结果可合并。
概念解释
- 终止条件:什么情况下不再往下递归。
- 递归关系:当前解如何由子问题解得到。
- 返回值:函数向上层传递什么信息(单值、对象、布尔)。
原理流程
- 先写基准情形并直接返回。
- 再写递归调用,参数必须比当前更接近基准。
- 最后合并子结果,确定本层返回值。
代码 / 示例
// 求数组和:基准空数组返回 0;递归 head + 剩余和
int sum(int[] a, int i) {
if (i == a.length) return 0; // 终止条件
return a[i] + sum(a, i + 1); // 递归关系 + 返回值合并
}
常见误区
- 误区:只写递归调用不写终止条件;正解:先保证基准分支存在且可达。
- 误区:递归参数没有向基准靠近;正解:每一层都要让规模严格下降。
追问
- Q:三要素中哪个最容易被面试追问? A:返回值设计,尤其是需要同时返回多个信息时要封装对象。
- Q:终止条件写在递归体内还是体外? A:通常函数入口先判断基准再递归,避免越界调用。
02.6.1.1-003 递归调用栈与栈帧是什么?
一句话结论
每次递归调用都会在调用栈上压入一个栈帧,保存参数、局部变量、返回地址;递归返回时逐层弹出;栈深度超过虚拟机栈容量就会栈溢出(StackOverflowError)。
概念解释
- 栈帧:一次调用的现场快照。
- 调用栈:从当前函数到根调用的帧序列。
- 栈深度:同时存活的栈帧个数。
原理流程
- 调用自身前压帧。
- 子问题执行期间父帧挂起。
- 子问题返回后父帧恢复并继续。
代码 / 图示
fact(3)
fact(2)
fact(1) -> 1
<- 2*1=2
<- 3*2=6
常见误区
- 误区:递归占用的是堆内存;正解:栈帧在调用栈上,堆用于对象。
- 误区:返回值会自动跨帧保留;正解:局部变量随帧弹出,需通过返回值或共享结构回传。
追问
- Q:栈溢出由什么决定? A:最大递归深度与单帧大小,受 JVM 栈容量限制。
- Q:如何估算递归深度? A:看每次调用规模下降多少,如 n 每次减 1 深度为 n。
02.6.1.1-004 递归和迭代是什么关系?
一句话结论
迭代用循环在同一栈帧内反复更新状态;递归用多帧自顶向下分解问题;二者可互相转化,递归靠调用栈保存状态,迭代靠显式变量或显式栈保存状态。
概念解释
- 迭代:状态在循环变量上滚动。
- 递归:状态分布在各层栈帧。
- 等价性:任意递归可由显式栈模拟为迭代。
原理流程
- 递归:拆子问题 → 压帧 → 返回合并。
- 迭代:初始化状态 → 循环更新 → 终止退出。
- 转换:把栈帧信息搬到显式栈。
代码 / 示例
// 迭代阶乘
long factIter(int n) {
long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
常见误区
- 误区:迭代一定比递归快;正解:简单尾递归常被优化,复杂递归可读性更好,需实测。
- 误区:递归转迭代只改循环结构;正解:树形/回溯递归还需显式栈保存路径与返回点。
追问
- Q:什么递归最难转迭代? A:需要后序合并结果、且分支顺序复杂的树形递归。
- Q:迭代的状态存在哪里? A:循环变量、数组、显式栈或队列。
02.6.1.1-005 递归深度为什么会栈溢出?怎么控制?
一句话结论
递归深度等于最长调用链长度,深度过大时栈帧数量超过栈容量即溢出;控制手段包括减小递归深度(分治平衡)、改迭代、增大栈容量(不推荐作为主方案)。
概念解释
- 深度:从根到叶的最长链路。
- 栈容量:线程栈可容纳的帧上限。
- 溢出:帧超出栈边界。
原理流程
- 估算最坏深度。
- 若深度接近上限,评估改造。
- 树形递归优先用平衡划分压低高度。
代码 / 示例
// 链表长度递归最坏 O(n) 深度;链表过长应改迭代统计
常见误区
- 误区:只要结果正确就不怕深递归;正解:深度是硬约束,长链表/长字符串递归可能直接溢出。
- 误区:增大栈参数能根治;正解:只是推迟溢出,深迭代仍是正确工程解。
追问
- Q:二叉树递归深度是什么? A:树高,最坏链形 O(n),平衡 O(log n)。
- Q:DFS 递归和 BFS 谁更易溢出? A:递归 DFS 受深度影响,BFS 用队列不受栈深限制。
02.6.1.1-006 递归树怎么画?怎么用它估复杂度?
一句话结论
递归树把每层递归调用画成节点,边表示一次子问题拆分;节点标注子问题规模与代价,累加各层代价再乘层数,即可估算时间复杂度;分治类问题还可结合主定理核对。
概念解释
- 节点:一次递归调用及其代价。
- 层:相同深度的所有调用。
- 规模:子问题输入大小。
原理流程
- 根节点写原问题规模与单次代价。
- 按拆分关系展开子节点。
- 汇总每层总代价,乘层数得量级。
代码 / 图示
f(n) 代价 c
/ \
f(n/2) f(n/2)
/ \ / \
... 共 n 个叶子,层数 log n
常见误区
- 误区:只看叶子个数估时间;正解:每层内部代价也要累加,不是只数叶子。
- 误区:递归树层数就是问题规模;正解:层数取决于每次规模缩减比例。
追问
- Q:归并排序递归树每层代价多少? A:每层合并合计 O(n),共 O(log n) 层,总 O(n log n)。
- Q:树节点数与时间复杂度什么关系? A:无剪枝时节点数即调用次数,与总代价成正比。
02.6.1.1-007 手写阶乘递归并报复杂度。
一句话结论
阶乘 n! = n × (n-1)!,基准 0!=1!=1;时间 O(n)(n 次调用),空间 O(n)(递归栈深度)。
概念解释
- 子问题规模每次减 1。
- 每层做一次乘法。
- 结果自底向上回乘。
原理流程
- n ≤ 1 返回 1。
- 递归求 (n-1)!。
- 返回 n × 子结果。
代码 / 示例
long fact(int n) {
if (n < 0) throw new IllegalArgumentException();
if (n <= 1) return 1;
return n * fact(n - 1);
}
常见误区
- 误区:把基准写成 n==0 返回 0;正解:阶乘基准返回 1。
- 误区:n 较大用 int 累加;正解:结果快速溢出,需 long 或大数类型并评估范围。
追问
- Q:阶乘能用尾递归吗? A:可带累积参数写成尾递归形式,但是否消除尾调用取决于运行环境,待确认。
- Q:阶乘时间复杂度? A:O(n),空间 O(n)。
02.6.1.1-008 斐波那契递归为什么慢?重复子问题在哪?
一句话结论
朴素斐波那契递归 f(n)=f(n-1)+f(n-2) 存在大量重复子问题,同一 f(k) 被反复计算,时间 O(2ⁿ)、空间 O(n);加记忆化后降到 O(n)。
概念解释
- 重叠子问题:相同状态被多次求解。
- 递归树指数膨胀:f(n-1) 与 f(n-2) 共享大量子树。
原理流程
- 展开 f(n) 观察重复节点。
- 重复节点越多,浪费越大。
- 记忆化把算过的状态缓存复用。
代码 / 示例
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // 重复计算
}
常见误区
- 误区:递归写法天然慢是因为函数调用;正解:主因是指数级重复子问题,不是调用开销本身。
- 误区:记忆化后空间仍 O(2ⁿ);正解:缓存每个状态一份,空间 O(n)。
追问
- Q:记忆化后时间多少? A:O(n),每个状态算一次。
- Q:能否压成 O(1) 空间? A:迭代滚动两个变量即可。
02.6.1.1-009 递归求数组和、最大值、翻转分别怎么写?
一句话结论
以当前下标为状态:和用累加合并,最大值用比较合并,翻转用交换对称位置;三者基准都是下标越界直接返回。
概念解释
- 状态:当前处理到下标 i。
- 合并:和为加,最值为比较,翻转为对称交换。
原理流程
- 基准 i 越界。
- 递归处理剩余区间。
- 本层元素参与合并。
代码 / 示例
int max(int[] a, int i) {
if (i == a.length - 1) return a[i];
return Math.max(a[i], max(a, i + 1));
}
常见误区
- 误区:最大值基准返回 0;正解:元素可能为负,基准应返回末端元素。
- 误区:翻转递归里忘记交换回来;正解:原地交换无需撤销,但要先定好对称区间。
追问
- Q:空数组怎么处理? A:入口判空,按题意返回 0 或抛异常。
- Q:这三类递归空间多少? A:O(n) 栈深,迭代可压到 O(1)。
02.6.1.1-010 链表反转的递归写法思路是什么?
一句话结论
递归假设 head.next 之后已反转,新头为 newHead;把 head.next.next = head 完成回指,再断开 head.next = null;基准是空节点或单节点。
概念解释
- 子问题:反转除首节点外的后缀链表。
- 合并:把首节点接到反转后缀的末端。
原理流程
- 递归得到后缀反转后的头。
- 原第二个节点的 next 指回 head。
- head 置为尾并返回新头。
代码 / 示例
ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
常见误区
- 误区:忘记
head.next = null;正解:否则原头留在环链中。 - 误区:返回后缀的旧头;正解:要返回递归得到的新头。
追问
- Q:递归空间多少? A:O(n) 栈深,迭代版 O(1)。
- Q:链表过深会栈溢出吗? A:会,长链表工程上优先迭代。
02.6.1.1-011 二叉树遍历为什么天然用递归?
一句话结论
二叉树左右子树是与原问题同构的子问题,遍历位置(前/中/后序)决定递归调用与访问节点的先后;递归代码最短,迭代需显式栈模拟。
概念解释
- 同构:子树也是二叉树。
- 访问时机:根在递归前、中、后对应三种序。
原理流程
- 空节点返回。
- 按序访问根与递归左右。
- 结果由各层拼接。
代码 / 示例
void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
visit(root.val);
inorder(root.right);
}
常见误区
- 误区:前中后序区别在于先左还是先右;正解:区别是根节点访问时机,左右顺序固定。
- 误区:递归遍历会修改树;正解:只读访问,不改指针。
追问
- Q:递归遍历空间多少? A:O(h) 栈深,h 为树高。
- Q:树极端链形时空间多少? A:O(n)。
02.6.1.1-012 递归返回值怎么设计:单值还是辅助函数?
一句话结论
只需要一个聚合结果时直接返回单值;需要同时回传多个信息(如高度 + 是否平衡)时,封装成对象或用成员变量/数组在递归间共享;辅助函数负责扩展状态参数。
概念解释
- 单值返回:和、最大值、是否合法。
- 多值返回:对象封装、全局数组携带。
- 辅助函数:原函数对外简洁,内部带深度/路径等参数。
原理流程
- 列清每层需要向上汇报的信息。
- 单值直接 return;多值定义返回结构。
- 辅助函数补全递归参数。
代码 / 示例
// 返回 {高度, 是否平衡}
static class Info { int h; boolean ok; }
Info dfs(TreeNode r) {
if (r == null) return new Info(0, true);
Info l = dfs(r.left), rr = dfs(r.right);
boolean ok = l.ok && rr.ok && Math.abs(l.h - rr.h) <= 1;
return new Info(Math.max(l.h, rr.h) + 1, ok);
}
常见误区
- 误区:用多个全局变量互相赋值替代返回;正解:能局部封装就避免跨层共享,降低并发与回溯风险。
- 误区:把判断结果塞进返回值又用异常分支传递;正解:状态结构化更清晰。
追问
- Q:为什么平衡树判断要后序? A:需要左右高度才能判断当前层。
- Q:辅助函数的状态参数放哪? A:随递归栈保存,不修改共享对象。
02.6.1.1-013 纯递归和回溯的区别是什么?
一句话结论
纯递归只做分解与合并,路径状态随栈帧自然销毁;回溯在递归树上枚举所有选择,做选择后递归、返回后撤销选择恢复现场,以复用同一条路径容器;回溯是带现场恢复的递归。
概念解释
- 纯递归:结果自底向上合并,不维护可复用路径。
- 回溯:显式 path 容器,选择/撤销成对出现。
原理流程
- 纯递归:基准 → 子问题 → 合并。
- 回溯:选择 → 递归 → 撤销。
- 二者底层都是递归栈。
代码 / 示例
// 回溯:选择与撤销成对
path.add(x);
backtrack(...);
path.remove(path.size() - 1);
常见误区
- 误区:回溯必须改原数据结构;正解:可只传参数副本,但撤销写法更省拷贝。
- 误区:纯递归不能枚举多分支;正解:多分支递归也是 DFS,回溯强调路径记录与撤销。
追问
- Q:回溯的撤销在什么时候? A:子递归返回后立即恢复现场。
- Q:什么时候不需要撤销? A:每次新建副本、不修改共享路径时。
02.6.1.1-014 什么是尾递归?它为什么可能被优化?
一句话结论
尾递归指递归调用是函数最后一步操作,返回值不再参与本层运算;部分运行环境可复用当前栈帧消除递归,但 Java 的 HotSpot 并不保证尾递归优化,工程上不能依赖。
概念解释
- 尾调用:最后一步调用另一函数。
- 尾递归:被调用者是自身。
- 优化前提:本层不再保留局部状态。
原理流程
- 把累积结果作为参数带入。
- 递归调用后直接返回,不再计算。
- 符合条件的运行环境可覆盖当前帧。
代码 / 示例
// 带累加器的尾递归形式(是否消除取决于运行环境,待确认)
long factTail(int n, long acc) {
if (n <= 1) return acc;
return factTail(n - 1, n * acc);
}
常见误区
- 误区:写成尾递归 Java 就不会栈溢出;正解:JVM 规范未要求尾调用优化,深度仍可能溢出。
- 误区:尾递归和迭代等价写法可以照搬所有语言;正解:优化行为按语言/运行环境区分。
追问
- Q:如何判断是否尾递归? A:看递归返回后本层是否还有运算。
- Q:不依赖优化时怎么办? A:显式写成循环或用显式栈。
02.6.1.1-015 分治和递归是什么关系?
一句话结论
分治是一种解题策略:分解成子问题、递归求解、合并结果;递归是实现分治的手段;分治要求子问题独立且合并可做,典型如归并排序、快排、最近点对。
概念解释
- 分解:切分为同质子问题。
- 解决:递归求解。
- 合并:汇总子结果。
原理流程
- 按可合并原则切分。
- 递归处理各部分。
- 合并阶段补回跨部分答案。
代码 / 示例
归并排序:分解到单元素 → 递归有序 → 合并两个有序段
常见误区
- 误区:分治子问题可以互相依赖;正解:子问题应独立,跨部分信息在合并层处理。
- 误区:分治一定比暴力快;正解:只有合并代价可控才会降低总复杂度。
追问
- Q:分治复杂度常用什么分析? A:递归树或主定理。
- Q:快排是分治吗? A:是,划分即分解,递归排序左右段。
02.6.1.1-016 递归中值传递、引用传递和全局变量怎么理解?
一句话结论
基本类型按值拷贝进栈帧,修改不影响上层;引用类型拷贝引用,指向同一对象,子层修改对象内容对上层可见;全局/成员变量被所有层共享,回溯时必须显式撤销。
概念解释
- 值拷贝:基本类型各层独立。
- 引用共享:对象内容跨层可见。
- 全局状态:多分支共用,需恢复。
原理流程
- 判断参数类型决定隔离性。
- 引用类型在回溯中做撤销。
- 全局变量逐层复位。
代码 / 示例
void dfs(List<Integer> path, int x) {
path.add(x); // 引用共享,子层可见
dfs(...);
path.remove(...); // 撤销,恢复现场
}
常见误区
- 误区:把对象当值传递以为互不影响;正解:引用指向同一堆对象。
- 误区:回溯结束不清空全局标记;正解:标记数组必须随分支撤销。
追问
- Q:为什么结果要
new ArrayList<>(path)? A:记录副本,避免后续撤销改动已存入结果。 - Q:成员变量能当递归状态吗? A:能用但易乱,优先参数传递。
02.6.1.1-017 递归代码怎么调试?
一句话结论
先打印入参与层级深度确认收敛方向,再用小用例单步跟踪栈帧进出,观察返回值合并;必要时画递归树对照调用顺序,定位是基准、递归关系还是返回值出错。
概念解释
- 深度标记:识别当前层。
- 入参检查:确认规模下降。
- 返回值检查:确认合并正确。
原理流程
- 小样本构造基准与一层递归。
- 逐层打印调用与返回。
- 对照递归树找首个错误层。
代码 / 示例
void dfs(int i, int depth) {
System.out.println("depth=" + depth + " i=" + i);
// ...
}
常见误区
- 误区:直接在大数组上调试递归;正解:先最小用例定位分支逻辑。
- 误区:只看最终结果不看中间合并;正解:递归错误常出在子结果合并层。
追问
- Q:递归死循环怎么发现? A:入参不向基准靠近,打印参数可见规模不变。
- Q:栈帧内容怎么查看? A:调试器调用栈面板逐层展开局部变量。
02.6.1.1-018 递归复杂度怎么和主定理衔接?
一句话结论
递归时间复杂度写成递推式 T(n)=aT(n/b)+f(n),用递归树逐层求和或主定理判断量级;空间复杂度看递归深度与每层额外空间。
概念解释
- 递推式:子问题个数 a、规模 n/b、本层代价 f(n)。
- 主定理:比较 f(n) 与 n^log_b a 的阶。
原理流程
- 写出递推式。
- 递归树累加每层代价。
- 用主定理校验量级。
代码 / 示例
归并:T(n)=2T(n/2)+O(n) → O(n log n)
二分:T(n)=T(n/2)+O(1) → O(log n)
常见误区
- 误区:递归复杂度只看递归次数;正解:还要算每层非递归工作(合并、扫描)。
- 误区:空间复杂度按节点总数算;正解:递归空间看同时存活的栈深度。
追问
- Q:主定理适用什么形式? A:子问题等规模、固定分裂系数的递推。
- Q:树状递归空间怎么估? A:O(h) 栈深 + 路径/输出空间。
02.6.1.1-019 递归转迭代的总思路是什么?
一句话结论
把每个栈帧需要保存的信息(参数、局部变量、执行到哪一步)压入显式栈,按后进先出模拟调用顺序;后序类问题还需记录“已处理子节点”状态,出栈时做合并。
概念解释
- 显式栈:手动维护帧。
- 执行位置:标记当前帧是刚进入还是子节点已返回。
- 合并:出栈阶段计算结果。
原理流程
- 拆解递归帧保存的状态。
- 压栈进入,标记待处理。
- 子帧完成后回到本帧合并。
代码 / 示例
显式栈元素:{入参, 状态位}
压入根 → 弹出处理 → 需要子问题则压回本帧并压子帧
常见误区
- 误区:迭代只把递归调用换成 while;正解:树形/后序逻辑必须保存返回点与局部状态。
- 误区:迭代栈顺序和递归完全一致;正解:子节点出栈顺序可能反转,需按题调整。
追问
- Q:DFS 迭代为什么用栈? A:栈 LIFO 保证深度优先。
- Q:BFS 对应什么结构? A:队列,层序扩展。
02.6.1.1-020 递归最常见的陷阱有哪些?
一句话结论
高频陷阱:缺终止条件或参数不收敛、返回值合并错误、引用类型未撤销/未拷贝、深度过大栈溢出、重复子问题未记忆化;逐条对照三要素即可规避。
概念解释
- 收敛性:规模必须下降。
- 现场管理:引用与全局状态恢复。
- 性能:重复计算与深度约束。
原理流程
- 先核对基准是否可达。
- 再核对参数下降方向。
- 最后检查现场恢复与复杂度。
代码 / 示例
检查清单:终止条件 / 参数收敛 / 返回合并 / 引用撤销 / 深度估算
常见误区
- 误区:程序能跑就说明递归正确;正解:分支遗漏、现场污染常在边界用例暴露。
- 误区:所有递归都该记忆化;正解:状态无重复或带路径依赖时记忆化无效。
追问
- Q:递归写出死循环的直接原因? A:递归参数没有向基准情形靠近。
- Q:递归结果被后续改动污染? A:结果存入的是路径引用,需存副本。