一. 遞歸

1. 什么是遞歸？

• 定義： 函數自己調用自己的情況
• 關鍵點：
  ?終止條件： 必須明確遞歸出口，避免無限遞歸
  ?子問題拆分： 問題需能分解成結構相同的更小的子問題
• 缺點：
  ?棧溢出風險： 遞歸深度過大時可能引發棧溢出

2. 為什么會用到遞歸？

• 二叉樹的后序遍歷
• 快排
• 歸并

3. 如何理解遞歸？

1. 遞歸展開的細節圖
2. 二叉樹中的題目
3. 宏觀看待遞歸的過程
   ?不要在意遞歸的細節展開圖
   ?把遞歸的函數當成一個黑盒
   ?相信這個黑盒一定能完成任務

4. 如何寫好一個遞歸？

1. 先找到相同的子問題 -> 函數頭的設計
2. 只關心某一個子問題是如何解決的 -> 函數體的部分
3. 注意遞歸函數的出口

手寫筆記：

二.搜索 vs 深度優先遍歷 vs深度優先搜索 vs 寬度優先遍歷 vs 寬度優先搜索 vs 暴搜

1. 深度優先遍歷 vs 深度優先搜索 -> dfs
2. 寬度優先遍歷 vs 寬度優先搜索 -> bfs
   遍歷是形式，目的是搜索

手寫筆記：

3. 回溯與剪枝

回溯：

1. 本質： 就是深搜

• 在找某種情況的時候，發現這個情況行不通，然后返回到上一級的操作

2. 核心思想：

• 路徑： 記錄已做出的選擇
• 選擇列表： 當前可用的選項
• 結束條件： 滿足條件時將路徑加入結果

剪枝：

1. 目標： 減少無效搜索，提前終止不可能到達解的路徑
2. 剪枝策略：

• 可行性剪枝： 當前路徑明顯不滿足約束時終止
• 去重剪枝： 避免生成重復解
• 最優解剪枝： 在求最優解時，若當前路徑已劣于已知最優解，提前終止