遞歸→搜索→回溯

名詞解釋

遞歸

1.什么是遞歸
形象地說就是函數自己調用自己。

例子：
二叉樹的遍歷-后序遍歷

void dfs(treenode* root)
{//細節 - 出口if(root == NULL) return;dfs(root->left);dfs(root->right);printf(root->val);
}

快排

void quickSort(nums)
{// 基線條件：數組長度≤1時無需排序if 數組長度(arr) ≤ 1:return arr// 1. 選基準（此處選第一個元素）pivot = arr[0]// 2. 分兩堆：小于等于基準的放left，大于基準的放rightleft = [所有 arr 中 ≤ pivot 的元素（除基準外）]right = [所有 arr 中 > pivot 的元素]// 3. 遞歸排序子數組，再合并結果return quickSort(left) + [pivot] + quickSort(right)
}

歸并排序

void merge(nums, int left, int right)
{//細節 - 出口if(left >= right) return;int mid = (left +right)/2;merge(nums, left, mid);merge(nums, mid, right);合并兩個有序數組
}

2.遞歸的本質
本質：
主問題—可以通過函數f分解—>相同的子問題
子問題—可以通過函數f分解—>相同的子問題
……
而分解主問題的函數，又可以繼續用于以后的子問題，這樣就形成了遞歸。

3.如何理解遞歸

1. 通過遞歸展開的細節圖理解
2. 二叉樹的題目
3. 宏觀看待遞歸過程

• 不要過于在意遞歸的細節展開圖
• 把遞歸的函數當成一個黑盒
• 相信黑盒一定能完成任務

4.如何寫好一個遞歸
1.先找到相同的子問題。
2.只關心某一個子問題如何解決。
3.注意遞歸函數的出口。

搜索

1.深度優先遍歷vs深度優先搜索（dfs： deep first search），寬度優先遍歷vs寬度優先搜索（bfs：breath first search）
遍歷是形式，搜索是目的。
dfs：深度優先搜索

bfs：寬度優先搜索

2.搜索vs暴力搜索
搜索=暴力搜索：遍歷一遍所有的情況。
搜索（暴搜）兩種方式：dfs（遞歸方式），bfs（優選方式）

3.拓展搜索問題
例子：全排列問題解決方式是樹狀圖
例：1,2,3全排列

回溯與剪枝

1.本質
本質就是dfs。