【C++】競程筆記（遞迴）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

遞迴（Recursion）

遞迴是函式的定義方式，這個函式透過呼叫自身來解決一個問題，並依賴於一個或多個終止條件來避免無限呼叫。

簡單來說，遞迴就是一個函式呼叫他自己本身，使得程式碼不斷地被執行，直到達成某個終止條件才會停止。

如：

1
2
3
int func(int a){
    func(a);
}

設計遞迴程式有兩個重點：

  1. 設定終止條件：避免進入無窮遞迴。
  2. 遞迴規則：將原問題簡化並以相同邏輯遞迴呼叫自身。

應用

  1. Fibonacci Number (Leetcode)：https://leetcode.com/problems/fibonacci-number/
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int fib(int n) {
        if (n == 0 || n == 1){
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
};

image

只需要很直覺的照公式寫就好。

  1. 河內塔：https://tioj.ck.tp.edu.tw/problems/1355

一開始所有盤子都會在 a 柱上，且由上往下是直徑由小到大的盤子。

然後要把所有盤子都移到最右邊的柱子上。

一開始一定只能移動最小的盤子，之後才能移動後續的盤子。

而河內塔的核心解法就如下所示：

:::success
先把前 n-1 個圓盤移到輔助柱子，接著把最大的圓盤移到目標柱子，最後再把 n-1 個圓盤從輔助柱子移到目標柱子。
:::

輔助柱子可以是任意一個柱子，反正最大的盤子一定要先在目標柱子就對了。

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
// from NTUCPC Guide
#include <iostream>

using namespace std;

void move(int a, int b){
    static int step = 0;
    ++step;
    cout << "#" << step << " : move the dish from #" << a << " to #" << b << "\n";
}

void hanoi(int n, int a, int b, int c){
    if (n == 1){
        move(a, b);
        return;
    }
    hanoi(n - 1, a, c, b);
    move(a, b);
    hanoi(n - 1, c, b, a);
}

int main(){
    int n;
    cin >> n;
    hanoi(n, 1, 3, 2);
    return 0;
}
  1. 河內塔（續）：https://tioj.ck.tp.edu.tw/problems/1356

柱子只能相鄰移動，從 1 往 3 或 3 往 1，必須經過 2。

這種河內塔比較麻煩，所以要透過 if-else 判斷是否相鄰，再用遞迴的方式去移動盤子。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cmath>

using namespace std;

int step = 0;

void hanoi(int n, int a, int b) {
    if (n == 1) {
        int d = abs(a - b);
        // 若不是相鄰，必先經過中柱 2
        if (d == 2) {
            int mid = 6 - a - b; // 不要直接寫 mid = 2
                                 // 當 a = 2, b = 3 時，mid 應該 = 1
                                 // 另外 mid 作用是找出輔助柱
            ++step;
            cout << "#" << step << " : move the dish from #" << a
                 << " to #" << mid << "\n";
            ++step;
            cout << "#" << step << " : move the dish from #" << mid
                 << " to #" << b << "\n";
        } else {
            ++step;
            cout << "#" << step << " : move the dish from #" << a
                 << " to #" << b << "\n";
        }
        return;
    }
    int d = abs(a - b);
    if (d == 2) {
        int mid = 6 - a - b;
        // 先將上面 n–1 片從 a 移到 b
        hanoi(n - 1, a, b);
        // 將第 n 片從 a 到 mid
        ++step;
        cout << "#" << step << " : move the dish from #" << a
             << " to #" << mid << "\n";
        // 將上面 n–1 片從 b 移回 a
        hanoi(n - 1, b, a);
        // 將第 n 片從 mid 到 b
        ++step;
        cout << "#" << step << " : move the dish from #" << mid
             << " to #" << b << "\n";
        // 再將 n–1 片從 a 移到 b
        hanoi(n - 1, a, b);
    } else {
        int other = 6 - a - b;
        // 相鄰柱子直接遞迴
        hanoi(n - 1, a, other);
        ++step;
        cout << "#" << step << " : move the dish from #" << a
             << " to #" << b << "\n";
        hanoi(n - 1, other, b);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    hanoi(n, 1, 3);
    return 0;
}