信息技术大学
递归与分治
数据结构与算法·面试高频 · 第 4 章 算法思想
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
递归与分治
数据结构与算法·面试高频 · 第 4 章 算法思想
递归三要素
递归不玄：明确函数职责、找递推关系、定终止条件，三件齐了再动笔。
职责
函数只回答一个问题，定义清晰不越界
递推
大问题怎么拆成小问题，信任返回值
终止
最小子问题直接给答案，防无限下钻
子集与全排列
子集是「选或不选」，排列是「每个位置谁上」：树形决策画出来再写。
子集树
每元素二选一，2^n 个叶子即全部子集
排列树
used 数组排除在岗者，共 n! 条路径
去重
排序后同层跳过相同元素，防重复解
组合总和系列
可重复选、不可重复用、去重组合：同框架三变体，差异全在「下一层从谁开始」。
可重复
递归起点仍是 i，允许反复选同一个
不可重复
起点移到 i+1，排序后跳过同值元素
剪枝
排序后前缀和超目标值整枝砍断
分治与主定理
分治三步：分、治、合。合并往往是成本大头，主定理给出总账公式。
三步
分半、递归求解、线性合并
主定理
T(n)=aT(n/b)+f(n)，比较 f 与子项定阶
典型
归并 O(n log n)，快排期望同阶
本节要点
- ✓递归三要素：职责、递推、终止
- ✓子集选不选，排列排谁上
- ✓组合变体：起点与去重剪枝
- ✓分治的合并是成本大头
延伸主题：手写全排列去重版复述主定理三情形
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1排列问题里 used 数组与「起点后移」有什么本质区别？
参考答案排列关心顺序，同一集合换序是新解，用 used 标记谁在岗；组合不关心顺序，用起点后移保证只向前选，天然不重复。一个是标记问题，一个是顺序约定。
2递归深度过大会怎样，工程上怎么应对？
参考答案栈溢出或撞语言深度上限。应对：改成显式栈的迭代、减小分治深度、或用记忆化砍掉重复下钻。递归是思维工具，落地常要转迭代。
3为什么「信任递归返回值」能成立？
参考答案数学归纳：基例正确、递推正确，则可假设子问题已正确解决，当前层只负责正确组合子答案。每层只管「要什么」不管「怎么算」，这是递归心法。