首頁 教學 演算法

# 前言

上一章介紹了工具箱，這一章開始講真正的演算法思維，而遞迴是所有後續章節的共同基礎 —— 分治、動態規劃、DFS、樹上演算法，骨架全都是遞迴。

# 什麼是遞迴

遞迴是指一個函式在其定義中呼叫自身的過程。在寫程式中，遞迴是一種解決問題的方法，其中函式通過反覆呼叫自身來解決更小規模的子問題，直到達到終止條件，從而得到最終的結果。

遞迴通常包含兩個部分：

  1. 終止條件（base case）：問題規模小到可以直接回答時就停下來
  2. 遞迴情況（recursive case）：把問題分解為更小規模的子問題，並透過遞迴呼叫來解決

遞迴在許多演算法和資料結構中被廣泛應用，例如樹和圖的遍歷、分治演算法、動態規劃等。使用遞迴可以簡化問題的表達和思考，但需要注意遞迴的終止條件和遞迴呼叫的合理性，以避免出現無限遞迴或效率低下的情況。

# 從費氏數列理解

舉個簡單的費氏數列當例子：設定 f (0) 為 0，f (1) 為 1，要求 f (4) 為多少，費氏數列的定義是 f(n) = f(n-1) + f(n-2) 。

一開始要求 f (4)，所以往下遞迴 f (3) 跟 f (2)，因為都還沒達到終止條件所以繼續往下遞迴，直到達到終止條件就會回傳。當 f (3) 的兩邊 f (1) 跟 f (2) 都回傳過來之後就加起來，然後回傳計算好的值 —— 這樣就是遞迴概念。

int f(int n)
{
    if( n == 0 ) return 0;
    if( n == 1 ) return 1;
    return f(n-1) + f(n-2);
}
畫成遞迴樹會長這樣：


                    f(4)
                  /      \
              f(3)        f(2)
             /    \      /    \
         f(2)     f(1) f(1)   f(0)
        /    \
     f(1)   f(0)



從圖中可以看到同個函式被呼叫不只一次，同個值像是 f (2) 被計算不只一次。減少重複的計算就是演算法重要的一個課題，現在不需要知道該怎麼解決，只要了解遞迴的概念就好，後面提到動態規劃時就會知道了。


這裡先預告一下解法：只要把算過的答案存起來，下次遇到直接拿出來用，時間複雜度就會從指數級的  O(2^n)  掉回乾淨的  O(n) 。這個技巧叫做 memoization（記憶化），也就是 top-down 形式的動態規劃，我們在 1-8 動態規劃 會詳談。


# 遞迴的成本：呼叫堆疊


遞迴不是免費的。每一次函式呼叫，系統都會在 ** 呼叫堆疊（call stack）** 上配置一塊空間，存放參數、區域變數與返回位址。所以：


    

  • 空間複雜度至少是  O(遞迴深度) ，即使你沒有開任何陣列
    • 

  • 遞迴太深會堆疊溢位（stack overflow），程式直接崩潰
    • 



一般競賽環境的堆疊大約幾 MB，能容納的遞迴深度大約在  10^5  到  10^6  這個量級（取決於每層用了多少變數）。所以看到 n 到  10^6  而且需要深度遞迴時，就要考慮改寫成迭代或用自己的 stack 模擬。


另外要注意參數傳遞的成本：如果你在遞迴函式裡用 pass by value 傳一個很大的 vector 或 string，每一層都會複製一份，常數會爆炸。這種時候一定要用傳參考：


void dfs(vector<int> v);         // 慢：每層都複製整個 vector
void dfs(vector<int>& v);        // 快：傳參考，不複製
void dfs(const vector<int>& v);  // 更好：傳唯讀參考，避免不小心改到
如果不想傳參數，也可以把資料開成全域變數 —— 這是競賽常見的寫法，我自己的程式碼大多都是這樣寫。


# 寫遞迴的三個檢查點


寫遞迴時如果卡住，照這三點檢查通常能找到問題：


    

  1. 終止條件設對了嗎？ 沒有終止條件或條件錯誤，都會導致無窮遞迴，最後記憶體用盡當機。
    2. 

  2. 每次遞迴都有讓問題「變小」嗎？ 如果遞迴呼叫的參數沒有朝終止條件靠近，一樣會無限跑下去。
    3. 

  3. 回傳值處理對了嗎？ 特別是有多個遞迴分支時，要確認是取 max、取 min、還是相加。
    4. 





# 例題一：合成函數 (2)（APCS）




題目來源：APCS 201902 ｜ AP325 Q-1-2




令 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。


輸入格式：輸入一行，長度不超過 1000，它是一個 f, g, 與 h 的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過 1000。


輸出：輸出函數值。最後答案與運算過程不會超過正負 10 億的區間。






範例輸入
範例輸出






h f 5 g 3 4 3
18






# 解題思路


這一題的重點在於把  cin  放在函式裡面讓程式進行遞迴，在剛開始接觸可能會比較難想到這個方法。


觀察輸入格式： h f 5 g 3 4 3 。因為括號和逗號都被換成空白了，看起來像是一串扁平的符號，但它其實仍然帶有完整的樹狀結構：


        h
      / | \
     f  g  3
     |  |\
     5  3 4



關鍵的觀察是：每個函式需要幾個參數是固定的（f 要 1 個、g 要 2 個、h 要 3 個）。所以只要按順序讀，讀到  h  就知道「接下來要遞迴取得 3 個值」，讀到  f  就知道「接下來要遞迴取得 1 個值」，讀到數字就直接回傳。


這樣一來，輸入的讀取順序剛好就是前序走訪（preorder）的順序，遞迴會自動把結構還原出來，完全不需要真的建一棵樹。


int eval(){
    char a[3];
    int x, y, z;
    cin >> a;
    if (a[0] == 'f'){
        x = eval();
        return (2 * x - 3);
    }else if (a[0] == 'g'){
        x = eval();
        y = eval();
        return (2 * x + y - 7);
    }else if (a[0] == 'h'){
        x = eval();
        y = eval();
        z = eval();
        return (3 * x - 2 * y + z);
    }else
        return atoi(a);
}
int main(){
    cout << eval();
    return 0;
}
觀察程式碼的最後一個  else  就是終止條件 —— 讀到的不是 f/g/h，那就是數字，直接用  atoi  轉成整數回傳，不再往下遞迴。


有一個細節值得注意： x = eval(); y = eval();  必須分兩行寫，不能寫成  return (2 * eval() + eval() - 7); 。因為 C++ 並不保證同一個運算式中多個函式呼叫的求值順序，可能先算右邊那個  eval() ，這樣讀入的順序就錯了。這種「有副作用（會讀輸入）的函式」一定要拆開寫，明確指定順序。


時間複雜度是  O(L) ，L 是輸入長度，因為每個符號只會被讀取一次。




# 例題二：支點切割（APCS）




題目來源：APCS 201802 ｜ AP325 Q-1-4




輸入一個大小為 N 的一維整數陣列 p []，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於 3 或切到給定的層級 K 就不再切割。


而所謂最佳切點的要求是讓左右各點數字與切點距離的乘積總和差盡可能的小，也就是說，若區段的範圍是 [s,t]，則要找出切點 m∈[s+1,t-1]，使得 |Σt i=s p [i]×(i-m)| 越小越好，如果有兩個最佳切點，則選擇編號較小的。


輸入說明：第一行有兩個正整數 N 與 K。第二行有 N 個正整數，代表陣列內容 p [1] ~ p [N]，數字間以空白隔開，總和不超過 10^9，N≤50000，切割層級限制 K<30。


輸出說明：所有切點的 p [] 值總和。






範例一輸入
範例一輸出






7 3
2 4 1 3 7 6 9		
1




範例二輸入
範例二輸出




5 1
1 2 3 4 100		
4






# 解題思路


這題雖然有一些數學符號可是並不用想的那麼難。觀察一下題目，想像一根棍子依照題目的要求去切棍子，題目的意思其實就是在找這個棍子的重心 —— 一根棍子每個部份的重量都不一樣，要找到最接近重心的位置讓兩邊的重量差盡量到最小。


找到切點後，就對左右兩半分別做同樣的事，這就是遞迴。終止條件有兩個：切到第 K 層，或區間小到不能再切。


#include<bits/stdc++.h>
using namespace std;
#define  N 50005
typedef long long LL;
LL a[N],K,lps[N],rps[N];//ps:prefix sum
int cut(int l,int r,int k){
    if(k>K || r-l<2)
        return 0;
    LL buffer=0;
    lps[l]=0;rps[r]=0;
    for(int i=l+1;i<r;i++){// 從左邊開始的前綴和
        buffer+=a[i-1];
        lps[i]=lps[i-1]+buffer;
    }
    buffer=0;
    for(int i=r-1;i>l;i--){// 從右邊開始的前綴和
        buffer+=a[i+1];
        rps[i]=rps[i+1]+buffer;
    }
    buffer=10e8+1;
    int c;
    for(int i=r-1;i>l;i--){
        LL sum;
        sum=abs(lps[i]-rps[i]);
        if(sum<=buffer){
            buffer=sum;
            c=i;
        }
    }// 兩邊各自遞迴出答案並加上現在的答案
    return a[c]+cut(l,c-1,k+1)+cut(c+1,r,k+1);
}
int main(){
    int n;
    cin>>n>>K;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<cut(0,n-1,1);
    return 0;
}
程式裡用到了前綴和的概念來快速計算力矩總和。這個技巧非常重要，下一章 1-3 搜尋技巧 會完整介紹，這裡先簡單說明它在這題的作用。


lps[i]  累積的是「從左邊到 i 為止的力矩」， rps[i]  是「從右邊到 i 為止的力矩」。有了這兩個陣列，判斷任何一個候選切點的好壞就只要  O(1)  —— 直接看  abs(lps[i] - rps[i])  就好，不用每次都重新掃一遍整個區間。


注意最後  return a[c] + cut(左半) + cut(右半)  這一行，就是遞迴的合併步驟：當前這一刀的貢獻，加上左右兩邊各自遞迴出來的答案。


還有一個細節： if(sum<=buffer)  用的是小於等於，配合迴圈由右往左跑，這樣遇到相同的最小值時最後留下的會是編號較小的那個，符合題目「如果有兩個最佳切點，則選擇編號較小的」的要求。這種細節看錯就會 WA。


複雜度：每一層要掃過所有元素算前綴和，共 K 層，所以是  O(NK) 。K<30，N≤50000，總共約  1.5×10^6 ，很安全。




# 例題三：DF-expression（APCS）




題目來源：APCS 201810 ｜ AP325 Q-1-5




假設 n 是 2 的冪次，也就是存在某個非負整數 k 使得 n=2^k。將一個 n×n 的黑白影像以下列遞迴方式編碼：


    

  • 如果每一格像素都是白色，我們用 0 來表示
    • 

  • 如果每一格像素都是黑色，我們用 1 來表示
    • 

  • 否則，並非每一格像素都同色，先將影像均開等劃分為四個邊長為 n/2 的小正方形後，然後表示如下：先寫下 2，之後依續接上左上、右上、左下、右下四塊的編碼
    • 



輸入編碼字串 S 以及影像尺寸 n，請計算原始影像中有多少個像素是 1。


輸入說明：第一行是影像的編碼 S，字串長度小於 10^6。第二行為正整數 n，1≤n≤1024，其中 n 必為 2 的冪次。






範例輸入
範例輸出






2020020100010
8		
17






# 解題思路


這題的編碼方式本身就是遞迴定義的，所以解法自然也是遞迴。這是遞迴題很典型的特徵：題目怎麼定義，程式就怎麼寫。


三種情況剛好對應遞迴的三個分支：


    

  • 讀到  0 ：整塊全白，回傳 0（終止條件）
    • 

  • 讀到  1 ：整塊全黑，回傳這塊的面積  n×n （終止條件）
    • 

  • 讀到  2 ：要往下切成四塊，邊長減半，遞迴四次後把結果加總
    • 



#include <bits/stdc++.h>
using namespace std;
string s;
int n,d;
int dfs(int _n){
    if(s[d]=='0') return 0;// 終止條件
    if(s[d]=='1') return _n*_n;
    _n/=2;
    int temp=0;
    for(int i=0;i<4;i++){
        d++;
        temp+=dfs(_n);// 進入遞迴
    }
    return temp;
}
int main(){
    cin>>s>>n;
    cout<<dfs(n);
}
這裡用了一個全域變數  d  當作「目前讀到字串的第幾個字元」的指標。因為字串的讀取順序就是遞迴的走訪順序，用一個全域指標往前推進，比把位置當參數傳來傳去更簡潔。


要注意  d++  的位置在  dfs(_n)  之前，因為進入子區塊前要先把指標移到下一個字元。這種指標推進的時機非常容易寫錯，建議拿範例輸入手動跑一遍確認。


另外， _n*_n  在 n 最大 1024 時是  10^6 ，還在 int 範圍內，不會溢位。但如果題目把 n 放大，這裡就要改成  long long 。


複雜度是  O(|S|) ，字串每個字元只會被處理一次。




# 例題四：先加後乘與函數（APCS）




題目來源：APCS




給一個運算式，運算式的內容由數字、+、* 和某個函式 f () 所組成，除了函式 f () 以外不會有額外的括號。請將此運算式依照先加後乘的方式運算。


函式 f (X1,X2,X3,X4,...) 定義為從這個不定長度的參數 X1,X2,X3,X4,... 中的最大值扣掉最小值。例如 f (3,6,2)=6-2=4、f (3)=0。


輸入說明：輸入一個運算式，保證長度不超過 500，出現在運算式內的數字介於 0 到 200 之間，除了函式 f () 之外不會出現多餘的括號，並且運算式一定合法。


    

  • (30 分)：運算式只包含數字、+ 和 *
    • 

  • (70 分)：無其他限制
    • 



輸出說明：輸出運算式的計算結果，此題運算過程和答案可能超過 2^31 但不超過 10^17。






範例輸入
範例輸出






2+3*1+2+1
20




12+f(13,2+f(8,1+23),1+1f(20,4)*f(2))*2
50




f(0)
0






# 解題思路


這一題我覺得要注意的地方蠻多的，第一次寫時候很難寫的簡潔，對於定義每個函式該做的事情很有需要思考。沒做過類似的題目一定會覺得困難，建議先嘗試寫出第一個子題組，然後再想要從哪裡更動增加新功能，讓整個題目都能得分。這一題的細節要看有沒有 +1，要看清楚注意迴圈跑到了哪裡。


這題的難點在於它是互相遞迴（mutual recursion）：計算運算式時可能遇到  f(...) ，而  f  的參數裡面又是運算式。所以兩個函式會互相呼叫：


    

  • expre(idx) ：從位置 idx 開始解析一個運算式，回傳
    • 

  • f(idx) ：從位置 idx 開始解析一個 f 函式呼叫，回傳
    • 



因為 C++ 要求使用前先宣告，所以要先寫一行  pair<int,int> f(int idx);  的前置宣告，才能在  expre  裡呼叫它。


至於「先加後乘」怎麼處理：正常的運算優先序是先乘後加，這題反過來，所以用一個 stack —— 遇到  +  就把結果跟堆疊頂端相加後放回去，遇到  *  就先把兩個數存著，等到最後再一次乘起來。


#include <bits/stdc++.h>
using namespace std;
#define int long long
string s;
pair<int,int> f(int idx);// 宣告
pair<int,int> expre(int idx){//Expression 計算
    stack<int> stk;
    string op="#";//operators
    while(idx<(int)s.size() && !(s[idx]==',' || s[idx]==')')){
        int temp=0;
        if(s[idx]=='+' || s[idx]=='*'){
            op=s[idx++];
            continue;
        }else if(s[idx]=='f'){
            pair<int,int> buffer=f(idx+2);//+2 後會是數字
            idx=buffer.first;
            temp=buffer.second;
        }else{
            while(s[idx]>=48 && s[idx]<=57){
                temp*=10;
                temp+=(s[idx++]-48);
            }
        }
        if(op=="+"){//op[0]=='+'
            temp+=stk.top();
            stk.pop();
            stk.push(temp);
        }else if(op[0]=='*' && stk.size()>=2){
            int ta=stk.top();stk.pop();
            ta*=stk.top();stk.pop();
            stk.push(ta);
            stk.push(temp);
        }else
            stk.push(temp);
    }
    if(stk.size()>=2){
        int ta=stk.top();stk.pop();
        ta*=stk.top();stk.pop();
        stk.push(ta);
    }
    return {idx,stk.top()};
}
pair<int,int> f(int idx){// 計算 f 函式
    pair<int,int> temp=expre(idx);
    int mx,mn=temp.second;
    mx=mn;
    idx=temp.first;
    while(s[idx++] != ')'){// 注意這裡的 idx++
        temp=expre(idx);
        idx=temp.first;
        mx=max(mx,temp.second);
        mn=min(mn,temp.second);
    }
    return {idx,(mx-mn)};
}
signed main(){
    cin>>s;
    cout<<expre(0).second;
}
幾個實作重點：


回傳 pair 來傳遞位置。 因為每個子運算式解析完之後，主流程需要知道「讀到哪裡了」，所以回傳值同時帶著結束位置和計算結果。這是處理這類解析問題的通用手法。


 #define int long long  搭配  signed main() 。 題目說答案可能超過 2^31，所以用巨集把所有 int 都換成 long long。但  main  的回傳型別不能被換掉，所以要寫成  signed main() （ signed  就是  signed int  的簡寫，這裡因為巨集的關係不能直接寫 int）。這是競賽常見的偷懶寫法。


 while(s[idx++] != ')')  裡的  idx++ 。 這個後置遞增在判斷完之後才會生效，剛好跳過逗號進到下一個參數。這種寫法很精簡但也很容易看錯，寫的時候要特別想清楚。


複雜度是  O(L) ，L 是運算式長度，每個字元只處理一次。




# 小結


這章的核心觀念：


    

  • 遞迴 = 終止條件 + 問題變小的遞迴呼叫，兩者缺一不可
    • 

  • 遞迴的空間成本是  O(深度) ，太深會 stack overflow
    • 

  • 傳遞大型資料時要用參考，否則常數會爆炸
    • 

  • 遞迴會產生重複計算（費氏數列就是典型），解法是記憶化，也就是 DP
    • 

  • 讀取輸入的順序若與遞迴走訪順序一致，可以不建樹直接遞迴（合成函數、DF-expression 都是這個手法）
    • 



觀察這四題會發現一個共同模式：題目本身的定義是遞迴的，程式就照著定義寫。這是遞迴題最重要的直覺 —— 不要想著怎麼「展開」，而是相信「更小的子問題已經被解決了」，只要處理好合併的那一步就行。


下一章講搜尋技巧，包含前綴和、雙指針、滑動視窗與二分搜。這些是把暴力解優化成可通過解的關鍵武器，也是 APCS 最常考的技巧。


# 練習題


（之後補上）


      

          
          
          
          
      

  


   


    

  
    
      
    
    更新於
    
  
  
      
        
      
      閱讀次數
      
      次