递归、搜索与回溯知识点整理一、递归Recursion1. 什么是递归递归的核心定义函数自己调用自己的过程是C语言与数据结构中的核心思想典型应用场景包括二叉树的遍历前/中/后序快速排序归并排序2. 为什么会用到递归递归的本质是问题的自相似性主问题可以被拆解为多个和原问题结构完全相同的子问题子问题又可以继续拆解为更小规模的、结构相同的子问题最终拆解到“足够简单、可直接解决”的边界情况递归出口例如二叉树遍历每个节点的遍历逻辑与它的左、右子树的遍历逻辑完全相同快排/归并排序每个子数组的排序逻辑与原数组的排序逻辑完全相同3. 如何理解递归三层递进理解法1 误区过度纠结递归展开的每一层调用栈细节容易陷入混乱。2 进阶把递归函数当成一个“黑盒”只关注它的输入和输出不用关心内部执行细节。3 终极心法不要在意递归的细节展开图把递归函数当成一个能完成特定任务的黑盒相信这个黑盒一定能完成任务基于数学归纳法的正确性示例二叉树前序遍历void dfs(TreeNode* root) { // 递归出口空树直接返回 if(root NULL) return; printf(root-val); // 处理当前节点 dfs(root-left); // 相信dfs能遍历左子树 dfs(root-right); // 相信dfs能遍历右子树 }示例归并排序void merge(int* nums, int left, int right) { // 递归出口区间内只有一个元素无需排序 if(left right) return; int mid (left right) / 2; merge(nums, left, mid); // 相信merge能排好左半部分 merge(nums, mid 1, right); // 相信merge能排好右半部分 mergeTwoSortedArrays(nums, left, mid, right); // 合并有序数组 }4. 如何写好一个递归三步走1 设计函数头先找到相同的子问题明确函数的输入参数和功能例如汉诺塔问题中函数功能是“将x柱上的n个盘子借助y柱移到z柱”。2 编写函数体只关心当前子问题的解决逻辑直接调用递归函数处理更小的子问题。3 设置递归出口当问题规模足够小时直接解决问题避免无限递归导致栈溢出。二、搜索相关概念DFS vs BFS1. 核心概念区分遍历是一种访问所有节点的形式搜索是遍历的目的用于寻找特定解。深度优先遍历/深度优先搜索DFS沿着一条路径尽可能深地搜索直到无法前进再回溯通常用递归或栈实现。广度优先遍历/广度优先搜索BFS按层遍历先访问当前层所有节点再访问下一层通常用队列实现。2. 关系梳理暴力枚举穷举所有情况的实现方式主要有两种DFS 和 BFS二者都是“搜索”的具体实现。例如全排列问题可以用DFS构建决策树遍历所有可能的路径得到所有排列结果。三、回溯与剪枝1. 回溯的本质回溯算法的本质是深度优先搜索DFS是一种暴力搜索的优化形式。它通过“尝试-失败-回退”的过程遍历所有可能的解空间找到满足条件的解。例如迷宫问题中遇到死路时回退到上一个节点尝试其他路径这就是回溯的过程。2. 剪枝的作用剪枝是回溯算法的关键优化手段在搜索过程中提前判断某些路径不可能得到有效解直接跳过这些路径避免无意义的搜索大幅提高效率。例如在迷宫中提前标记已经走过的路径避免重复访问或者根据问题规则直接排除不符合条件的分支。四、递归的定义与适用条件在解决一个大规模的问题时如果满足以下条件就可以使用递归解决1. 可拆分性问题可以被划分为规模更小的子问题且这些子问题与原问题的解决方法完全相同。2. 递推关系当知道规模为 n-1 的子问题的解时可以直接计算出规模为 n 的问题的解。3. 边界条件存在一个“简单情况”当问题规模足够小时可以直接求解无需继续递归。递归的一般求解过程1. 验证简单情况先处理递归的终止条件边界。2. 假设与递推假设较小规模的子问题已经解决基于此解决当前问题。注上述过程可以通过数学归纳法来证明其正确性。题目1汉诺塔问题LeetCode 面试题 08.061. 题目描述2. 核心递归思路汉诺塔是递归的经典案例核心思想是“分治”把大规模问题拆成小规模子问题递归解决子问题后再处理原问题。基础情况分析当 n1只有1个盘子直接把A柱上的盘子移到C柱即可。当 n22个盘子需要借助B柱中转共3步把A柱上的小盘子1号移到B柱把A柱上的大盘子2号移到C柱把B柱上的小盘子1号移到C柱。当 n2n个盘子可以复用 n2 的策略将问题拆分为3步把A柱上的n-1个盘子借助C柱中转全部移到B柱上把A柱上剩下的最大的1个盘子直接移到C柱上把B柱上的n-1个盘子借助A柱中转全部移到C柱上。关键逻辑移动过程中A柱上的最大盘子始终在最底部不会被其他盘子压住因此不会违反“大盘不压小盘”的规则。3. 递归函数设计与流程函数定义void dfs(vectorint a, vectorint b, vectorint c, int n)功能将 a 柱上的 n 个盘子借助 b 柱中转移动到 c 柱上。参数a源柱、b辅助柱、c目标柱、n当前需要移动的盘子数量。递归流程1. 边界条件n 1直接将 a 柱最顶端的盘子移到 c 柱if (n 1) { c.push_back(a.back()); a.pop_back(); return; }2. 第一步移动n-1个盘子到辅助柱将 a 柱上的 n-1 个盘子借助 c 柱中转移动到 b 柱dfs(a, c, b, n - 1);3. 第二步移动最大盘子到目标柱将 a 柱上剩下的最大盘子直接移到 c 柱c.push_back(a.back());a.pop_back();4. 第三步移动n-1个盘子到目标柱将 b 柱上的 n-1 个盘子借助 a 柱中转移动到 c 柱dfs(b, a, c, n - 1);#include vector using namespace std; class Solution { public: void hanota(vectorint a, vectorint b, vectorint c) { // 调用递归函数将a柱的所有盘子a.size()个借助b柱移到c柱 dfs(a, b, c, a.size()); } private: // 递归函数将a柱的n个盘子借助b柱移动到c柱 void dfs(vectorint a, vectorint b, vectorint c, int n) { // 边界条件只有1个盘子时直接移动 if (n 1) { c.push_back(a.back()); a.pop_back(); return; } // 1. 把a柱上的n-1个盘子借助c柱移到b柱 dfs(a, c, b, n - 1); // 2. 把a柱剩下的最大盘子直接移到c柱 c.push_back(a.back()); a.pop_back(); // 3. 把b柱上的n-1个盘子借助a柱移到c柱 dfs(b, a, c, n - 1); } };4. 关键知识点总结1 递归的核心思想把复杂的大问题拆成和原问题解法相同、规模更小的子问题通过“递推”“回归”解决。2 汉诺塔的递推公式移动n个盘子需要的步数为 2ⁿ - 1例如n3时需要7步n14时需要16383步。3 栈的特性用 vector 模拟栈back() 取栈顶元素pop_back() 弹出栈顶元素push_back() 压入栈顶元素完全符合题目中“顶端移动”的规则。4 参数的传递逻辑递归调用时辅助柱和目标柱会动态切换以实现“中转”的效果这是汉诺塔递归实现的关键。题目2合并两个有序链表LeetCode 211. 题目描述提示两个链表的节点数目范围是[0, 50]-100 Node.val 100l1和l2均按非递减顺序排列2. 递归解法核心知识点1 递归函数的含义递归函数的定义是传入两个链表的头结点返回合并后链表的头结点。它的作用是帮你把两个有序链表合并成一个有序链表并返回合并后的头。2 算法核心思路递归的核心是分而治之每次解决“当前一步”的问题剩下的交给递归处理1. 选头结点比较两个链表的头结点值选择值较小的节点作为合并后链表的当前头结点。2. 递归处理剩余部分将“值较小节点的下一个节点”和“另一个链表的头结点”作为新的参数继续递归合并。3. 拼接结果将步骤2中递归返回的结果接到步骤1中选出的头结点后面。4. 返回头结点将当前选出的头结点作为结果返回供上一层调用。3 递归出口终止条件当某一个链表为空nullptr时直接返回另一个链表。若 l1 nullptr说明 l1 已经遍历完直接返回 l2 剩余部分即可。若 l2 nullptr同理直接返回 l1 剩余部分。4 关键注意事项链表题必须画图理解指针操作明确谁是当前节点谁是下一个节点递归返回的结果要接在谁的后面/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 递归出口某一个链表为空直接返回另一个 if(l1 nullptr) return l2; if(l2 nullptr) return l1; // 选值较小的节点作为当前头结点 if(l1-val l2-val) { // 递归合并 l1-next 和 l2结果接在 l1 后面 l1-next mergeTwoLists(l1-next, l2); return l1; } else { // 递归合并 l1 和 l2-next结果接在 l2 后面 l2-next mergeTwoLists(l1, l2-next); return l2; } } };3. 知识点拓展1 时间复杂度递归的次数等于两个链表的总节点数每次递归只做一次比较和一次指针赋值因此时间复杂度为O(n m)其中 n、m 分别为两个链表的长度。2 空间复杂度递归调用栈的深度等于两个链表的总节点数因此空间复杂度为O(n m)递归栈开销。3 易错点总结空指针判断必须先判断链表是否为空否则访问 l1-val 会导致程序崩溃。指针赋值方向l1-next mergeTwoLists(...) 是关键不要搞反两个链表的参数顺序。非递减顺序题目中是“非递减”因此判断条件用 即可无需严格 。题目3反转链表LeetCode 2061. 题目描述示例 3输入head []输出[]提示链表中节点的数目范围是[0, 5000]-5000 Node.val 50002. 递归解法核心知识点1 递归函数的含义递归函数的作用传入一个链表的头指针返回反转后链表的头结点。2 算法核心思路递归的本质是“分而治之”核心步骤分为三步1. 递归处理后半段先把当前结点之后的链表反转得到反转后链表的头结点 newHead。2. 调整指针指向将当前结点的下一个结点的 next 指向当前结点实现反转。3. 处理尾结点将当前结点的 next 置为 nullptr避免链表出现环。4. 返回结果返回反转后链表的头结点 newHead。3 递归出口终止条件当链表为空 head nullptr或链表只有一个结点 head-next nullptr 时无需反转直接返回 head 即可。4 关键注意事项链表题必须画图理解指针操作明确每个结点的 next 指向变化。必须将原链表的头结点反转后的尾结点的 next 置为 nullptr否则会形成环形链表。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { // 递归出口链表为空或只有一个结点直接返回 if (head nullptr || head-next nullptr) return head; // 1. 递归处理 head-next 之后的链表得到反转后的头结点 ListNode* newHead reverseList(head-next); // 2. 调整指针让 head-next 的 next 指向 head head-next-next head; // 3. 处理尾结点将当前 head 的 next 置为 nullptr避免成环 head-next nullptr; // 4. 返回反转后链表的头结点 return newHead; } };3. 知识点拓展1 复杂度分析时间复杂度O(n)每个结点仅被访问一次其中 n 为链表长度。空间复杂度O(n)递归调用栈的深度等于链表长度最坏情况下链表长度为 n需要 n 层栈空间。2 易错点总结1. 指针指向错误忘记设置 head-next nullptr会导致反转后的链表形成环程序运行时死循环。2. 递归出口缺失没有处理链表为空的情况会导致空指针访问异常。3. 返回值错误误将 head 作为返回值而不是递归返回的 newHead导致反转后的链表头结点丢失。4. 迭代解法补充对比学习如果需要空间复杂度为 O(1) 的解法可以使用迭代法class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; // 前一个结点 ListNode* curr head; // 当前结点 while (curr ! nullptr) { ListNode* nextTemp curr-next; // 保存下一个结点 curr-next prev; // 反转指针 prev curr; // prev 后移 curr nextTemp; // curr 后移 } return prev; } };时间复杂度O(n) 空间复杂度O(1)仅使用常数额外空间。题目4两两交换链表中的节点LeetCode 241. 题目描述提示链表中节点的数目在范围[0, 100]内0 Node.val 1002. 递归解法核心解析1 递归函数的含义递归函数的作用传入一个链表的头指针返回两两交换完成后的链表头结点。2 算法核心思路递归的本质是分而治之核心步骤分为三步1. 递归处理后半段先处理从第三个节点开始的子链表返回其交换后的头结点 tmp。2. 交换当前两个节点原顺序head → head-next → 子链表交换后head-next → head → tmp3. 返回新头结点head-next 会成为当前层的新头结点将其返回给上一层。3 递归出口终止条件当链表为空 head nullptr 时直接返回 nullptr。当链表只有一个节点 head-next nullptr 时无需交换直接返回 head。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { // 递归出口链表为空或只有一个节点直接返回 if (head nullptr || head-next nullptr) return head; // 1. 递归处理后续子链表从第3个节点开始 auto tmp swapPairs(head-next-next); // 2. 保存当前层交换后的新头结点原第二个节点 auto ret head-next; // 3. 调整指针将当前节点的next指向tmp完成交换 head-next-next head; // 原第二个节点的next指向原第一个节点 head-next tmp; // 原第一个节点的next指向递归返回的子链表头 // 4. 返回当前层交换后的新头结点 return ret; } };3. 关键细节与易错点1 必须画图理解指针操作链表题的核心是指针的指向变化画图能帮你清晰看到每个步骤的节点连接关系避免逻辑混乱。2 交换顺序不能错必须先处理子链表再调整当前节点的指针否则会丢失后续节点的引用。3 返回值易错ret原第二个节点才是当前层交换后的新头结点不能直接返回 head。4 边界处理注意空链表、单节点链表的情况避免空指针访问异常。4. 复杂度分析时间复杂度O(n)每个节点仅被访问一次其中 n 为链表长度。空间复杂度O(n)递归调用栈的深度为链表长度的一半最坏情况下需要 n/2 层栈空间。5. 拓展迭代解法空间复杂度O(1)如果需要常数级空间复杂度可以使用迭代法class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next ! nullptr prev-next-next ! nullptr) { ListNode* first prev-next; ListNode* second prev-next-next; // 交换节点 first-next second-next; second-next first; prev-next second; // 移动指针 prev first; } return dummy.next; } };题目5Pow(x, n)LeetCode 501. 题目描述2. 递归快速幂解法核心解析1 核心思想分治法二分法class Solution { public: double myPow(double x, int n) { // 处理负指数注意n为-2^31时直接取反会溢出需转成long long return n 0 ? 1.0 / pow(x, -(long long)n) : pow(x, (long long)n); } private: // 递归快速幂n为非负整数 double pow(double x, long long n) { // 递归出口n0时返回1 if (n 0) return 1.0; // 分治先计算x^(n/2) double tmp pow(x, n / 2); // 根据n的奇偶性返回结果 return n % 2 0 ? tmp * tmp : tmp * tmp * x; } };3. 关键细节与易错点1 整数溢出问题int 范围为 -2^{31} 2^{31}-1当 n -2^31 时直接写 -n 会溢出必须先转成 long long 再取反。2 负指数处理x^{-n} 1 / x^n不能直接在递归函数中处理负指数否则 n/2 向下取整会出错。3 浮点数精度题目允许一定精度误差使用 double 计算即可满足要求。4 递归效率递归深度为 O(log n)远优于暴力法的 O(n)时间复杂度为 O(log n)空间复杂度为 O(log n)递归栈开销。4. 复杂度分析时间复杂度O(log n)每次递归/迭代将指数折半共需 log n 次计算。空间复杂度递归法为 O(log n)递归栈迭代法为 O(1)。5. 拓展迭代快速幂空间复杂度O(1)如果需要常数级空间复杂度可以用迭代法实现class Solution { public: double myPow(double x, int n) { long long N n; if (N 0) { x 1 / x; N -N; } double res 1.0; while (N 0) { if (N % 2 1) { res * x; } x * x; N / 2; } return res; } };