遞迴組合演算法，遞迴演算法必須包括的內容

這就是著名的背包問題。

這是乙個 n-p 問題，當 n 更大時，不可能找到最多的解。

通常的解決方案是基於貪婪演算法。

遞迴演算法由兩部分組成：

1.與自身定義的原始問題相似的較小規模的子問題（僅在資料大小上有所不同），使遞迴過程繼續進行，稱為一般條件。

2.所描述的問題的最簡單情況，即控制遞迴過程結束的條件，稱為基本條件。 （遞迴匯出）。

遞迴的定義：

如果乙個物件部分由自身組成或由自身定義，則稱為遞迴物件，因此遞迴是由函式過程子過程在操作過程中直接或間接呼叫自身引起的重入現象。

遞迴的基本思想：

就是把乙個大問題分成幾個小的子問題來解決，每個小問題可以分成幾個小的子問題。 基本上，所有遞迴問題都可以用遞迴公式表示。

最重要的一點是假設子問題已經解決了，現在基於已經解決的子問題解決了當前問題; 也就是說，必須先解決子問題，然後基於子問題解決當前問題，或者可以理解為遞迴求解具有依賴順序關係的多個問題。

遞迴的優缺點：

優點：邏輯清晰、結構清晰、可讀性好、簡潔、效率高（擴充套件：DFS深度優先搜尋，前、中、後序二叉樹遍歷）。

缺點：函式呼叫成本高，空間複雜度高，有堆疊溢位的風險。

遞迴演算法必須包括終止條件和遞迴部分。

電腦科學中的遞迴演算法是指通過反覆將問題分解為同類子問題來解決問題的方法。

遞迴方法可以用來解決許多電腦科學問題，因此它是電腦科學中的乙個重要概念。 絕大多數程式語言都支援函式的自呼叫，其中函式可以通過呼叫自身來遞迴呼叫。

可以解決的問題資料的定義是遞迴定義的。 比如斐波那契函式。

問題解決方案是根據遞迴演算法實現的。 比如河內問題。

資料的結構是遞迴定義的。 如二叉樹、廣義表等。

1.呼叫自身的函式是遞迴函式。

2.遞迴與普通函式呼叫一樣，是通過堆疊實現的。

3.樹和二叉樹適用於遞迴表示。

4.該演算法分為基本步驟和歸納步驟。

遞迴演算法是將歸納的思想應用到演算法設計中，遞迴演算法充分利用計算機系統的內部功能，自動實現呼叫過程中相關和必要資訊的儲存和回覆。

1）問題的描述涉及規模。

2）當問題的大小發生變化時，解是完全一樣的，原問題的解包括小問題的解。

3）小規模問題可以解決（關機可以用有限的步驟完成） 輸入：n 輸出：n！

輸入：板數 n，列名稱 a、b、c

輸出：移動方案。

輸入：位數 n

輸出：斐波那契數列的第 n 位數字的值。

有n個樓梯，一次只能走一兩個，所以可以計算出下樓的路有多少條。

演算法思路：1N 個數字分為 s1 和 s2

2.分別求解 S1 和 S2 的最大值和最小值。

S1 的最大值為 max1，S1 的最小值為 min1，S2 的最大值為 max2，S2 的最小值為 min23計算 min（min1， min2）， max（max1， max2）。

首先，含義不同：

遞迴是重複呼叫函式本身來實現迴圈。 迭代是函式中實現迴圈的某個片段，迴圈中操作涉及的變數也是儲存結果的變數，當前儲存的結果作為下週期計算的初始值。

在遞迴迴圈中，當滿足終止條件時，它會逐層返回到末尾。 迭代使用計數器來結束迴圈。 當然，在許多情況下，它是一種多迴圈混合物，具體取決於具體需求。

二、結構不同：

遞迴和迭代都基於控制結構：迭代使用重複結構，而遞迴使用選擇結構。 遞迴和迭代都涉及重複：迭代顯式使用重複結構，而遞迴通過重複函式呼叫實現重複。

遞迴和迭代都涉及終止測試：迭代在迴圈條件失敗時終止，遞迴在遇到基本情況時終止，使用計數器控制重複和遞迴的迭代都逐漸到達終點：迭代修改計數器，直到計數器值導致迴圈條件失敗; 遞迴不斷生成初始問題的簡化副本，直到達到基本情況。

遞迴演算法通常用於解決三類問題：

1）資料的定義是遞迴定義的。（斐波那契函式）。

2）根據遞迴演算法實現問題解。

雖然本身沒有明顯的遞迴結構，但這種問題比迭代更容易解決，比如河內問題。

3）資料的結構是遞迴定義的。

例如，二叉樹、廣義表等，由於結構本身固有的遞迴性質，它們的操作可以遞迴地描述。

以上內容參考：百科全書 - 遞迴。

遞迴演算法是一種使用遞迴的計算方法，即在函式定義中使用函式本身的計算方法。 遞迴演算法可用於解決許多計算問題，例如搜尋、排序和遞迴。 遞迴演算法通常由基本情況（即不再使用遞迴的情況）和遞迴情況組成，其中函式呼叫自身來解決較小的問題。