遞歸 引入 什麼是遞歸？先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟裡有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟裡有一個老和尚在給小和尚講故事，故事里說……。象這樣，一個對象部分地由它自己組成，或者是按它自己定義，我們稱之為遞歸。 一個函數、過程、概念或數學結構， ...
遞歸
引入
什麼是遞歸？先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟裡有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟裡有一個老和尚在給小和尚講故事，故事里說……。象這樣，一個對象部分地由它自己組成，或者是按它自己定義，我們稱之為遞歸。 一個函數、過程、概念或數學結構，如果在其定義或說明內部又直接或間接地出現有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。在程式設計中，過程或函數直接或者間接調用自己，就被稱為遞歸調用。遞歸的概念
- 遞歸過程是藉助於一個遞歸工作棧來實現的
- 問題向一極推進，這一過程叫做遞推；
- 問題逐一解決，最後回到原問題，這一過程叫做回歸。
- 遞歸的過程正是由遞推和回歸兩個過程組成。
用遞歸方法編寫的問題解決程式具有結構清晰，可讀性強等優點，且遞歸演算法的設計比非遞歸演算法的設計往往要容易一些，所以當問題本身是遞歸定義的，或者問題所涉及到的數據結構是遞歸定義的，或者是問題的解決方法是遞歸形式的時候，往往採用遞歸演算法來解決。
遞歸的應用及實現
遞歸演算法在可計算性理論中占有重要地位，它是演算法設計的有力工具，對於拓展編程思路非常有用。就遞歸演算法而言並不涉及高深數學知識，只不過初學者要建立起遞歸概念不十分容易。
我們先從一個最簡單的例子導入。
求斐波那契數列的第n位（C++代碼）：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int fibonacci(int n) { 5 if (n <= 1) { 6 return n; 7 } else { 8 return fibonacci(n-1) + fibonacci(n-2); 9 } 10 } 11 12 int main() { 13 int n ; 14 cin >> n ; 15 printf("斐波那契數列前 %d 項為：\n", n); 16 for (int i = 1; i <= n; i++) { 17 printf("%d ", fibonacci(i)); 18 } 19 printf("\n"); 20 return 0; 21 }
回溯法
回溯法的概念與模板
回溯法是一種常用的演算法，它主要用於解決一些組合優化問題，例如八皇後問題、0/1背包問題等。回溯法的基本思想是：從問題的某一種狀態開始，搜索所有可能的情況，直到找到符合要求的解為止。回溯法的實現過程通常採用遞歸的方式，每次遞歸都會嘗試一種可能的情況，如果這種情況不符合要求，就回溯到上一層遞歸，嘗試其它的情況。在回溯的過程中，需要記錄已經嘗試過的情況，以避免重覆計算。
回溯法的時間複雜度通常比較高，因為它需要搜索所有可能的情況。但是，在一些特殊的情況下，回溯法可以通過剪枝等優化技巧來提高效率。
回溯法是一種常用的演算法思想，可以用於解決很多問題，比如八皇後問題、0/1背包問題等。下麵是一個用C語言實現回溯法的模板：1 #include <bits/stdc++.h> 2 3 #define MAX_N 100 // 最大的問題規模 4 5 int n; // 問題規模 6 int a[MAX_N]; // 存儲解的數組 7 8 // 檢查當前解是否合法 9 int check(int cur) { 10 // TODO: 根據具體問題實現 11 } 12 13 // 回溯函數 14 void backtrack(int cur) { 15 if (cur == n) { // 找到一個解 16 // TODO: 處理解的代碼 17 return; 18 } 19 for (int i = 0; i < n; i++) { // 枚舉當前位置的所有可能取值 20 a[cur] = i; // 嘗試將當前位置設為i 21 if (check(cur)) { // 如果當前解合法 22 backtrack(cur + 1); // 繼續搜索下一個位置 23 } 24 } 25 } 26 27 int main() { 28 // TODO: 讀入問題規模n和其它必要的輸入 29 backtrack(0); // 從第0個位置開始搜索 30 return 0; 31 }
在實際使用中，需要根據具體問題實現check函數和處理解的代碼。
八皇後問題
下麵是一個八皇後問題的回溯法實現：
1 #include <iostream> 2 using namespace std; 3 4 const int N = 8; 5 int queen[N]; // 存放每一行皇後所在的列號 6 7 bool check(int row, int col) // 判斷當前位置是否可以放置皇後 8 { 9 for (int i = 0; i < row; i++) 10 { 11 if (queen[i] == col || abs(row - i) == abs(col - queen[i])) 12 return false; 13 } 14 return true; 15 } 16 17 void backtrack(int row) // 回溯函數 18 { 19 if (row == N) // 找到一組解 20 { 21 for (int i = 0; i < N; i++) 22 cout << queen[i] << " "; 23 cout << endl; 24 return; 25 } 26 27 for (int col = 0; col < N; col++) // 枚舉當前行所有可能的列 28 { 29 if (check(row, col)) // 如果當前位置可以放置皇後 30 { 31 queen[row] = col; // 記錄當前皇後所在的列號 32 backtrack(row + 1); // 繼續搜索下一行 33 } 34 } 35 } 36 37 int main() 38 { 39 backtrack(0); 40 return 0; 41 }
在上面的代碼中，check函數用於判斷當前位置是否可以放置皇後，backtrack函數用於搜索所有可能的情況。在搜索過程中，queen數組用於記錄每一行皇後所在的列號。
回溯法是一種非常實用的演算法，它可以解決很多組合優化問題。但是，由於回溯法的時間複雜度較高，因此在實際應用中需要註意優化。
碼字不易，點個贊唄§(*￣▽￣*)§
