C++ 遞歸、搜索與回溯:三劍客
更新時間：2026年04月10日 08:52:32 作者：JAVA+C語言
本文介紹了C++遞歸、搜索、回溯三大核心內(nèi)容,下面用最清晰、最容易理解的方式,一次性講透 C++ 遞歸、搜索、回溯三大核心內(nèi)容,適合學(xué)習(xí)、復(fù)習(xí)、寫題,感興趣的朋友跟隨小編一起看看吧
下面用最清晰、最容易理解的方式，一次性講透 C++ 遞歸、搜索、回溯三大核心內(nèi)容，適合學(xué)習(xí)、復(fù)習(xí)、寫題。
一、遞歸（Recursion）
1. 概念
函數(shù)自己調(diào)用自己，把大問題拆成更小的同類型問題。
2. 兩個必備條件
- 遞歸出口（base case）：不再遞歸，直接返回結(jié)果
- 遞歸式：把問題規(guī)?？s小
3. 經(jīng)典示例：求階乘
int fact(int n) {
if (n == 0) return 1; // 出口
return n * fact(n - 1); // 遞歸式
}4. 本質(zhì)
- 系統(tǒng)使用棧保存每一層調(diào)用
- 太深會棧溢出（stack overflow）
二、搜索（Search）
搜索就是在所有可能情況里找答案。常見兩類：
- 深度優(yōu)先搜索 DFS（一條路走到底）
- 廣度優(yōu)先搜索 BFS（一層層擴散）
遞歸最常配合 DFS。
三、回溯（Backtracking）
1. 概念
遞歸搜索 + 撤銷選擇 = 回溯
- 選一條路走
- 走不通就回退一步
- 嘗試其他可能
典型場景：排列、組合、子集、N 皇后、數(shù)獨
2. 回溯通用模板（必背）
void backtrack(路徑, 選擇列表) {
if (滿足結(jié)束條件) {
記錄答案;
return;
}
for (選擇 : 選擇列表) {
做選擇;
backtrack(路徑, 選擇列表);
撤銷選擇; // 回溯核心
}
}四、三個經(jīng)典例子（一看就懂）
例 1：全排列（回溯經(jīng)典）
求 [1,2,3] 的所有排列
vector<vector<int>> res;
vector<int> path;
bool vis[10];
void dfs(vector<int>& nums) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (vis[i]) continue;
vis[i] = 1;
path.push_back(nums[i]);
dfs(nums);
path.pop_back(); // 回溯
vis[i] = 0;
}
}例 2：子集（搜索所有可能）
void dfs(vector<int>& nums, int u) {
res.push_back(path);
for (int i = u; i < nums.size(); i++) {
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}例 3：斐波那契（純遞歸）
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}五、三者關(guān)系（一句話總結(jié)）
- 遞歸：函數(shù)自己調(diào)用自己，是實現(xiàn)方式
- 搜索：遍歷所有可能，是算法思想
- 回溯：遞歸搜索 + 撤銷選擇，是搜索的一種通用寫法
六、最?？碱}型
- 全排列、組合、子集
- N 皇后
- 數(shù)獨
- 電話號碼字母組合
- 矩陣中的路徑（單詞搜索）
- 分割回文串
到此這篇關(guān)于C++ 遞歸、搜索與回溯的文章就介紹到這了,更多相關(guān)C++ 搜索與回溯內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
今天給大家?guī)淼氖顷P(guān)于Java的相關(guān)知識,文章圍繞著Java String類用法展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下2021-08-08
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單反彈球消磚塊游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細介紹了C++實現(xiàn)簡易萬年歷，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10![深入理解char *a與char a[]的區(qū)別](http://img.jbzj.com/images/xgimg/bcimg3.png)
很多人可能或多或少知道char *a與char a[]的一些區(qū)別，但如果詳細的說出來卻不知如何說去，下面這篇文章就給大家詳細介紹了關(guān)于C語言中char *a與char a[]的區(qū)別，有需要的朋友們可以參考借鑒，下面來一起學(xué)習(xí)學(xué)習(xí)吧。2016-12-12
這篇文章主要介紹了windows消息和消息隊列實例詳解,詳細講述了Windows的消息機制與原理,對于深入理解和學(xué)習(xí)Windows應(yīng)用程序設(shè)計有不錯的借鑒價值,需要的朋友可以參考下2014-10-10
rand()函數(shù)用來產(chǎn)生隨機數(shù)，但是，rand()的內(nèi)部實現(xiàn)是用線性同余法實現(xiàn)的，是偽隨機數(shù)，由于周期較長，因此在一定范圍內(nèi)可以看成是隨機的。srand()用來設(shè)置rand()產(chǎn)生隨機數(shù)時的隨機數(shù)種子。參數(shù)seed是整數(shù)，通常可以利用time(0)或geypid(0)的返回值作為seed2023-02-02
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單五子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
這篇文章主要為大家詳細介紹了C++中類的this指針以使用，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
Qt是一個跨平臺C++開發(fā)框架,包含GUI、網(wǎng)絡(luò)、SQL、多媒體等模塊,安裝后自帶豐富工具鏈,若未正確配置環(huán)境變量會導(dǎo)致一系列問題,因此建議根據(jù)實際開發(fā)場景,合理設(shè)置局部或臨時Qt環(huán)境變量,實現(xiàn)靈活且可控的開發(fā)體驗,所以本文介紹了Windows配置Qt環(huán)境變量的全指南2025-07-07
這篇文章主要介紹了C++ 容器 Vector 的使用方法，Vector 是一個能夠存放任意類型的動態(tài)數(shù)組，有點類似數(shù)組，是一個連續(xù)地址空間，下文更多詳細內(nèi)容的介紹，需要的小伙伴可以參考一下2022-07-07