[13] 遞歸

上一節：《字典》

第六節介紹了遞歸函數的寫法，也就是在函數實現的內部調用函數本身。藉助遞歸，我們可以很直觀地把一個看似複雜的問題規約為若干簡單問題。只要能證明規約過程是正確的，那麼遞歸的結果就一定是正確的。這是程序的魔力，也是數學的魔力。

例如要實現函數 f(n)=1+2+...+n 。規約過程是這樣的：

如果n==1，f(n)=1 （遞歸終止條件）否則，f(n)=(1+2+...+(n-1))+n=f(n-1)+n

可以按照下面這個機械的過程計算f(4)：

f(4) = f(3) + 4 …… 中間狀態1f(3) = f(2) + 3 …… 中間狀態2f(2) = f(1) + 2 …… 中間狀態3f(1) = 1 （遞歸終止條件）因為f(1)=1，中間狀態3=> f(2)=1+2=3因為f(2)=3，中間狀態2=> f(3)=3+3=6因為f(3)=6，中間狀態1=> f(4)=6+4=10。遞歸結束。

C語言代碼如下：

int f(int n){ if (n == 1) return 1; else return f(n-1) + n;}int main(){ return f(4);}

看完這段代碼有同學會提出質疑：「在函數f的實現代碼裡面使用函數f，這是不科學的。因為在函數都還沒有定義好的時候，怎麼能使用它呢？」 這裡不正面回答這個問題，不過下面有4種等價的變體，都可以不用在函數還沒完成定義時調用函數自身：

遞歸變體1：

int (*g)(int); // 定義函數類型的全局變數gint f(int n){ if (n == 1) return 1; else return g(n-1) + n;}int main(){ g = f; return f(4);}

遞歸變體2：

int f(void* h, int n){ if (n == 1) return 1; int(*g)(void*, int) = h; // 隱式類型轉換 return g(h, n-1) + n;}int main(){ return f(f, 4);}

遞歸變體3：

int f(void* g, int n){ if (n == 1) return 1; return ((int(*)(void*, int))g)(g, n-1) + n; // 強制類型轉換}int main(){ return f(f, 4);}

遞歸變體4：

typedef struct _t { int(*g)(struct _t*, int); } T;int f(T* t, int n){ if (n == 1) return 1; return t->g(t, n - 1) + n;}int main(){ return f(&(T){f}, 4);}

背包問題

題目描述：你有一個背包和N件物品，第 件物品的重量是 價值是 ，而背包最多能裝總重量不超過V的物品。求解背包能裝入的物品價值最大總和為多少。

樣例：

N=5 V=16c[1]=6 w[1]=6c[2]=5 w[2]=12c[3]=4 w[3]=3c[4]=7 w[4]=10c[5]=2 w[5]=3

答案：

25

解法：

定義函數f(x, y)來表示「只考慮第1~x件物品，且背包總重量不超過y」的價值最大總和。

怎樣對函數f進行規約呢？

• 首先是最簡單的邊界情況，如果x=0或者y=0，f(x, y)都應該等於0；
• 其次，要使f(x, y)最大，只有兩種可能操作，一種可能是裝入第x件物品後價值最大（前提是裝入後不超重），另一種可能是不裝入第x件物品的價值最大。

綜合這兩點，我們可以得出遞歸表達式：

如果x==0或者y==0，f(x, y)=0如果c[x]<=y，f(x, y)=f(x-1, y-c[x])+w[x]和f(x-1, y)的較大者否則f(x, y)=f(x-1, y)

代碼如下：

typedef struct { int c; int w; } Item;int max(int x, int y){ return x > y ? x : y;}int f(int x, int y, Item t[]){ if (x == 0 || y == 0) return 0; if (t[x].c <= y) return max( f(x - 1, y - t[x].c, t) + t[x].w, f(x - 1, y, t) ); else return f(x - 1, y, t);}int main(){ int N = 5; int V = 16; Item items[] = { [1]={.c=6, .w=6}, {.c=5, .w=12}, {.c=4, .w=3}, {.c=7, .w=10}, {.c=2, .w=3} }; return f(N, V, items);}

八皇后問題

題目描述：要在一個國際象棋棋盤上擺放八個皇后，且它們相互不會攻擊，問一共有多少種擺法（不考慮旋轉等價）。

解法：

遞歸除了可以規約問題外，還可以實現「回溯法」遍歷。回溯法依賴「上下文」來保存當前的考察對象，並且要不斷地改變上下文，使得在遍歷結束的時候，所有可能的情況都已經被考察過。

以八皇后問題為例，假設棋盤左上角坐標為(0, 0)，右下角坐標為(7, 7)，回溯的方式如下：

當前要考察第x行的皇后擺放： 假設第x行的皇后擺在第0列： 如果第x行的皇后不會攻擊已經擺放的皇后： 如果當前考察的是第7行，則結果增加1；否則考察第x+1行的擺放 假設第x行的皇后擺在第1列： ……（同上，略）…… …… …… 假設第x行的皇后擺在第7列： ……（同上，略）…… 返回上一層考察

現在我們可以用f(x)來表示當前考察第x行的皇后擺放，代碼如下（注意函數f返回值類型是void）：

#define Q 8 // 設置棋盤大小int a[Q] = {}; // a[i]表示第i行的皇后所在的列。因為每一行只能有一個皇后，所以不需要用二維數組int ans = 0;int valid(int x){ int i; for (i = 0; i < x; i++) { if (a[i] == a[x] || a[i] - a[x] == i - x || a[i] - a[x] == x - i) return 0; } return 1;}void f(int x){ int i; for (i = 0; i < Q; i++) { a[x] = i; // 當前擺放：第x行的皇后擺在第i列 if (valid(x)) { // 判斷皇后(x, a[x])是否會攻擊到(0, a[0]), (1, a[1])...(x-1, a[x-1]) if (x == Q - 1) ans += 1; // 8行皇后都沒有互相攻擊，答案增加1 else f(x + 1); // 遍歷下一行皇后的擺放 } }}int main(){ f(0); return ans;}

如果不想使用全局變數a[]和ans來表示上下文的話，也可以寫成下面的代碼：

#define Q 8 // 設置棋盤大小int valid(int a[], int x){ int i; for (i = 0; i < x; i++) { if (a[i] == a[x] || a[i] - a[x] == i - x || a[i] - a[x] == x - i) return 0; } return 1;}void f(int x, int a[], int* n){ int i; for (i = 0; i < Q; i++) { a[x] = i; // 當前擺放：第x行的皇后擺在第i列 if (valid(a, x)) { // 判斷皇后(x, a[x])是否會攻擊到(0, a[0]), (1, a[1])...(x-1, a[x-1]) if (x == Q - 1) *n += 1; // 8行皇后都沒有互相攻擊，答案增加1 else f(x + 1, a, n); // 遍歷下一行皇后的擺放 } }}int main(){ int a[Q] = {}; // a[i]表示第i行的皇后所在的列。因為每一行只能有一個皇后，所以不需要用二維數組 int ans = 0; f(0, a, &ans); return ans;}

運行程序可知，八皇后問題的答案是92。

練習題一：踩氣球比賽

題目描述（參見ZOJ1003）：兩個小朋友比賽踩100個氣球，氣球上標有1~100的號碼，每踩一個氣球，則自己的得分可以乘以該氣球的標號（初始得分為1，每個氣球只能踩一次）。比賽結束後兩個人自己說出自己的得分，如果雙方的得分是不可能的，則得分低的人獲勝，否則得分高的人獲勝。

例如，一個人說自己得分是343，而另一個人說自己的得分是49。由於343=7x49，所以兩個人都必須踩了標號49的氣球，但每個氣球只能踩一次，所以343和49這對得分是不可能的。根據規則，得分49的人獲勝。

樣例：

輸入：343 493599 61062 36輸出：4961062

練習題二：加法分拆

題目描述：把一個整數分拆成所有可能的加法形式，並且全部列印在屏幕上。（注意：1+2+1和2+1+1隻能算是一種形式）

樣例：

輸入：5輸出：1+1+1+1+11+1+1+21+1+31+2+21+42+3

下一節： 《多維數組》