# 遞迴 (Recursion)
(這個筆記大致取材於AP325第一章，但包含了一些關於遞迴更基礎與更詳盡的解說)
「遞迴是大事化小，要記得小事化無。」
「暴力或許可以解決一切，但是可能必須等到地球毀滅。」
「遞迴搜尋如同末日世界，心中有樹而程式(城市)中無樹。」
本章介紹遞迴函數的基本方法與運用，也介紹使用窮舉暴搜的方法。
---
## 基本觀念與用法
遞迴在數學上是函數直接或間接以自己定義自己，在程式上則是函數直接或間接呼叫自己。遞迴是一個非常重要的程式結構，在演算法上扮演重要的角色，許多的算法策略都是以遞迴為基礎出發的，例如分治與動態規劃。
### 遞迴是什麼
程式由指令組成，而其流程結構，也就是指令執行順序可以分成4種：
1. 循序，一一往下
2. 條件分支，if, else, switch
3. 迴圈，for, while, do-while
4. 副程式(函數)呼叫，庫存函式或自訂函式
在副程式(函數)呼叫時，執行指令位置從呼叫點轉移至被呼叫函數的開始位置，直到執行到return指令或是函式結束時，轉移回到被呼叫的點。
當一個函數直接或間接呼叫自己時，這就是一個遞迴函數。所謂直接就是某函數foo內有呼叫自己的指令，例如
```cpp=
void foo() {
foo();
cout << "hello, foo\n";
return;
}
```
這樣寫語法上是可以的，但是有個問題，它會無窮遞迴下去，所以合理的遞迴必然包含遞迴的終止條件，基本常見的寫法是在遞迴函數一開始的地方寫終止條件。例如：
```cpp=
void foo(int n) {
if (n<0) return; // terminal case
foo(n-1);
cout << "hello, foo\n";
return;
}
```
如果我們以呼叫foo(3)開始，每一次遞迴呼叫時，參數會減1，到小於0時就不再往下遞迴。它的遞迴呼叫過程是
$foo(3)\rightarrow foo(2)\rightarrow foo(1)\rightarrow foo(0)\rightarrow foo(-1)$
遞迴也可能間接呼叫自己，例如
```cpp=
void foo(int n) {
if (n<0) return; // terminal case
bar(n);
cout << "foo\n";
return;
}
void bar(int n) {
foo(n-1);
cout << "bar\n";
}
```
函數在遞迴呼叫時，會將當時的區域變數儲存起來，產生一組新的區域變數，當返回時，再回存當時的區域變數內容。所以每一次的遞迴呼叫會擁有自己的區域變數，可以看成同函數的不同分身。
請看下面這個例子。
```cpp=
#include<bits/stdc++.h>
using namespace std;
void f(int n) {
cout << n <<'\n';
// n=0 is the terminal case
for (int i=0; i<n; i++) f(i);
}
int main() {
f(3);
return 0;
}
```
執行結果
```
3
0
1
0
2
0
1
0
```
遞迴的過程，可以用下圖表示
### 以遞迴定義函數
學習遞迴是一件重要的事，不過遞迴的思考方式與一般的不同，它不是直接的給予答案，而是間接的說明答案與答案的關係，不少程式的學習者對遞迴感到困難。以簡單的階乘為例，如果採直接的定義：
對正整數$n$，$fac(n)$定義為所有不大於$n$的正整數的乘積，也就是
$fac(n) = 1 \times 2 \times 3 \times \ldots \times n$。
如果採遞迴的定義，則是：
$fac(1) = 1$; and
$fac(n) = n \times fac(n-1)$ for $n>1$。
若以$n=3$為例，直接的定義告訴你如何計算$fac(3)$，而遞迴的定義並不直接告訴你$fac(3)$是多少，而是
$fac(3) = 3 \times fac(2)$，而
$fac(2) = 2 \times fac(1)$，最後才知道
$fac(1) = 1$。
所以要得到$fac(3)$的值，我們再逐步迭代回去，
$fac(2) = 2 \times fac(1) = 2 \times 1 = 2$，
$fac(3) = 3 \times fac(2) = 3 \times 2 = 6$。
現在大多數的程式語言都支援遞迴函數的寫法，而函數呼叫與轉移的過程，正如上面逐步推導的過程一樣，雖然過程有點複雜，但不是寫程式的人的事，以程式來撰寫遞迴函數幾乎就跟定義一模一樣。上面的階乘函數以程式來實作可以寫成：
```cpp=
int fac(int n) {
if (n == 1) return 1;
return n * fac(n-1);
}
```
再舉一個很有名的費式數列(Fibonacci)來作為例子。費式數列的定義：
$F(1) = F(2) = 1$;
$F(n) = F(n-1) + F(n-2)$ for $n>2$.
以程式來實作可以寫成：
```cpp=
int f(int n) {
if (n <= 2) return 1;
return f(n-1) + f(n-2);
}
```
遞迴函數一定會有終端條件(也稱邊界條件)，例如上面費式數列的
$F(1) = F(2) = 1$以及階乘的$fac(1) = 1$，通常的寫法都是先寫終端條件。遞迴程式與其數學定義非常相似，通常只要把數學符號換成適當的指令就可以了。上面的兩個例子中，程式裡面就只有一個簡單的計算，有時候也會帶有迴圈，例如Catalan number的遞迴式定義：
$C_0=1$ and
$C_n = \sum_{i=0}^{n-1} C_i×C_{n-1-i}$ for $n\ge 1$。
程式如下：
```cpp=
int cat(int n) {
if (n == 0) return 1;
int sum = 0;
for (int i=0; i<n; i++)
sum += cat(i)*cat(n-1-i);
return sum;
}
```
### 以遞迴的思維解決問題
以遞迴的思維來解決問題時，其想法就是：「遞迴是大事化小，要記得小事化無。」
對於一個問題$P$，輸入為$I$，我們可以看成要計算的答案是一個函數值$P(I)$。舉例來說$P$是找最大值，$I=(5,1,8,4,3)$是一個整數序列放在陣列中。我們要構思的事情有二：
1. 遞迴關係：對於比較小的輸入資料$I'$，如果已知其解$P(I')$，如何建構出所要的$P(I)$。很常見的情形是$I'$只比$I$少一個元素。
2. 終端條件：當$I$很小時，其答案為何，通常通端條件是只有一個元素。
以最大值的例子來說，我們要找出$\max(5,1,8,4,3)$。
1. 遞迴關係：如果已知$x = \max(5,1,8,4)$，如何建構出$\max(5,1,8,4,3)$？答案是$\max(x,3)$。更一般化的情形，若資料放在陣列$A$中，要找前$i$個的最大值 $P(i)$，若已知$P(i-1)=x$，則$P(i)=\max(x,A[i])$。
2. 終端條件：當只有一個元素$i=0$時，$P(0)=A[0]$。
寫成C\++的程式則是：
```cpp
int p(int A[],i) {
if (i==0) return A[0]; // terminal case
return max(p(A,i-1), A[i]);
}
```
再舉一個簡單的例子，要把陣列中的偶數加起來。
遞迴的想法：先把前面的偶數加起來，如果我是偶數就把自己將上去。
```cpp
int p(int A[],i) {
if (i==0) {// terminal case
if (A[0]%2==0) return A[0];
else return 0;
}
if (A[i]%2==0)
return p(A,i-1)+A[i];
else return p(A,i-1);
}
```
也可以這麼寫：
```cpp
int p(int A[],i) {
if (i<0) return 0;
return p(A,i-1) + ((A[i]%2==0)?A[i]:0);
}
```
**遞迴的代價**：上面兩個例子只是為了說明遞迴的思考方式，這兩個問題還是用一般的迴圈寫法比較好。
雖然遞迴的寫法通常很簡潔，上面的例子的時間複雜度也很好，但是遞迴還是有代價的。遞迴程式在執行時，要靠系統幫忙，需要準備系統堆疊來存放當時的狀況(變數內容，指令位置)，所以遞迴是需要消耗記憶體以及時間的。如果遞迴的深度太大，通常就不適合用遞迴的方式來寫。
再看一個有名的例子，河內之塔。
有三根杆子A，B，C。A杆上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 杆：
1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。盤子也不能放在柱子以外的地方。
遞迴思考：如果會搬N-1個的話，如何搬N個？
1. 先將N-1個由A搬至B
2. 把剩下的一個由A搬至C
3. 把在B的N-1個搬至C
```cpp=
#include <stdio.h>
void hanoi(int n,char from, char to, char tem) {
if (n==1) {
printf("Move %d from %c to %c;\n", n,from,to);
} else {
hanoi(n-1,from,tem,to);
printf("Move %d from %c to %c;\n",n,from,to);
hanoi(n-1,tem,to,from);
}
}
int main() {
int n;
scanf("%d", &n);
hanoi(n,'A','C','B');
}
```
執行結果
```
3
Move 1 from A to C;
Move 2 from A to B;
Move 1 from C to B;
Move 3 from A to C;
Move 1 from B to A;
Move 2 from B to C;
Move 1 from A to C;
```
回顧一下這個解法為何是對的。最大的第N個並沒有放在其他較小的圓盤上，當我們搬前$N-1$個時，最大的在下方，所以只要此$N-1$個的搬動是合法的，根據數學歸納法，全部的搬動就是合法的，沒有大壓小。
再想想遞迴的思路：大事化小，小事化無。要搬$N$個，只要會先搬$N-1$個，而如果只搬一個，很簡單。
為何遞迴的思考方式可行？當我們把$N$個的問題化為$N-1$個時，問題沒有改變，只是要處理的東西變小了，這個很重要，因為如此才能用遞迴呼叫同一個程式來完成。
### 遞迴暴搜
以**樹狀結構**展開所有的可能，其實並不是艱難的觀念。
小美有紅綠黑3件衣服，黃紅綠3件褲子以及紅綠2雙鞋子。若紅綠不能相配，則有哪幾種穿搭方式。
這在資訊科學中稱為樹狀結構，對於有連線的上層與下層，上層的節點稱為parent，下層的稱為child。
樹狀展開圖中每一層根據一個決定將目前所有的可能分成若干類，每個節點(圖中的小圓點)承繼他所有祖先的決定，例如(紅衣、紅褲)以及(綠衣、黃褲、綠鞋)。最下層的稱為leaf，每個leaf各是一種最後的結果。
**以DFS生成所有子集合**
一個$n$個元素的集合有$2^n$個子集合，很多組合問題需要將這些子集合全部枚舉出來找答案，這個方法稱為暴搜(Brute Force)。問題是如何有系統的枚舉所有的子集合，遞迴是一個好方法，我們先看如何以上面的樹狀圖產生所有子集合。
假設$A$陣列中有$n$個整數，我們要產生其所有組合，這裡不管元素內容相不相同，以不同index做為不同的組合。以下是以樹狀圖來產生三個元素集合的所有子集合。
用此觀念遞迴生成所有子集合時，我們並不需在程式中建構這棵樹，也就是「遞迴搜尋如同末日世界，心中有樹而程式(城市)中無樹。」
每一個節點是一個遞迴呼叫，負責產生其下的所有子集合，我們看看它需要什麼資料。他其實只需要兩項資料就可以
1. 繼承自他的所有祖先的決策，也就是目前已經選取的元素
2. 他在第幾層，也就是他負責哪一個元素選取或不選取
我們看下面這個範例程式，它產生所有的子集合然後簡單地把它印出來。這裡先示範用vector來存放的寫法，重點在副程式subset。傳入參數curr是目前已經選取的子集合內容，a是原集合的內容，idx則是目前要選擇第幾個(也就是第幾層)。
進入函數先處理終端條件，如果是終端條件，把子集合印出結束了。在不是終端條件的狀況，這次遞迴呼叫(這個節點)要負責產生兩個節點：一個是不選取a[idx]，一個是選取a[idx]，寫在第20 ~ 22行。
```cpp=
#include <bits/stdc++.h>
using namespace std;
void print(vector<int> &v) {
if (v.size()==0) {
printf("empty\n");
return;
}
for (int i=0; i<v.size(); i++) {
printf("%d%c", v[i]," \n"[i==v.size()-1]);
}
return;
}
// note that cuu is passed by value, involving copying
void subset(vector<int> curr, vector<int> &a, int idx) {
if (idx == a.size()) { // terminal
printf("subset = ");
print(curr);
return;
}
subset(curr,a,idx+1); // not choosing a[idx]
curr.push_back(a[idx]);
subset(curr,a,idx+1); // choosing a[idx]
// pass by value will not change its parent's curr
return;
}
int main() {
int n;
vector<int> curr, inp({4,1,5,8});
subset(curr,inp,0);
return 0;
}
```
我們觀察一下這些遞迴的過程，它是沿著這棵樹做一個所謂的深度優先搜尋(Depth First Search, DFS)，也就是先往左下走，走到沒路時會回到上一層的parent，再往右孩子走，如下圖。
這裡需要注意一件事，一個節點修改curr時，不能去改到parent的curr內容，因為在它結束時，可能會回到他的parent再繼續做。
如果使用pass by reference就會導致錯誤的結果。
避免修改傳入參數的方法有多種方式，這裡用的是pass by value，也就是會參數複製一份再傳入呼叫的函數，當然複製會需要時間，那麼可以有其他處理方式來避免複製嗎？
答案是肯定的。我們的目標是遞迴程序在結束回到其parent時不要修改到傳進來的curr，那麼可以在返回前將所做的修改復原即可。以下是範例程式，我們只揭示副程式的部分。
請注意到參數傳入是以pass by reference (有加&)的方式，所以並沒有複製的動作，在第10行多加了一行復原的動作。
```cpp=
void subset(vector<int> &curr, vector<int> &a, int idx) {
if (idx == a.size()) { // terminal
printf("subset = ");
print(curr);
return;
}
subset(curr,a,idx+1); // not choosing a[idx]
curr.push_back(a[idx]);
subset(curr,a,idx+1); // choosing a[idx]
curr.pop_back(); // recover modification
return;
}
```
這種程式的行為也可以看成是一個「找路」的過程，在每一個岔路口一一嘗試所有可能的下一步，嘗試完畢後，恢復所做的修改，退回到前一步，所以也稱為回溯法(Backtracking)。
可能有些讀者還不太熟悉vector，以下是用陣列的方式來做的範例程式，這個範例中，我們也偷懶將初始陣列放在global variable。
以陣列儲存時，我們需要自己記錄目前元素的個數，所以curr需要一個n_curr來記錄目前的陣列長度。雖然傳遞陣列位置會修改到parent的內容，但是第24行變更curr的內容並不會影響parent，因為這裡只是在curr後方加入元素，而parent自己的n_curr並不會被改到。
```cpp=
// enumerate subsets, using array
#include <bits/stdc++.h>
using namespace std;
int arr[10]={4,1,5,8},n=4;
void print(int v[],int k) {
if (k==0) {
printf("empty\n");
return;
}
for (int i=0; i<k; i++) {
printf("%d%c", v[i]," \n"[i==k-1]);
}
return;
}
// arr and n=len(arr) are global var
void subset(int curr[], int n_curr, int idx) {
if (idx == n) { // terminal
printf("subset = ");
print(curr,n_curr); // subset and its length
return;
}
subset(curr,n_curr,idx+1); // not choosing arr[idx]
curr[n_curr] = arr[idx];
subset(curr,n_curr+1,idx+1); // choosing arr[idx]
// array curr is changed, but parent's n_curr keeps result valid
return;
}
int main() {
int tem[10]; // enough space for subsets
subset(tem,0,0);
return 0;
}
```
下面這個AP325的習題是一個簡單的變化。
##### Q-1-8. 子集合的和 (APCS201810, subtask)
輸入$n$個正整數，請計算各種組合中，其和最接近$P$但不超過$P$的和是多少。每個元素可以選取或不選取但不可重複選，輸入的數字可能重複。$P\le$ 1e9+9，$0 < n < 26$。
Time limit: 1秒
輸入格式：第一行是$n$與$P$，第二行是$n$個可挑選的正整數，大小不會超過$P$，同行數字以空白間隔。
輸出格式：最接近$P$但不超過$P$的和。
範例輸入：
5 17
5 5 8 3 10
範例輸出：
16
---
我們是要枚舉所有子集合的總和，當然我們可以用上面的程式產生所有的子集合，然後再將原來印出子集合的內容改成計算總和。我們可以更簡單的處理此事，因為我們並不需要子集合內容，只需要他的和，所以我們繼承自parent的資訊可以簡單的用「目前已經選取元素的總和」來表示。
下面的範例程式中，遞迴函數dfs的傳入參數只有兩個整數，他的架構與前一支類似但更加簡單。
```cpp=
// subset sum closest to P, using recursion
#include<bits/stdc++.h>
using namespace std;
int n, ans=0; // current best result
int P, A[26]; // input data
// discard or choose the i-th element
void dfs(int curr_sum, int idx) {
if (idx >= n) { // terminal condition
if (curr_sum <= P)
ans = max(ans, curr_sum);
return;
}
dfs(curr_sum, idx+1); // discard A[i]
dfs(curr_sum+A[idx], idx+1); // choose A[i]
return;
}
int main() {
scanf("%d%d", &n, &P);
for (int i=0;i<n;i++) scanf("%d", &A[i]);
ans=0;
dfs(0,0);
printf("%d\n", ans);
return 0;
}
```
由於這一題的輸入資料只有非負整數，所以在計算過程中，如果目前總和以及超過$P$，這個節點所產生的子集合都將不合乎要求，我們可以提前結束不再往下搜下它所產生的解，這個手法稱為「剪枝」。剪枝可能帶來效率的提升，有些是可以保證worst case time complexity的改善，有些並未有和保證，這裡的剪枝很簡單，但有些問題可能有複雜的剪枝。
以下是修改後的程式，我們只揭示副程式的部分，其他並無不同。修改的內容也很簡單，一開始的地方多加一行檢查，第4行比較答案的地方就不必再檢查是否<=P了。
```cpp=
void dfs(int curr_sum, int idx) {
if (curr_sum > P) return; // simple cut
if (idx >= n) { // terminal condition
if (curr_sum > ans) ans = curr_sum;
return;
}
dfs(curr_sum, idx+1); // discard A[i]
dfs(curr_sum+A[idx], idx+1); // choose A[i]
return;
}
```
接著我們看一個帶有限制性的子集合問題。
---
##### 例題：不相交字串的組合數
有10個科目，$n$個學生，每個學生修過其中若干個科目。現在想要選取若干學生組成一個團隊，團隊至少需要包含一人，且團隊中任兩人均無共同修過的科目，請計算出有多少種選取的方式。每一個科目以前10個大寫英文字母ABCDEFGHIJ的一個字母表示，一個學生修過的科目以一個字串表示，每個學生至少修過一科(字串非空)。下面是一個5個學生的例子
1. CABHIJ
2. GDEF
3. CAI
4. FBA
5. EFGD
我們可以發現{1,2}是一個組合，兩人沒有交集，但{1,3}不是，{1,4}也不是。全部合於條件的組合為：{1},{2},{3},{4},{5},{1,2},{1,5},{2,3},{3,5}，一共有9個。請注意{1,2}與{2,1}算相同的組合，不重複計算。
Time limit: 1秒
輸入格式：輸入第一行是一個正整數n，$n \leq 30$，以下$n$行，每行是一個字串表示一個學生修過的科目，每個字串的字元皆屬前10個大寫英文字母，且同一個字串中沒有重複字母。
輸出：輸出組合的個數。
範例輸入：
5
CABHIJ
GDEF
CAI
FBA
EFGD
範例輸出：
9
---
最多只有30個學生，如果要窮舉$2^{30}$，執行時間是不夠的，不過因為科目只有10個，合於規定不重複得組合並沒有那麼多，最壞的狀況是每個學生都只修一科，每一科恰有3個學生修，此時組合數最多為 $(3+1)^{10} = 2^{20}$，窮舉的時間還是夠的。如果參數的範圍更大，這題有DP的解法。
遞迴枚舉有限制的子集合，與前面枚舉子集合的架構相同，第i層決定挑選第i個是否挑選。在每一次遞迴，我們需要決定目前的學生可不可以挑，不能單純的到最後才來判定是否有交集，否則檢查的個數就會到達$2^{30}$。因此，我們必須使用一個方式來決定第i個與目前以挑選的是否有交集。
這有多種方式來做，最方便的方式是bitmask，這是用一個整數來表示一個子集合，第i個bit是1表示第i個元素在；反之表示不在。例如0010110011，表示$\{ 0,1,4,5,7\}$。
利用位元運算可以很容易的做交集與聯集。請看下面的範例程式。
副程式dfs的傳入參數curr是目前已經選取學生所修科目的聯集，本題不需要紀錄學生編號或學生數，idx則是目前要決定哪一位學生。副程式回傳可於規定的組合數。一開始的第7行是終端情形，如果全部的學生都已決定，則回傳1，因為我們過程中不會產生不合法(有交集)的組合。
若非終端情形，先遞迴呼叫計算不含student[idx]的組合，此時不會有交集；再來，使用位元的&運算來檢查student[idx]是否與curr有交集，若無，則遞迴計算加入該學生的組合數，此時用位元的|運算做聯集(用加法也可以)。
主程式部分是將每一個學生所修科目轉換為一個整數表示，我們以'A"為0，所以字元ch對應的整數編號即為ch-'A'，對應的位元則是將1左移這麼多位，也就是
1 << (ch - 'A')
初始的遞迴從dfs(0,0)計算所有無交集的子集合數量，最後減去1則是扣除空集合。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n, student[50];
// curr is bitmask for current char
int dfs(int curr, int idx) { // return num of valid subsets
if (idx >= n) return 1;
int q = dfs(curr, idx+1); // not choosing
if ((student[idx] & curr) == 0) // if disjoint
q += dfs(curr|student[idx], idx+1);
return q;
}
int main() {
int i,j;
string s;
cin >> n;
for (i=0; i<n;i++) {
cin >> s;
int b = 0; // bitmask for a student
for (char ch: s) {
b |= (1 << (ch-'A'));
}
student[i] = b;
}
int ans = dfs(0,0)-1; // -1 is for empty set
cout << ans << '\n';
return 0;
}
```
接下來看一個遞迴的經典名題，八后問題。它是一個窮舉排列的例子。
西洋棋的棋盤是一個$8\times 8$的方格，其中皇后的攻擊方式是皇后所在位置的八方位不限距離，也就是只要是在同行、同列或同對角線(包含45度與135度兩條對斜線)，都可以攻擊。八皇后問題是問說：在西洋棋盤上有多少種擺放方式可以擺上8個皇后使得彼此之間都不會被攻擊到。這個問題可以延伸到不一定限於是$8\times 8$的棋盤，而是$N\times N$的棋盤上擺放$N$個皇后。八皇后問題有兩個版本，這裡假設不可以旋轉棋盤。
---
##### P-1-9. N-Queen解的個數
計算N-Queen有幾組不同的解，對所有$0 < N < 12$。
(本題無須測資)
---
要擺上N個皇后，那麼顯然每一列恰有一個皇后，不可以多也不可以少。所以每一組解需要表示每一列的皇后放置在哪一行，也就是說，我們可以以一個陣列p[N]來表示一組解。因為兩個皇后不可能在同一行，所以p[N]必然是一個0 ~ N-1的排列。我們可以嘗試所有可能的排列，對每一個排列來檢查是否有任兩個皇后在同一斜線上(同行同列不需要檢查了)。先看非遞迴檢查所有排列的寫法。
要產生所有排列通常是以字典順序(lexicographic order)的方式依序產生下一個排列，這裡我們不講這個方法，而介紹使用庫存函數 next_permutation()，它的作用是找到目前排列在字典順序的下一個排列，用法是傳入目前排列所在的陣列位置$[s,t)$，留意C\++庫存函數中區間的表示方式幾乎都是左閉右開區間。回傳值是一個bool，當找不到下一個的時候回傳false，否則回傳true。下面是迴圈窮舉的範例程式，其中檢查是否在同一條對角線可以很簡單的檢查 「abs(p[i]-p[j]) == j-i」。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int nq(int n) {
int p[14], total=0;
for (int i=0;i<n;i++) p[i]=i; //first permutation
do {
// check valid
bool valid=true;
for (int i=0; i<n; i++) for (int j=i+1;j<n;j++)
if (abs(p[i]-p[j])==j-i) { // one the same diagonal
valid=false;
break;
}
if (valid) total++;
} while (next_permutation(p, p+n)); // until no-next
return total;
}
int main() {
for (int i=1;i<12;i++)
printf("%d ",nq(i));
return 0;
}
```
接著看遞迴的寫法，每呼叫一次遞迴，我們檢查這一列的每個位置是否可以放置皇后而不被之前所放置的皇后攻擊。對於每一個可以放的位置，我們就嘗試放下並往下一層遞迴呼叫，如果最後放到第n列就表示全部n列都放置成功。
```cpp=
// number of n-queens, recursion
#include<bits/stdc++.h>
using namespace std;
// k is current row, p[] are column indexes of previous rows
int nqr(int n, int k, int p[]) {
if (k>=n) return 1; // no more rows, successful
int total=0;
for (int i=0;i<n;i++) { // try each column
// check valid
bool valid=true;
for (int j=0;j<k;j++)
if (p[j]==i || abs(i-p[j])==k-j) {
valid=false;
break;
}
if (!valid) continue;
p[k]=i;
total+=nqr(n,k+1,p);
}
return total;
}
int main() {
int p[15];
for (int i=1;i<12;i++)
printf("%d ",nqr(i,0,p));
return 0;
}
```
副程式中我們對每一個可能的位置 i 都以一個 j-迴圈檢查該位置是否被 $(j,p[j])$ 攻擊，這似乎有點缺乏效率。我們可以對每一個 $(j,p[j])$ 標記它在此列可以攻擊的位置，這樣就更有效率了。以下是這樣修改後的程式碼，這個程式大約比前一個快了一倍，比迴圈窮舉的方法則快了百倍。以迴圈窮舉的方法複雜度是$O(n^2\times n!)$，而遞迴的方法不會超過$O(n\times n!)$，而且實際上比$O(n\times n!)$快很多，因為你可以看得到，在遞迴過程中，被已放置皇后攻擊的位置都被略去了，所以實際上並未嘗試所有排列。這種情況下我們知道他的複雜度上限，但真正準確的複雜度往往難以分析，如果以實際程式來量測，$n=11$時，$n!=39,916,800$，但遞迴被呼叫的次數只有$16,6926$次，差了非常多。
```cpp=
// number of n-queens, recursion, better
#include<bits/stdc++.h>
using namespace std;
// k is current row, p[] are column indexes of previous rows
int nqr(int n, int k, int p[]) {
if (k>=n) return 1; // no more rows, successful
int total=0;
bool valid[n];
for (int i=0;i<n;i++) valid[i]=true;
// mark positions attacked by (j,p[j])
for (int j=0; j<k; j++) {
valid[p[j]]=false;
int i=k-j+p[j];
if (i<n) valid[i]=false;
i=p[j]-(k-j);
if (i>=0) valid[i]=false;
}
for (int i=0;i<n;i++) { // try each column
if (valid[i]) {
p[k]=i;
total+=nqr(n,k+1,p);
}
}
return total;
}
int main() {
int p[15];
for (int i=1;i<12;i++)
printf("%d ",nqr(i,0,p));
return 0;
}
```
## 其他範例
遞迴程式雖然好寫，但往往有效率不佳的問題，通常遞迴函數裡面只呼叫一次自己的效率比較不會有問題，但如果像Fibonacci與Catalan number，一個呼叫兩個或是更多個，其複雜度通常都是指數成長，演算法裡面有些策略是來改善純遞迴的效率，例如動態規劃，這在以後的章節中再說明。
遞迴通常使用的時機有兩類：
* 根據定義來實作。
* 為了計算答案，以遞迴來進行窮舉暴搜。
以下我們分別來舉一些例題與習題。
### 實作遞迴定義
---
##### P-1-1. 合成函數(1)
令$f(x)=2x-1$以及$g(x,y)=x+2y-3$。本題要計算一個合成函數的值，例如
$f(g(f(1),3))=f(g(1,3))=f(4)=7$。
Time limit: 1秒
輸入格式：輸入一行，長度不超過1000，它是一個$f$與$g$的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過1000。
輸出：輸出函數值。最後答案與運算過程不會超過正負10億的區間。
範例輸入：
f g f 1 3
範例輸出：
7
---
題解：合成函數的意思是它的傳入參數可能是個數字也可能是另外一個函數值。以遞迴的觀念來思考，我們可以將一個合成函數的表示式定義為一個函式eval()，這個函式從輸入讀取字串，回傳函數值。其流程只有兩個主要步驟，第一步是讀取一個字串，根據題目定義，這個字串只有3種情形：f, g 或是一個數字。第二步是根據這個字串分別去進行 f 或 g 函數值的計算或是直接回傳字串代表的數字。至於如何計算 f 與 g 的函數值呢？如果是 f，因為它有一個傳入參數，這個參數也是個合成函數，所以我們遞迴呼叫 eval()來取得此參數值，再根據定義計算。如果是g，就要呼叫eval()兩次取得兩個參數。 以下是演算法流程：
```
int eval() // 一個遞迴函式，回傳表示式的值
讀入一個空白間隔的字串token;
if token是f then
x = eval();
return 2*x - 1;
else if token是g then
x = eval();
y = eval();
return x + 2*y - 3;
else // token是一個數字字串
return token代表的數字
end of eval()
```
程式實作時，每次我們用字串的輸入來取得下一個字串，而字串可能需要轉成數字，這可以用庫存函數atoi()來做。
```cpp=
// p 1.1a
#include <bits/stdc++.h>
int eval(){
int val, x, y, z;
char token[7];
scanf("%s", token);
if (token[0] == 'f') {
x = eval();
return 2*x - 1;
} else if (token[0] == 'g') {
x = eval();
y = eval();
return x + 2*y -3;
} else {
return atoi(token);
}
}
int main() {
printf("%d\n", eval());
return 0;
}
```
atoi()是一個常用的函數，可以把字串轉成對應的整數，名字的由來是ascii-to-int。當然也有其它的方式來轉換，這一題甚至可以只用scanf()就可以，這要利用scanf()的回傳值。我們可以將eval()改寫如下，請看程式中的註解。
```cpp=
// p_1_1b
int eval(){
int val, x, y, z;
char c;
// first try to read an int, if successful, return the int
if (scanf("%d",&val) == 1) {
return val;
}
// otherwise, it is a function name: f or g
scanf("%c", &c);
if (c == 'f') {
x = eval(); // f has one variable
return 2*x-1;
} else if (c == 'g') {
x = eval(); // g has two variables
y = eval();
return x + 2*y -3;
}
}
```
下面是個類似的習題。
---
##### Q-1-2. 合成函數(2) (APCS201902)
令$f(x)=2x–3$；$g(x,y)=2x+y–7$；$h(x,y,z)=3x–2y+z$。本題要計算一個合成函數的值，例如 $h(f(5),g(3,4),3)=h(7,3,3)=18$。
Time limit: 1秒
輸入格式：輸入一行，長度不超過1000，它是一個f, g, 與h的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過1000。
輸出：輸出函數值。最後答案與運算過程不會超過正負10億的區間。
範例輸入：
h f 5 g 3 4 3
範例輸出：
18
---
每個例題與習題都若干筆測資在檔案內，請自行練習。再看下一個例題。
---
##### P-1-3. 棍子中點切割
有一台切割棍子的機器，每次將一段棍子會送入此台機器時，機器會偵測棍子上標示的可切割點，然後計算出最接近中點的切割點，並於此切割點將棍子切割成兩段，切割後的每一段棍子都會被繼續送入機器進行切割，直到每一段棍子都沒有切割點為止。請注意，如果最接近中點的切割點有二，則會選擇座標較小的切割點。每一段棍子的切割成本是該段棍子的長度，輸入一根長度$L$的棍子上面$N$個切割點位置的座標，請計算出切割總成本。
Time limit: 1秒
輸入格式：第一行有兩個正整數$N$與$L$。第二行有$N$個正整數，依序代表由小到大的切割點座標$p[1]$ ~ $p[N]$，數字間以空白隔開，座標的標示的方式是以棍子左端為0，而右端為$L$。$N \le 5e4$，$L< 1e9$。
輸出：切割總成本點。
範例輸入：
4 10
1 2 4 6
範例輸出：
22
範例說明：第一次會切割在座標 4 的位置，切成兩段 [0, 4], [4, 10]，成本10；
[0, 4] 切成 [0, 2] 與 [2, 4]，成本 4；
[4, 10] 切成 [4, 6] 與 [6, 10]，成本 6；
[0, 2] 切成 [0, 1] 與 [1, 2]；成本 2；
總成本 10+4+6+2 = 22
---
P-1-3題解：棍子切斷後，要針對切開的兩段重複做切割的動作，所以是遞迴的題型。因為切點的座標值並不會改變，我們可以將座標的陣列放在全域變數中，遞迴函數需要傳入的是本次切割的左右端點。因為總成本可能大過一個 int 可以存的範圍，我們以long long型態來宣告變數，函數的架構很簡單：
```
// 座標存於 p[]
// 遞迴函式，回傳此段的總成本
long long cut(int left, int right) {
找出離中點最近的切割點 m;
return p[right]-p[left] + cut(left,m) + cut(m,right);
}
```
至於如何找到某一段的中點呢？離兩端等距的點座標應該是
x = (p[right] + p[left])/2
所以我們要找某個 m，滿足 p[m-1] < x <= p[m]，然後要找的切割點就是m-1或m，看這兩點哪一點離中點較近，如相等就取m-1。這一題因為數值的範圍所限，採取最簡單的線性搜尋即可，但二分搜是更快的方法，因為座標是遞增的。以下看實作，先看以線性搜尋的範例程式。
這裡有些細節要留意，當中點的位置非整數時，k因為捨位誤差比真正的中點位置小0.5，若p[m]==k，它可能在真正中點的左方，但根據題意，此時要取的中點就是p[m]。此外，在比較m-1以及m與中點的距離時，這裡的寫法是比較與端點的距離。與端點較遠的就是離中點較近。當然也有其他的寫法。
```cpp=
// p_1_3a, linear search middle-point
#include <cstdio>
#define N 50010
typedef long long LL;
LL p[N];
// find the cut in (left,right), and then recursively
LL cut(int left, int right) {
if (right-left<=1) return 0;
LL len=p[right]-p[left], k=(p[right]+p[left])/2;
int m=left;
while (p[m]<k) m++; // linear search the first >=k
if (p[m-1]-p[left] >= p[right]-p[m]) // check if m-1 is better
m--;
return len + cut(left, m) + cut(m, right);
}
int main() {
int i, n, l;
scanf("%d%d", &n, &l);
p[0]=0; p[n+1]=l; // left and right ends
for (i=1; i<=n; i++) scanf("%lld", &p[i]);
printf("%lld\n",cut(0, n+1));
return 0;
}
```
主程式中我們只需做輸入的動作，我們把頭尾加上左右端的座標，然後直接呼叫遞迴函數取得答案。如果採用二分搜來找中點，我們可以自己寫，也可以呼叫C++ STL的庫存函數。二分搜的寫法通常有兩種：一種(比較常見的)是維護搜尋範圍的左右端，每次以中點來進行比較，縮減一半的範圍。在陣列中以二分搜搜尋某個元素的話，這種方法是不會有甚麼問題，但是二分搜應用的範圍其實很廣，在某些場合這個方法很容易不小心寫錯。這裡推薦另外一種二分搜的寫法，它的寫法很直覺也不容易寫錯。
```
// 跳躍法二分搜
// 假設遞增值存於 p[]，在p[s]~p[t]找到最後一個 < x 的位置
k = s; // k存目前位置, jump是每次要往前跳的距離，逐步所減
for (jump = (t – s)/2; jump>0; jump /= 2) {
while (k+jump<t && p[k+jump]<x) // 還能往前跳就跳
k += jump;
}
```
唯一要提醒的有兩點：第一是要先確認p[s]<x，否則最後的結果m=s而p[m]>=x；第二是內迴圈要用while而不能只用if，因為事實上內迴圈最多會做兩次。
我們來看看應用在這題時的寫法，以下只顯示副程式，其他部分沒變就省略了。
```cpp=
LL cut(int left, int right) {
if (right-left<=1) return 0;
int m=left;
LL k=(p[right]+p[left])/2;
for (int jump=(right-left)/2;jump>0; jump>>=1) {
while (m+jump<right && p[m+jump]<k)
m+=jump;
}
if (p[m]-p[left] < p[right]-p[m+1])
m++;
return p[right]-p[left] + cut(left, m) + cut(m, right);
}
```
我們也可以呼叫C++ STL中的函數來做二分搜。以下程式是一個範例。
呼叫lower_bound(s,t,x)會在$[s,t)$的區間內找到第一個>= x的位置，回傳的是位置，所以把它減去起始位置就是得到索引值。
```cpp=
// 偷懶的方法，加以下這兩行就可以使用STL中的資料結構與演算法函數
#include <bits/stdc++.h>
using namespace std;
#define N 50010
typedef long long LL;
LL p[N];
// find the cut in (left,right), and then recursively
LL cut(int left, int right) {
if (right-left<=1) return 0;
LL k=(p[right]+p[left])/2;
int m=lower_bound(p+left, p+right,k)-p;
if (p[m-1]-p[left] >= p[right]-p[m])
m--;
return p[right]-p[left] + cut(left, m) + cut(m, right);
}
```
有關二分搜在下一章裡面會有更多的說明與應用。
---
##### Q-1-4. 支點切割 (APCS201802) (@@)
輸入一個大小為N的一維整數陣列$p[]$，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於3或切到給定的層級$K$就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，但不可以是兩端點，也就是說，若區段的範圍是$[s,t]$，則要找出切點 $m\in [s+1,t-1]$，使得 $| \sum_{i=s}^{t} p[i]\times (i-m) |$ 越小越好，如果有兩個最佳切點，則選擇編號較小的。所謂切割層級的限制，第一次切以第一層計算。
Time limit: 1秒
輸入格式：第一行有兩個正整數$N$與$K$。第二行有$N$個正整數，代表陣列內容$p[1]$ ~ $p[N]$，數字間以空白隔開，總和不超過1e9。$N \le 50000$，切割層級限制$K<30$。
輸出：所有切點的p[ ]值總和。
範例一輸入：
7 3
2 4 1 3 7 6 9
範例一輸出：
11
範例二輸入：
5 1
1 2 3 4 100
範例二輸出：
4
範例一說明：第一層切在7，切成第二層的[2, 4, 1, 3]與[6, 9]。左邊[2, 4, 1, 3]切在4與1都是最佳，選擇4來切，切成[2]與[1, 3]，右邊[6, 9]不到3個就不切了。第三層都不到3個，所以終止。總計切兩個位置7+4=11。
範例二說明：第一層切在4(注意切點不可在端點)，切出[1, 2, 3]與[100]，因為K=1，所以不再切。
提示：與P_1_3類似，只是找切割點的定義不同，終端條件多了一個切割層級。
---
##### Q-1-5. 二維黑白影像編碼 (APCS201810)
假設$n$ 是2的冪次，也就是存在某個非負整數$k$使得 $n = 2^k$ 。將一個$n\times n$的黑白影像以下列遞迴方式編碼：
* 如果每一格像素都是白色，我們用0來表示；
* 如果每一格像素都是黑色，我們用1來表示；
* 否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 $n/2$ 的小正方形後，然後表示如下：先寫下$2$，之後依續接上左上、右上、左下、右下四塊的編碼。
輸入編碼字串$S$以及影像尺寸$n$，請計算原始影像中有多少個像素是$1$。
Time limit: 1秒
輸入格式：第一行是影像的編碼 $S$，字串長度小於1,100,000。第二行為正整數 $n$，$1\le n \le 1024$，其中 $n$ 必為2 的冪次。
輸出格式：輸出有多少個像素是1。
範例輸入：
2020020100010
8
範例輸出：
17
---
## 以遞迴窮舉暴搜
窮舉(Enumeration)與暴搜(Brute Force)是一種透過嘗試所有可能來搜尋答案的演算法策略。通常它的效率很差，但是在有些場合也是沒有辦法中的辦法。暴搜通常是窮舉某種組合結構，例如：n取2的組合，所有子集合，或是所有排列等等。因為暴搜也有效率的差異，所以還是有值得學習之處。通常以迴圈窮舉的效率不如以遞迴方式來做，遞迴的暴搜方式如同以樹狀圖來展開所有組合，所以也稱為分枝演算法或Tree searching algorithm，這類演算法可以另外加上一些技巧來減少執行時間，不過這個部份比較困難，這裡不談。
以下舉一些例子，先看一個迴圈窮舉的例題，本題用來說明，未附測資。
---
##### P-1-6. 最接近的區間和
假設陣列$A[0..n-1]$中存放著某些整數，另外給了一個整數$K$，請計算最接近$K$而不超過$K$的連續區段的和。
---
(這個問題有更有效率的解，在此我們先說明窮舉的解法。)
要尋找的是一個連續區段，一個連續區段可以用一對註標(index) $[i,j]$ 來定義，因此我們可以窮舉所有的 $0\le i\le j< n$。剩下的問題是對於任一區段$[i,j]$，如何計算$A[i..j]$區間的和。最直接的做法是用sum來計算，這導致以下的程式：
```cpp=
// O(n^3) for range-sum
int best = K; // solution for empty range
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j++) {
int sum=0;
for (int r=i; r<=j; r++)
sum += A[r];
if (sum<=K && K-sum<best)
best = K-sum;
}
}
printf("%d\n", best);
```
上述程式的複雜度是$O(n^3)$，如果我們認真想一下，會發現事實上這個程式可以改進的。對於固定的左端 i，若我們已經算出[i,j]區間的和，那麼要計算[i,j+1]的區間和只需要再加上A[j+1]就可以了，而不需要整段重算。於是我們可以得到以下$O(n^2)$的程式：
```cpp=
// O(n^2) for range-sum
int best = K; // solution for empty range
for (int i=1; i<=n; i++) {
int sum=0;
for (int j=i; j<=n; j++) {
sum += A[j]; // sum of A[i] ~ A[j]
if (sum<=K && K-sum<best)
best = K-sum;
}
}
printf("%d\n", best);
```
另外一種$O(n^2)$的程式解法是利用前綴和(prefix sum)，前綴和是指：對每一項 $i$，從最前面一直加到第$i$項的和，也就是定義 $ps[i]=\sum_{j=1}^{i}A[j]$。前綴和有許多應用，基本上，我們可以把它看成一個前處理，例如，如果已經算好所有的前綴和，那麼，對任意區間$[i,j]$，我們只需要一個減法就可以計算出此區間的和，因為
$\sum_{r=i}^{j} A[r]= ps[j]-ps[i-1]$ for $i>0$。
當$i=0$時，$[i,j]$的區間和即是$ps[j]$。
此外，我們只需要$O(n)$的運算就可以計算出所有的前綴和，因為
$ps[i]=ps[i-1]+A[i]$ for $i>0$。以下是利用prefix-sum的寫法，為了方便，我們設$ps[0]=0$。
```cpp=
// O(n^2) for range-sum, using prefix sum
ps[0]=0;
for (int i=1; i<=n; i++)
ps[i]=ps[i-1]+A[i];
int best = K; // solution for empty range
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j++) {
int sum = ps[j] - ps[i-1];
if (sum<=K && K-sum<best)
best = K-sum;
}
}
printf("%d\n", best);
```
接下來看一個暴搜子集合的例題。
---
##### P-1-7. 子集合乘積
輸入$n$個正整數，請計算其中有多少組合的相乘積除以$P$的餘數為1，每個數字可以選取或不選取但不可重複選，輸入的數字可能重複。$P=10009$，$0<n<26$。
輸入第一行是$n$，第二行是$n$個以空白間隔的正整數。
輸出有多少種組合。
若輸入為$[1, 1, 2]$，則有三種組合，選第一個1，選第2個1，以及選兩個1。
time limit = 1 sec。
---
我們以窮舉所有的子集合的方式來找答案，這裡的集合是指multi-set，也就是允許相同元素，這只是題目描述上的問題，對解法沒有影響。
要窮舉子集合有兩個方法：迴圈窮舉以及遞迴，遞迴會比較好寫也較有效率。先介紹迴圈窮舉的方法。
因為通常元素個數很有限，我們可以用一個整數來表達一個集合的子集合：第$i$個bit是1 或0代表第$i$個元素在或不在此子集合中。看以下的範例程式：
```cpp=
// subset product = 1 mod P, using loop
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, ans=0;
long long P=10009, A[26];
scanf("%d", &n);
for (int i=0;i<n;i++) scanf("%lld", &A[i]);
for (int s=1; s< (1<<n); s++) { // for each subset s
long long prod=1;
for (int j=0;j<n;j++) { // check j-th bit
if (s & (1<<j)) // if j-th bit is 1
prod = (prod*A[j])%P; // remember %
}
if (prod==1) ans++;
}
printf("%d\n", ans);
}
```
以下是遞迴的寫法。為了簡短方便，我們把變數都放在全域變數。遞迴副程式rec(i, prod)之參數的意義是指目前考慮第i個元素是否選取納入子集合，而prod是目前已納入子集合元素的乘積。
遞迴的寫法時間複雜度是$O(2^n)$ 而迴圈的寫法時間複雜度是$O(n\times 2^n)$。
```cpp=
// subset product = 1 mod P, using recursion
#include<bits/stdc++.h>
using namespace std;
int n, ans=0;
long long P=10009, A[26];
// for i-th element, current product=prod
void rec(int i, int prod) {
if (i>=n) { // terminal condition
if (prod==1) ans++;
return;
}
rec(i+1, (prod*A[i])%P); // select A[i]
rec(i+1, prod); // discard A[i]
return;
}
int main() {
scanf("%d", &n);
for (int i=0;i<n;i++) scanf("%lld", &A[i]);
ans=0;
rec(0,1);
printf("%d\n", ans-1); // -1 for empty subset
return 0;
}
```
以下是一個與八后問題類似的習題。
---
##### Q-1-10. 最多得分的皇后
在一個 $n\times n$的方格棋盤上每一個格子都有一個正整數的得分，如果將一個皇后放在某格子上就可以得到該格子的分數，請問在放置的皇后不可以互相攻擊的條件下，最多可以得到幾分，皇后的個數不限制。$0 < n < 11$。每格得分數不超過100。
Time limit: 1秒
輸入格式：第一行是$n$，接下來$n$行是格子分數，由上而下，由左而右，同行數字以空白間隔。
輸出格式：最大得分。
範例輸入：
3
1 4 2
5 3 2
7 8 5
範例輸出：
11
說明：選擇4 與 7。
(請注意：是否限定恰好$n$個皇后答案不同，但解法類似，本題不限恰好$N$個皇后，所以遞迴搜尋過程要考慮某些列不放皇后的可能)
---
上面幾個例子都可以看到遞迴窮舉通常比迴圈窮舉來得有效率，有些問題迴圈的方法甚至很不好寫，而遞迴要容易得多，以下的習題是一個例子。
---
##### Q-1-11. 刪除矩形邊界 — 遞迴 (APCS201910, subtask)
一個矩形的邊界是指它的最上與最下列以及最左與最右行。對於一個元素皆為0與1的矩陣，每次可以刪除四條邊界的其中之一，要以逐步刪除邊界的方式將整個矩陣全部刪除。刪除一個邊界的成本就是「該邊界上0的個數與1的個數中較小的」。例如一個邊界如果包含3個0與5個1，刪除該邊界的成本就是 $\min\{3,5\} = 3$。
根據定義，只有一列或只有一行的矩陣的刪除成本是0。不同的刪除順序會導致不同的成本，本題的目標是要找到最小成本的刪除順序。
Time limit: 1秒
輸入格式：第一行是兩個正整數 $m$ 和 $n$，以下$m$行是矩陣內容，順序是由上而下，由左至右，矩陣內容為0或1，同一行數字中間以一個空白間隔。$m + n \le 13$。
輸出格式：最小刪除成本。
範例輸入：
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
範例輸出：
1
---
提示：將目前的矩陣範圍當作遞迴傳入的參數，對四個邊界的每一個，遞迴計算刪除該邊界後子矩陣的成本，對四種情形取最小值，遞迴的終止條件是：如果只有一列或一行則成本為0。(本題有更有效率的DP解法)
**本單元結束**
Sign in with Wallet
Connect another wallet