從零開始的演算法競賽入門教學
0%

0-10 遞迴

發表於

遞迴是什麼

狹義的遞迴，指的是一個函式，在運行過程中，直接或間接的去呼叫了自己這個函式。沒錯，這是可以的，且是許多演算法實作過程的一部分。

但其實，遞迴不僅僅是語法，而是一種概念。將一個問題，歸約到一個或多個規模較小的子問題，不管它的實作方式是使用遞迴還是迴圈，我認為都可以算是遞迴的一部份。遞迴的這個概念，在演算法競賽裡非常重要。未來在第二、三章節，會一次又一次的，以不同模樣出現，DP根本就是遞迴，排序、資料結構在實作的過程中，亦有許多遞迴的影子。

但現在，我們就來看看狹義遞迴的語法吧

語法

1
2
3
4
void func(){
    //...
    func();
}

基本上，概念是這樣的。當然，如果沒有自己設定，遞迴是不可能停下來的。由於非常容易掛掉以及 debug 較為困難，因此遞迴成為了不少人的惡夢。

在撰寫遞迴程式時，務必再三確認是否有設定中止條件，以及其是否正確，不然要是停不下來的話就糟糕了。

範例

今天，我要印出從 1 ~ n 裡的每一個整數。當然，我可以使用迴圈實作，而且迴圈也是更好的作法。但為了使讀者更明白遞迴的過程，這裡使用遞迴撰寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
    cout << x << '\n';
    if(x == n) return; // 中止條件 相當重要
    print(x + 1);
}

int main(){
    print(1);
}

問題相對直觀，得到參數 x 後，輸出它，並且以 x + 1 作為參數呼叫下一次遞迴，直到 x 等於 5 時才停下。輸出為：

1
2
3
4
5
1
2
3
4
5

但如果今天程式是這樣呢？

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
    if(x < n) print(x + 1);
    cout << x << '\n';
}

int main(){
    print(1);
}

這時候，變成我先呼叫 print(x + 1)後，再輸出 x，這樣的輸出會是什麼呢？稍微有點難想，但若從 5 反推回來，print(5)只輸出 5，print(4) 是 print(5) 後輸出 4，print(3) 是 print(4) 後輸出 3，可以發現，輸出應該就是：

1
2
3
4
5
5
4
3
2
1

困難的來了，如果我的程式是這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
    if(x < n){
        print(x + 1);
        print(x + 2);
    }
    cout << x << '\n';
}

int main(){
    print(1);
}

這就不是個簡單的遞迴函式了，事實上，我也無法在不借助紙筆的方式下，得知它的輸出。呼叫 print(1) 時，我先呼叫了 print(2)，這時 print(2) 會一直遞迴下去，直到 print(2) 完全結束以後，再呼叫 print(3)。等到 print(3) 結束後，最後輸出 1。

最後的輸出長這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5
6
4
5
3
5
6
4
2
5
6
4
5
3
1

很難理解吧！我們嘗試透過一些輔助的文字去幫助理解，紀錄一個值d，代表我現在處於遞迴中的第d層，輸出該數前，我先輸出d個空格，以此區分不同層的輸出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x, int d){
    if(x < n){
        print(x + 1, d + 1);
        print(x + 2, d + 1);
    }
    for(int i=0;i<d;i++) cout<<" ";
    cout << x << '\n';
}

int main(){
    print(1, 0);
}

輸出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    5
    6
   4
   5
  3
   5
   6
  4
 2
   5
   6
  4
  5
 3
1

恩…還是有點難懂，不然我們在呼叫print(x+1)跟print(x+2)時，都輸出一句話好了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x, int d){
    if(x < n){
        for(int i=0;i<d;i++) cout<<" ";
        cout<<"x = " << x <<", print(x+1):\n";
        print(x + 1, d + 1);
        for(int i=0;i<d;i++) cout<<" ";
        cout<<"x = " << x <<", print(x+2):\n";
        print(x + 2, d + 1);
    }
    for(int i=0;i<d;i++) cout<<" ";
    cout << x << '\n';
}

int main(){
    print(1, 0);
}

輸出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
x = 1, print(x+1): // a
 x = 2, print(x+1): // b
  x = 3, print(x+1): // c
   x = 4, print(x+1): // d
    5
   x = 4, print(x+2): // d
    6
   4
  x = 3, print(x+2): // c
   5
  3
 x = 2, print(x+2): // b
  x = 4, print(x+1):
   5
  x = 4, print(x+2):
   6
  4
 2
x = 1, print(x+2): // a
 x = 3, print(x+1):
  x = 4, print(x+1):
   5
  x = 4, print(x+2):
   6
  4
 x = 3, print(x+2):
  5
 3
1

其中，// 後方的字相同者，表示其分別是同一層中的 print(x+1) 與 print(x+2) 兩個函式，不是程式實際輸出。

遞迴的思考相當抽象，建議搭配影片理解。

但也因為這樣，遞迴可以用來解一般正常思考下想不到或難解決的問題，下方練習題皆為遞迴經典題，具有相當的難度，但理解後，會發現，用遞迴寫，原來這麼簡潔、乾淨、漂亮！

遞迴是…

我覺得，解決遞迴問題的過程，就像是人生。未來過於遙遠，無法想像、無法預測，我們唯一能夠改變的，只有每個當下的自己。不需要去猜測未來到底會變得如何，我們所能做的一切，只是把握此時此刻，努力面對並解決今天遇到的問題。並且相信：明天一定會更好的！

唯一不同的是，人生會在執行到一半時，突然發生大量意外，但程式基本上不會，除非你寫爛了。

練習題

河內塔問題(易 建議完全了解此題)：
ZeroJudge a227

合成函數：(中偏難) : tcirc d002

約瑟夫問題 定時K彈(難 有興趣可寫)：ZeroJudge c296

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// ZeroJudge a227
#include<bits/stdc++.h>
using namespace std;

int n;

void hanoi(int n, char from, char to, char mid){
	if(n == 1){ // 遞迴停止條件即為只需移一個盤子
		cout<< "Move ring " << n << " from " << from << " to " << to << '\n';
		return;
	}
	hanoi(n-1, from, mid, to); // 先想辦法把前面 n-1 個搬到中間那根柱子
	cout<< "Move ring " << n << " from " << from << " to " << to << '\n'; 
	hanoi(n-1, mid, to, from); // 把前面 n-1 個柱子從中間搬到目標上
}

int main(){
	while(cin>>n){
		hanoi(n,'A','C','B');
		cout<<'\n';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 合成函數
#include<bits/stdc++.h>
#define ll long long // 將程式裡的 ll 視為 long long 的意思
using namespace std;

ll n;
string s;

ll str_to_int(string s){ // 將字串轉為整數
	ll ans = 0, st = 0;
	bool neg = 0;
	if(s[st] == '-') neg = 1, st++;
	for(int i=st;i<s.size();i++) ans = ans * 10 + s[i] - '0';
	if(neg) ans = -ans;
	return ans;
}

ll solve(){
	cin >> s; // 讀入下一個
	if(s == "f"){
		ll x = solve(); // f 後面 有 1 個參數
		return x * 2 - 3;
	}
	else if(s == "g"){
		ll x = solve(); // g 後面 有 2 個參數
		ll y = solve();
		return x * 2 + y - 7;
	}
	else if(s == "h"){
		ll x = solve(); // h 後面 有 3 個參數
		ll y = solve();
		ll z = solve();
		return 3 * x - 2 * y + z;
	}
	else return str_to_int(s); // 是數字的話 就直接回傳
}

int main(){
	cout<<solve()<<'\n';
}

定時K彈詳解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定時K彈 最短的最難 https://www.facebook.com/nthuioncamp/posts/438261166736061
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, K;

int solve(int N, int M, int K){
	if(K == 0) return 0;
	return (solve(N-1, M, K-1) + M) % N;
}

int main(){
	cin >> N >> M >> K;
	cout << solve(N, M, K) + 1 << '\n';
}