遞廻的概念

簡介

#

遞迴是一種在函式中直接或間接地調用自己的技術。這種技術通常用於解決可以被分解為相同類型的子問題的問題，或者是不知道套多少層迴圈的問題。

費氏數列

#

費氏數列是一個遞迴的例子，其定義如下：

$$
F(n) = \begin{cases}
0 & \text{if } n = 0 \
1 & \text{if } n = 1 \
F(n-1) + F(n-2) & \text{if } n > 1
\end{cases}
$$

這個定義可以直接翻譯成程式碼：

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

寫起來就跟數學式幾乎一樣，只要呼叫 fib(n) 就可以得到第 \(n\) 項費氏數列的值！

進階題

#

接下來我們來看一個稍微複雜的例子，這個例子是 2018 年 APCS 的第三題：

一個 \(n \times n\) 的黑白影像可以用下列遞迴方式編碼：

如果每一格像素都是白色，我們用 \(0\) 來表示； 如果每一格像素都是黑色，我們用 \(1\) 來表示； 否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 \(\frac n 2\) 的小正方形後，然後表示如下：先寫下 \(2\)，之後依續接上左上、右上、左下、右下四塊的編碼。

如果還是不太清楚的話可以直接進去 ZJ 看題：
https://zerojudge.tw/ShowProblem?problemid=f637

這個題目的解法就是用遞迴，我們可以把影像分成小正方形當作子問題，然後再呼叫遞迴函式解決子問題，在需要時再讓子問題呼叫遞迴函式解決更小的子問題，直到遞迴到最小的子問題，然後再一層一層回傳答案。

根據上面的定義，我們可以得出以下邏輯：

• 當讀入到 \(1\) 時，代表這個小正方形是黑色，直接回傳 \(n \times n\)。
• 當讀入到 \(0\) 時，代表這個小正方形是白色，直接回傳 \(0\)。
• 當讀入到 \(2\) 時，代表這個小正方形不是單色，我們需要再分成四個小正方形，分別呼叫遞迴函式解決子問題，然後再將四個小正方形的答案相加回傳。

就可以寫出以下程式碼，非常的簡潔！

string s;
int idx = 0;

int read(int n) {
    char c = s[idx++];
    if (c == '1') return n * n;
    if (c == '0') return 0;
    return read(n/2) + read(n/2) + read(n/2) + read(n/2);
}

signed main() {
    int n;
    cin >> s >> n;
    cout << read(n) << endl;
}