【递归、搜索与回溯算法】(递归问题拆解与经典模型实战大秘笈)
在算法学习的过程中,递归、搜索与回溯,几乎是每一个程序员都绕不开的核心内容.很多人第一次接触递归时,都会觉得它"看起来简单,写起来困难;题目好像能看懂,代码却总是写不出来".尤其是一遇到树结构、深度优先搜索、排列组合、子集划分、路径查找这类问题时,常常会陷入"知道可能要用递归,但不知道函数该怎么定义、边界该怎么设、过程该怎么回退"的困惑之中.事实上,递归并不可怕,真正难的也从来不是"函数调用自己"这件事,而是能否建立起一种清晰的问题拆解思维.因为递归的本质,不是机械地重复调用,而是把一个复杂问题不断拆分成规模更小、结构相同的子问题,再通过边界条件和返回过程层层求解.搜索则是在这种递归框架下,对解空间进行系统性探索;而回溯,则是在搜索过程中,面对一条路径走不通时,能够及时撤销选择、返回上一步、继续尝试其他可能.三者看似不同,实则紧密相连,共同构成了算法题中极其重要的一套解题方法论.本篇文章将围绕"递归、搜索与回溯算法"这一主题,从思想理解到实战应用,系统梳理这类问题的核心本质.你将看到:什么是递归,为什么很多问题天然适合用递归解决;搜索和回溯究竟与递归是什么关系;面对一道题时,如何准确判断它是不是递归模型;又该如何一步步拆解问题、设计函数、确定边界、组织状态,并最终写出结构清晰、逻辑严谨的代码.除了基础原理之外,文章还会结合经典模型与典型案例,帮助你真正建立"会想、会写、会调试"的递归思维.无论你是刚接触算法的新手,还是在刷题过程中总被递归和回溯卡住的学习者,相信读完这篇文章后,你都会对这类问题有一个更系统、更深入、也更实用的认识.接下来,就让我们从递归的本质出发,一步一步拆开这套看似抽象、实则极具规律性的算法思想.废话不多说,下面跟着小编的节奏🎵一起去疯狂的学习吧!
1.递归问题算法思想背景
1.什么是递归?
递归就是:一个函数在其定义过程中,直接或间接调用自己.在C++里最典型的形式就是:
int f(int n) {
if (/* 终止条件 */) {
return ...;
}
return f(n - 1); //调用自己
}
但"调用自己"不是重点,重点是:把一个大问题，拆成一个规模更小、但本质相同的子问题.也就是说,递归本质上是一种 问题分解方法,函数自己调用自己只是代码表现形式.
2.为什么会用递归?
- 因为很多问题天然就长成"递归结构".问题本身可以不断拆小比如阶乘:n! = n * (n - 1)! 要算n!,你只要会算 (n - 1)! 就行.
- 数据结构天然是层级结构
比如:
(1)二叉树
(2)目录/文件夹
(3)图的深度优先搜索
(4)嵌套表达式
(5)归并排序、快速排序
例如二叉树：
(1)一棵树 = 根节点 + 左子树 + 右子树
(2)左子树本身又是一棵树
(3)右子树本身又是一棵树
这就是典型的"自相似结构",非常适合递归.
- 有些搜索问题用递归最自然
比如:
(1)全排列
(2)组合
(3)子集
(4)N 皇后
(5)回溯搜索 - 因为过程往往是:
(1)先做一个选择
(2)递归处理剩余问题
(3)回退，尝试别的选择
3.如何理解递归?
很多人学不会递,不是因为语法难,而是因为总想把每一层都在脑子里完整展开.其实理解递归最重要的一句话是:不要试图同时看懂所有层,只看清当前这一层的定义.
4.理解递归的核心思想
写递归时,你要先定义:func(x) 到底表示什么?一旦定义清楚,就"相信它".
例如:
int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}
这里你要这样理解:
• factorial(n) 的定义：返回 n 的阶乘
• 那么 factorial(n - 1) 的定义：返回 n - 1 的阶乘
• 所以 factorial(n) = n * factorial(n - 1)
你不需要一开始就追踪 5 层、10 层调用细节.你只要相信"子问题会被正确解决".这就是理解递归最关键的思维方式:只考虑当前层怎么利用子问题,不要过度沉迷调用展开.
5.递归一定包含的两个要素
- 第一:终止条件也叫边界条件.如果没有终止条件,函数会无限调用自己,最后导致栈溢出.
- 第二:递归关系也叫状态转移或问题缩小方式.每次递归都必须让问题规模更小,逐渐逼近终止条件.
6.如何写好一个递归?
这是最关键的部分.
-
第一步:先定义函数含义这是最重要的.你必须先明确:这个函数到底在解决什么问题?
例如：
• factorial(n)：返回 n!
• sum(arr, n)：返回前 n 个元素之和
• maxDepth(root)：返回以 root 为根的树的最大深度
• dfs(u)：遍历从节点 u 开始的所有可达节点
函数定义越清晰,递归越容易写. -
第二步:写终止条件问自己:最简单的情况是什么?这个时候能不能直接得到答案?
例如:
if (n == 0) return 0;
if (root == nullptr) return 0;
终止条件一定要简单、明确、可达.
- 第三步:写"缩小问题"的方式问自己:如果子问题已经解决了,当前问题如何用子问题得到答案?
比如:
return n * factorial(n - 1);
或者:
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
- 第四步:检查规模是否真的变小这是很多人最容易犯错的地方.
错误例子:
int f(int n) {
return f(n);
}
这根本没有缩小问题,必然死递归.
正确递归必须满足:
• 参数在变化
• 子问题规模更小
• 能一步步走到终止条件
2.汉诺塔问题(OJ题)
算法思路:解法(递归):
这是一道递归方法的经典题目,我们可以先从最简单的情况考虑"
- 假设n = 1,只有一个盘子,很简单,直接把它从 A 中拿出来,移到C上;
- 如果n =2呢?这时候我们就要借助B了,因为小盘子必须时刻都在大盘子上面,共需要3步(为了方便叙述,记A中的盘子从上到下为1号,2号):
a. 1号盘子放到 B 上;
b. 2号盘子放到 C 上;
c. 1号盘子放到 C 上.
至此,C 中的盘子从上到下为1号,2 号. - 如果n > 2呢?这时我们需要用到n =2时的策略,将A上面的两个盘子挪到B上,再将最大的盘子挪到C 上,最后将B上的小盘子挪到C上就完成了所有步骤.例如n = 3时如下图:
因为A中最后处理的是最大的盘子,所以在移动过程中不存在大盘子在小盘子上面的情况.
则本题可以被解释为:
- 对于规模为n的问题,我们需要将A柱上的n个盘子移动到C柱上.
- 规模为n的问题可以被拆分为规模为n-1的子问题:
a. 将A柱上的上面n-1个盘子移动到B柱上.
b. 将A柱上的最大盘子移动到C柱上,然后将B柱上的n-1个盘子移动到C柱上. - 当问题的规模变为n=1时,即只有一个盘子时,我们可以直接将其从A柱移动到C柱.
- 需要注意的是,步骤2.b考虑的是总体问题中的子问题b情况.在处理子问题的子问题b时,我们应该将A柱中的最上面的盘子移动到C柱,然后再将B柱上的盘子移动到C柱.在处理总体问题的子问题b时,A柱中的最大盘子仍然是最上面的盘子,因此这种做法是通用的.
算法流程:
递归函数设计：void hanotaa(vector<int>& A, vector<int>& B, vector<int>& C, int n)
- 返回值：无;
- 参数：三个柱子上的盘子,当前需要处理的盘子个数(当前问题规模).
- 函数作用：将A中的上面n个盘子挪到C中.
递归函数流程:
- 当前问题规模为n=1时,直接将A中的最上面盘子挪到C中并返回;
- 递归将A中最上面的n-1个盘子挪到B中;
- 将A中最上面的一个盘子挪到C中;
- 将B中上面n-1个盘子挪到C中.
核心代码
class Solution
{
public:
void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
{
dfs(a, b, c, a.size());
}
void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n) //这个函数的含义是：把a上面的n个盘子,借助b,移动到c
{
if (n == 1)
{
c.push_back(a.back());
a.pop_back();
return;
}
dfs(a, c, b, n - 1);//把a上的n-1个盘子,借助c,移动到b
c.push_back(a.back());
a.pop_back();
dfs(b, a, c, n - 1);//把b上的n-1个盘子,借助a,移动到c
}
};
完整测试代码
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
{
dfs(a, b, c, a.size());
}
void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
{
if (n == 1)
{
c.push_back(a.back());
a.pop_back();
return;
}
dfs(a, c, b, n - 1);
c.push_back(a.back());
a.pop_back();
dfs(b, a, c, n - 1);
}
};
void printVector(const vector<int>& v, const string& name)
{
cout << name << ": [";
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i];
if (i != v.size() - 1) cout << ", ";
}
cout << "]" << endl;
}
int main()
{
Solution solution;
// 测试数据：A 柱子上有 3 个盘子，数字越大盘子越大
vector<int> A = {2, 1, 0};
vector<int> B;
vector<int> C;
cout << "移动前：" << endl;
printVector(A, "A");
printVector(B, "B");
printVector(C, "C");
solution.hanota(A, B, C);
cout << "\n移动后：" << endl;
printVector(A, "A");
printVector(B, "B");
printVector(C, "C");
return 0;
}
3.合并两个有序链表(OJ题)
算法思路:解法(递归):
-
递归函数的含义：交给你两个链表的头结点,你帮我把它们合并起来,并且返回合并后的头结点;
-
函数体：选择两个头结点中较小的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数去处理;
-
递归出口：当某一个链表为空的时候,返回另外一个链表.
-
把以 l1 为头的有序链表和以 l2 为头的有序链表合并,返回合并后链表的头结点.这是理解递归最关键的一步.
-
如果 l1 为空意思是:
• 如果第一个链表已经没节点了
• 那就直接返回第二个链表
因为第二个链表本来就是有序的,不需要再处理. -
如果 l2 为空,同理:
• 如果第二个链表空了
• 那就直接返回第一个链表 -
如果 l1 当前节点更小,或者相等,那么合并后的链表头结点就应该是 l1.因为两个链表都是升序的,谁小谁就该排前面.
-
每次从两个链表头结点中选出较小的那个作为当前结果节点,然后递归处理剩余部分.
核心代码
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 = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
完整测试代码
#include <iostream>
#include <vector>
using namespace std;
//链表节点定义
struct ListNode
{
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
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 = mergeTwoLists(l1->next, l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
//根据数组创建链表
ListNode* createList(const vector<int>& nums)
{
ListNode dummy(0);
ListNode* tail = &dummy;
for (int x : nums)
{
tail->next = new ListNode(x);
tail = tail->next;
}
return dummy.next;
}
//打印链表
void printList(ListNode* head)
{
while (head != nullptr)
{
cout << head->val;
if (head->next != nullptr)
cout << " -> ";
head = head->next;
}
cout << endl;
}
//释放链表内存
void freeList(ListNode* head)
{
while (head != nullptr)
{
ListNode* temp = head;
head = head->next;
delete temp;
}
}
int main()
{
Solution solution;
//测试数据
vector<int> nums1 = {1, 2, 4};
vector<int> nums2 = {1, 3, 4};
//创建两个有序链表
ListNode* l1 = createList(nums1);
ListNode* l2 = createList(nums2);
cout << "合并前：" << endl;
cout << "l1: ";
printList(l1);
cout << "l2: ";
printList(l2);
//合并链表
ListNode* merged = solution.mergeTwoLists(l1, l2);
cout << "\n合并后：" << endl;
cout << "merged: ";
printList(merged);
//释放内存
freeList(merged);
return 0;
}
4.反转链表(OJ题)
算法思路:解法(递归):
- 递归函数的含义：交给你一个链表的头指针,你帮我逆序之后,返回逆序后的头结点;
- 函数体：先把当前结点之后的链表逆序,逆序完之后,把当前结点添加到逆序后的链表后面即可,
- 递归出口：当前结点为空或者当前只有一个结点的时候,不用逆序,直接返回.
核心代码
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
完整测试代码
#include <iostream>
#include <vector>
using namespace std;
//链表节点定义
struct ListNode
{
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
//根据数组创建链表
ListNode* createList(const vector<int>& nums)
{
ListNode dummy(0);
ListNode* tail = &dummy;
for (int x : nums)
{
tail->next = new ListNode(x);
tail = tail->next;
}
return dummy.next;
}
//打印链表
void printList(ListNode* head)
{
while (head != nullptr)
{
cout << head->val;
if (head->next != nullptr)
cout << " -> ";
head = head->next;
}
cout << " -> nullptr" << endl;
}
//释放链表内存
void freeList(ListNode* head)
{
while (head != nullptr)
{
ListNode* temp = head;
head = head->next;
delete temp;
}
}
int main()
{
Solution solution;
//测试数据
vector<int> nums = {1, 2, 3, 4, 5};
//创建链表
ListNode* head = createList(nums);
cout << "反转前：" << endl;
printList(head);
//调用反转函数
ListNode* newHead = solution.reverseList(head);
cout << "反转后：" << endl;
printList(newHead);
//释放内存
freeList(newHead);
return 0;
}
5.两两交换链表中的节点(OJ题)
算法思路:解法(递归):
- 递归函数的含义：交给你一个链表,将这个链表两两交换一下,然后返回交换后的头结点;
- 函数体：先去处理一下第二个结点往后的链表,然后再把当前的两个结点交换一下,连接上后面处理后的链表;
- 递归出口：当前结点为空或者当前只有一个结点的时候,不用交换,直接返回.
核心代码
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head;
auto tmp = swapPairs(head->next->next);
auto ret = head->next;
head->next->next = head;
head->next = tmp;
return ret;
}
};
完整测试代码
#include <iostream>
#include <vector>
using namespace std;
//链表节点定义
struct ListNode
{
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head;
auto tmp = swapPairs(head->next->next);
auto ret = head->next;
head->next->next = head;
head->next = tmp;
return ret;
}
};
//根据数组创建链表
ListNode* createList(const vector<int>& nums)
{
ListNode dummy(0);
ListNode* tail = &dummy;
for (int x : nums)
{
tail->next = new ListNode(x);
tail = tail->next;
}
return dummy.next;
}
//打印链表
void printList(ListNode* head)
{
while (head != nullptr)
{
cout << head->val;
if (head->next != nullptr)
cout << " -> ";
head = head->next;
}
cout << " -> nullptr" << endl;
}
//释放链表内存
void freeList(ListNode* head)
{
while (head != nullptr)
{
ListNode* temp = head;
head = head->next;
delete temp;
}
}
void test(const vector<int>& nums)
{
Solution solution;
ListNode* head = createList(nums);
cout << "原链表: ";
printList(head);
ListNode* newHead = solution.swapPairs(head);
cout << "交换后: ";
printList(newHead);
cout << "------------------------" << endl;
freeList(newHead);
}
int main()
{
test({1, 2, 3, 4});
test({1, 2, 3});
test({1, 2});
test({1});
test({});
return 0;
}
6.pow幂函数(OJ题)
算法思路:解法(递归 - 快速幂):
- 递归函数的含义：求出 x 的 n 次方是多少,然后返回;
- 函数体：先求出 x 的 n / 2 次方是多少,然后根据 n 的奇偶,得出 x 的 n 次方是多少;
- 递归出口：当 n 为 0 的时候,返回 1 即可.
核心代码
class Solution
{
public:
double myPow(double x, int n)
{
return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
}
double pow(double x, long long n)
{
if (n == 0)
return 1.0;
double tmp = pow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
};
完整测试代码
#include <iostream>
#include <iomanip>
using namespace std;
class Solution
{
public:
double myPow(double x, int n)
{
return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
}
double pow(double x, long long n)
{
if (n == 0)
return 1.0;
double tmp = pow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
};
void test(double x, int n)
{
Solution solution;
double ans = solution.myPow(x, n);
cout << "x = " << x << ", n = " << n << endl;
cout << "myPow(x, n) = " << fixed << setprecision(10) << ans << endl;
cout << "-----------------------------" << endl;
}
int main()
{
test(2.0, 10);
test(2.1, 3);
test(2.0, -2);
test(2.0, 0);
test(-2.0, 3);
test(-2.0, 4);
return 0;
}
敬请期待下一篇文章内容:【递归、搜索与回溯算法】(二叉树深搜模型拆解与经典题型全面突破)
每日心灵鸡汤:🚴致自己逝去的青春,砥砺前行共赴山海🚴
我经常会在睡不着的时候反思,反思我走过的路,我做过的决定,如果可以重来的话,我会不会做出不同的选择.我也会在某一个瞬间觉得自己走错了很多路,但它们都成为了我人生宝贵的经历,任何人与事给予的经历,不是得到就是学到,以前心心念念的东西现在不想要了,以前较真的东西现在不在乎了.我很感谢生活赠予我的一切惊慌失措,我也始终相信人生没有白走的路,也许真正的成长不是焦虑地怀疑自我,而是平静地自我接纳;不是对自己和他人的不满,而是被生活的无奈打磨之下,还能勇敢向前.时间能改变生活和人,时间也从来没让我原谅过任何人,我只是不在乎了……事事难两全,得失总相伴,勇敢的往前走,一切总会好起来!我一个人坐了好久好久,想起了很多事,突然很怀念以前的自己.回头看看自己走过的路,吃过的苦,受过的委屈,流过的眼泪,在不知不觉中,已经熬过了这么多的委屈和不甘.这一路走来,跌跌撞撞,我没有了以前的骄傲,也失去了原来的模样.从幼稚到成熟,从单纯到复杂,从直来直去到小心翼翼,从没心没肺到充满防备.曾经那个简单快乐的自己,再也回不去了.到了现在年纪,讲过去像是在卖惨,讲未来像是在白日做梦,讲现在又是旁观者迷,迟迟无语,字字心酸.我瞒着所有人,装着迈过很多次坎,装做很幸福的样子.其实只有我自己知道,有些坎,我永远都迈不过去.成年人的世界,哪有容易二字?晚风吹人醒,万事藏于心.我没说不公平,我也没有抱怨,我说我知道了.以前睡不着,是因为睡太多了;现在睡不着,是因为想太多了——因为人,因为事,因为烦恼,还有不尽人意的生活.没有人知道,你三更半夜睡不着在熬什么.那些回不去的,总有它回不去的道理.很多时候,表面上装做无所谓,其实心里有太多太多的心酸和委屈,无法诉说.一路走来,跌跌撞撞,一步一个教训.没有任何人能成为谁的避风港.有泪自己擦,有痛自己忍;累了憋着,苦了憋着,委屈了憋着,病了憋着,想哭的时候憋着.天大的事,自己扛.除了坚强,别无选择.何以言?何能言?与谁言?
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
24
0- 0
已为社区贡献6条内容
所有评论(0)