# AP325-Python 第1章 遞迴
「遞迴是大事化小，要記得小事化無。」
「暴力或許可以解決一切，但是可能必須等到地球毀滅。」
「遞迴搜尋如同末日世界，心中有樹而程式(城市)中無樹。」
本章介紹遞迴函數的基本方法與運用，也介紹使用窮舉暴搜的方法。
---
## 基本觀念與用法
遞迴在數學上是函數直接或間接以自己定義自己，在程式上則是函數直接或間接呼叫自己。遞迴是一個非常重要的程式結構，在演算法上扮演重要的角色，許多的算法策略都是以遞迴為基礎出發的，例如分治與動態規劃。
學習遞迴是一件重要的事，不過遞迴的思考方式與一般的不同，它不是直接的給予答案，而是間接的說明答案與答案的關係，不少程式的學習者對遞迴感到困難。以簡單的階乘為例，如果採直接的定義：
對正整數$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$。
現在大多數的程式語言都支援遞迴函數的寫法，而函數呼叫與轉移的過程，正如上面逐步推導的過程一樣，雖然過程有點複雜，但不是寫程式的人的事，以程式來撰寫遞迴函數幾乎就跟定義一模一樣。上面的階乘函數以程式來實作可以寫成：
```python=
def fac(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$.
以程式來實作可以寫成：
```python=
def f(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$。
程式如下：
```python=
def cat(n):
if n == 0: return 1
return sum(cat(i)*cat(n-1-i) for i in range(n))
```
遞迴程式雖然好寫，但往往有效率不佳的問題，通常遞迴函數裡面只呼叫一次自己的效率比較不會有問題，但如果像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
---
題解：合成函數的意思是它的傳入參數可能是個數字也可能是另外一個函數值。以遞迴的觀念來思考，我們可以將一個合成函數的表示式定義為一個函式$expr()$，這個函式從輸入讀取字串，回傳函數值。其流程只有兩個主要步驟，第一步是讀取一個字串，根據題目定義，這個字串只有3種情形：f, g 或是一個數字。第二步是根據這個字串分別去進行 f 或 g 函數值的計算或是直接回傳字串代表的數字。至於如何計算 f 與 g 的函數值呢？如果是 f，因為它有一個傳入參數，這個參數也是個合成函數，所以我們遞迴呼叫 $expr()$來取得此參數值，再根據定義計算。如果是g，就要呼叫$expr()$兩次取得兩個參數。 以下是演算法流程：
```
# P_1_1 的演算法流程規劃
int expr() // 一個遞迴函式，回傳表示式的值
找到一個空白間隔的字串token;
if token是f then
x = expr();
return 2*x - 1;
else if token是g then
x = expr();
y = expr();
return x + 2*y - 3;
else // token是一個數字字串
return token代表的數字
end of eval()
```
程式實作時，我們先將輸入讀入餅以空白切割後放在一個list line中，變數idx指出目前處理到第幾個字串。遞迴的程式幾乎照著演算法寫就可以了，第五行我們取得目前的字串$token$並將$idx$加一指向下一個位置。其他的部分就是照著寫改成python語法而已。
```python=
line = list(input().split())
idx = 0 # current index of line
def expr(): # return the result
global idx
token = line[idx]
idx += 1
if token == 'f':
x = expr()
return 2*x - 1
elif token == 'g':
x = expr()
y = expr()
return x + 2*y -3
else: # an int string
return int(token)
#
print(expr())
```
下面是個類似的習題。
---
##### 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題解：棍子切斷後，要針對切開的兩段重複做切割的動作，所以是遞迴的題型。因為切點的座標值並不會改變，我們可以將座標的陣列放在全域變數中，遞迴函數需要傳入的是本次切割的左右端點。函數的架構很簡單：
```
// 座標存於 p[]
// 遞迴函式，回傳此段的總成本
def 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$。
這一題因為數值的範圍所限，採取最簡單的線性搜尋即可，但二分搜是更快的方法，因為座標是遞增的。以下看實作，先看以線性搜尋的範例程式。
這裡有些細節要留意，當中點的位置非整數時，$x$因為捨位誤差比真正的中點位置小$0.5$，若$p[m]==x$，它可能在真正中點的左方，但根據題意，要取的中點就是$p[m]$。此外，在比較$m-1$以及$m$與中點的距離時，這裡第12行的寫法是比較與端點的距離。與端點較遠的就是離中點較近。當然也有其他的寫法。
```python=
# p_1_3a, linear search middle-point
n,l = [int(x) for x in input().split()]
p = [0]+[int(x) for x in input().split()]+[l]
# including left and right end point
# find the cut in (left,right), and then recursively
def cut(left, right):
if right - left <= 1: return 0 # no cost
leng = p[right]-p[left]
k = (p[right]+p[left])//2
m = left
while p[m] < k: m += 1 # linear search the first >=k
if p[m-1]-p[left] >= p[right]-p[m]: # if m-1 is better
m -= 1
return leng + cut(left, m) + cut(m, right)
#
print(cut(0, n+1))
```
主程式中我們只需做輸入的動作，我們把頭尾加上左右端的座標，然後直接呼叫遞迴函數取得答案。
如果採用二分搜來找中點，我們可以自己寫，也可以呼叫Python 的庫存函數。二分搜的寫法通常有兩種：一種(比較常見的)是維護搜尋範圍的左右端，每次以中點來進行比較，縮減一半的範圍。在陣列中以二分搜搜尋某個元素的話，這種方法是不會有甚麼問題，但是二分搜應用的範圍其實很廣，在某些場合這個方法很容易不小心寫錯。這裡推薦另外一種二分搜的寫法，它的寫法很直覺也不容易寫錯。
```
# 跳躍法二分搜
# 假設遞增值存於 p[]，在p[s]~p[t]找到最後一個 < x 的位置
k = s; // k存目前位置, jump是每次要往前跳的距離，逐步所減
jump = (t – s)/2
while jump > 0:
while k+jump<t and p[k+jump]<x: # 還能往前跳就跳
k += jump;
jump //= 2
```
唯一要提醒的有兩點：第一是要先確認$p[s]<x$，否則最後的結果$m=s$而$p[m]>=x$；第二是內迴圈要用while而不能只用if，因為事實上內迴圈最多會做兩次。我們來看看應用在這題時的寫法。
```python=
# p_1_3b, binary search middle-point
n,l = [int(x) for x in input().split()]
p = [0]+[int(x) for x in input().split()]+[l]
# including left and right end point
# find the cut in (left,right), and then recursively
def cut(left, right):
if right - left <= 1: return 0 # no cost
k = (p[right]+p[left])//2
m = left
jump = (right-left)//2
while jump:
while m+jump<right and p[m+jump]<k:
m += jump
jump >>= 1
if p[m]-p[left] < p[right]-p[m+1]:
m += 1
return p[right]-p[left]+cut(left, m)+cut(m, right)
#
print(cut(0, n+1))
```
我們也可以呼叫Python庫存函數中的二分搜bisect.bisect_left()來做。以下程式是一個範例。
呼叫bisect_left(p,x) 會在遞增的list $p$中找到第一個>= x的位置，回傳的是位置(index)。
```python=
# p_1_3c, bisect_left binary search middle-point
from bisect import bisect_left
n,l = [int(x) for x in input().split()]
p = [0]+[int(x) for x in input().split()]+[l]
# including left and right end point
# find the cut in (left,right), and then recursively
def cut(left, right):
if right - left <= 1: return 0 # no cost
k = (p[right]+p[left])//2
m = bisect_left(p,k)-1 # last one <x
if p[m]-p[left] < p[right]-p[m+1]:
m += 1
return p[right]-p[left]+cut(left, m)+cut(m, right)
#
print(cut(0, n+1))
```
有關二分搜在下一章裡面會有更多的說明與應用。
---
##### 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來計算，這導致以下的程式：
```python=
# O(n^3) for range-sum
best = 0 # solution for empty range
for i in range(n):
for j in range(i,n):
isum = sum(A[i:j+1])
if isum<=K and isum>best:
best = isum
#
#
print(best)
```
上述程式的複雜度是$O(n^3)$，請注意sum()其實是個迴圈。如果我們認真想一下，會發現事實上這個程式可以改進的。對於固定的左端 $i$，若我們已經算出$[i,j]$區間的和，那麼要計算$[i,j+1]$的區間和只需要再加上$A[j+1]$就可以了，而不需要整段重算。於是我們可以得到以下$O(n^2)$的程式：
```python=
# O(n^2) for range-sum
best = 0 # solution for empty range
for i in range(n):
isum = 0
for j in range(i,n):
isum += A[j]
if isum<=K and isum>best:
best = isum
#
#
print(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[n]$設為$0$，如此一來$ps[-1]$是最後一項，也就是$ps[n]=0$。
```python=
# O(n^2) for range-sum, using prefix sum
ps = [0]*n
for i in range(n):
ps[i] = ps[i-1]+A[i]
best = 0 # solution for empty range
for i in range(n):
for j in range(i,n):
isum = ps[j]-ps[i-1]
if isum<=K and isum>best:
best = isum
#
#
print(best)
```
接下來看一個暴搜子集合的例題。
---
##### P-1-7. 子集合乘積
輸入$n$個正整數，請計算其中有多少組合的相乘積除以$P$的餘數為1，每個數字可以選取或不選取但不可重複選，輸入的數字可能重複。$P=10009$，$0<n<21$。
輸入第一行是$n$，第二行是$n$個以空白間隔的正整數。
輸出有多少種組合。
若輸入為$[1, 1, 2]$，則有三種組合，選第一個1，選第2個1，以及選兩個1。
time limit = 2 sec。
---
我們以窮舉所有的子集合的方式來找答案，這裡的集合是指multi-set，也就是允許相同元素，這只是題目描述上的問題，對解法沒有影響。
要窮舉子集合有兩個方法：迴圈窮舉以及遞迴，遞迴會比較好寫也較有效率。先介紹迴圈窮舉的方法。
因為通常元素個數很有限，我們可以用一個整數來表達一個集合的子集合：第$i$個bit是1 或0代表第$i$個元素在或不在此子集合中。看以下的範例程式：
```python=
# subset product = 1 mod P, using loop
n = int(input())
a = [int(x) for x in input().split()]
P = 10009
ans = 0
for s in range(1,(1<<n)): # for each subset s
prod = 1
for j in range(n): # check j-th bit
if s & (1<<j): # if j-th bit is 1
prod = (prod*a[j])%P; # remember %
if prod==1: ans += 1
print(ans)
```
以下是遞迴的寫法。遞迴副程式$rec(arr, i, prod)$之參數的意義是指目前考慮list $arr$的第$i$個元素是否選取納入子集合，而$prod$是目前已納入子集合元素的乘積。
遞迴的寫法時間複雜度是$O(2^n)$ 而迴圈的寫法時間複雜度是$O(n\times 2^n)$。迴圈版可能無法通過全部的測資，需要看電腦速度。
```python=
# subset product = 1 mod P, using loop
n = int(input())
a = [int(x) for x in input().split()]
P = 10009
ans = 0
# for i-th element, current product=prod
def rec(arr, i, prod):
global ans
if i >=n : # terminal condition
if prod==1: ans += 1
return;
rec(arr, i+1, prod*arr[i]%P) # select A[i]
rec(arr, i+1, prod) # discard A[i]
return
#
rec(a,0,1)
print(ans-1) # -1 for empty subset
```
---
##### Q-1-8. 子集合的和 (APCS201810, subtask)
輸入$n$個正整數，請計算各種組合中，其和最接近$P$但不超過$P$的和是多少。每個元素可以選取或不選取但不可重複選，輸入的數字可能重複。$P\le$ 1e9+9，$0 < n < 21$。
Time limit: 2秒
輸入格式：第一行是$n$與$P$，第二行是$n$個可挑選的正整數，大小不會超過$P$，同行數字以空白間隔。
輸出格式：最接近$P$但不超過$P$的和。
範例輸入：
5 17
5 5 8 3 10
範例輸出：
16
---
接著舉一個窮舉排列的例子。西洋棋的棋盤是一個$8\times 8$的方格，其中皇后的攻擊方式是皇后所在位置的八方位不限距離，也就是只要是在同行、同列或同對角線(包含45度與135度兩條對斜線)，都可以攻擊。一個有名的八皇后問題是問說：在西洋棋盤上有多少種擺放方式可以擺上8個皇后使得彼此之間都不會被攻擊到。這個問題可以延伸到不一定限於是$8\times 8$的棋盤，而是$N\times N$的棋盤上擺放$N$個皇后。八皇后問題有兩個版本，這裡假設不可以旋轉棋盤。
---
##### P-1-9. N-Queen解的個數
計算N-Queen有幾組不同的解，對所有$0 < N < 12$。
(本題無須測資)
---
要擺上$N$個皇后，那麼顯然每一列恰有一個皇后，不可以多也不可以少。所以每一組解需要表示每一列的皇后放置在哪一行，也就是說，我們可以以一個List $p[]$來表示一組解，第$i$列的皇后放在第$p[i]$行。因為兩個皇后不可能在同一行，所以$p[]$必然是一個$0$ ~ $N-1$的排列。以下是遞迴的範例程式。
遞迴函數$nqr(p,n)$的輸入參數中，$p$是目前已經放的皇后的行編號，$n$是棋盤的大小。第3行是終端情形，$n$個皇后都已經成功擺放了，我們就回傳1並結束。
對於不是終端條件的情形，我們檢查這一列的每個位置是否可以放置皇后而不被之前所放置的皇后攻擊。第5行的迴圈嘗試第$i$行，第7行的迴圈枚舉$p$中每一個之前已經放的皇后座標$(r,col)$，檢查是否與目前位置$(len(p),i)$衝突，其中檢查是否在同一條對角線可以很簡單的檢查 「abs(行差值) == 列差值」。
對於每個找到的合法位置，我們將該位置加入$p$中(第12行)，遞迴呼叫進行下一列的擺放(第13行)，結束後再將加入的回復(第14行)，以便進行同一列的其他合法位置的嘗試。這樣類似trial and error的方法也稱為Backtracking。
```python=
# p[] are column indexes of previous rows
def nqr(p, n): # number of n-queen
if len(p) == n: return 1 # successful
total = 0
for i in range(n): # try each column
valid = True # check valid
for r,col in enumerate(p):
if col == i or abs(i-col) == len(p)-r:
valid = False
break
if valid:
p.append(i)
total += nqr(p, n)
p.pop() # backtracking recover
return total
#
for n in range(1,12):
print(nqr([], n))
```
函數中我們對每一個可能的位置 $i$ 都以一個 $j$-迴圈檢查該位置是否被攻擊，這似乎有點缺乏效率。我們可以對每一個之前的皇后，標記它在此列可以攻擊的位置，這樣就更有效率了。以下是這樣修改後的程式碼，這個程式大約比前一個快了一倍。
遞迴的方法不會超過$O(n\times n!)$，而且實際上要快很多，因為你可以看得到，在遞迴過程中，被已放置皇后攻擊的位置都被略去了，所以實際上並未嘗試所有排列。這種情況下我們知道他的複雜度上限，但真正準確的複雜度往往難以分析，如果以實際程式來量測，$n=11$時，$n!=39,916,800$，但遞迴被呼叫的次數只有$166,926$次，差了非常多。
```python=
# n-queen recursion, better implementation
# p[] are column indexes of previous rows
def nqr(p, n): # number of n-queen
if len(p) == n: return 1 # successful
total = 0
valid = [True]*n # if col i is valid
for r,col in enumerate(p): # mark invalid column
valid[col] = False # same column
i = col + len(p)-r # diagonal lower right
if i < n: valid[i] = False
i = col - (len(p)-r) # diagonal lower left
if i >= 0: valid[i] = False
for i in range(n): # try each column
if valid[i]:
p.append(i)
total += nqr(p, n)
p.pop() # backtracking recover
return total
#
for n in range(1,12):
print(nqr([], n))
```
以下是一個類似的習題。
---
##### Q-1-10. 最多得分的皇后
在一個 $n\times n$的方格棋盤上每一個格子都有一個正整數的得分，如果將一個皇后放在某格子上就可以得到該格子的分數，請問在放置的皇后不可以互相攻擊的條件下，最多可以得到幾分，皇后的個數不限制。$0 < n < 10$。每格得分數不超過100。
Time limit: 4秒
輸入格式：第一行是$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解法)
**第1章結束**
Sign in with Wallet
Connect another wallet