基本算法-02遞推與遞歸 學習筆記

一、理論與概述

宏觀描述：對于一個待求解的問題，當它局限在某邊界、某個小範圍或者某種特殊情形下時，其答案往往時已知的。如果能夠将該解答的應用場景擴大到原問題的狀态空間，并且擴充過程的每個步驟具有相似性，就可以考慮使用遞推和遞歸求解。

• 以已知的“問題邊界”為起點向“原問題”正向推導的擴充方式就是遞推
• 當推導的路線難以确定，這時以“原問題”為起點嘗試尋找把狀态空間縮小到已知的“問題邊界”的路線，再通過該路線反向回溯的周遊方式就是遞歸

使用遞推、遞歸要求“原問題”與“問題邊界”之間的每個變換步驟具有相似性，這樣我們才能夠設計一段程式實作這個步驟，将其重複作用與間隔之中。即：程式在每個步驟上應該面對同種種類的問題，這些問題都是原問題的一個子問題，可能僅在規模或者某些限制上有所差別，并且能夠使用“求解原問題的程式”進行求解。

對于遞歸算法，有以上前提後，我們就可以讓程式在每個變換過程中執行以下三個操作：

1. 縮小問題狀态空間的規模。這意味着程式嘗試尋找在“原問題”和“問題邊界”之間的變換路線，并向正在探索的路線上邁出一步。
2. 嘗試求解規模縮小以後的問題，結果可能是成功或是失敗的。
3. 如果成功，即找到了規模縮小以後的問題的答案，那麼将答案擴充到目前問題，如果失敗，那麼重新回到目前問題，程式可能會繼續尋找目前問題的其他變換路線，直至最終确定目前問題無法求解。

關鍵的兩點：

• “如何嘗試求解規模縮小的問題”：因為規模縮小後的問題是原問題的一個子問題。是以我們可以把它視為一個新的“原問題”有相同的程式進行求解。這就是所謂的“自身調用自身”
• 如果求解子問題失敗，程式需要重新回到目前問題去尋找其他的變換路線，是以把目前問題縮小為子問題時所作的對目前問題狀态産生影響的事應該全部失效，這是所謂的“回溯時還原現場

遞歸的基本單元是由”縮小“、”求解“、”擴充“組成的一種變換步驟。

二、遞推與遞歸的簡單應用

常見的枚舉形式和周遊方式

枚舉形式	狀态空間規模	一般周遊方式
多項式	n^k， k為常數	循環(for)、遞歸
指數	k^n，k為常數	遞歸、位運算
排列	n!	遞歸、C++ next_permutation
組合	Cn(m)	遞歸+剪枝

分治

分形