# AP325 U1 - 遞迴
###### tags: `Algorithms` `C++` `APCS`

[TOC]

---

## 1.1. 基本觀念與用法
### 定義
函式直接或間接的呼叫自己
### 範例
#### 階乘 Factorial

int fac(int n) {
    if (n == 1) return 1;
    return n * fac(n-1);
}

#### 費氏數列 Fibonacci

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

### 缺點
* 效率不佳
* 複雜度指數成長
=> 改善：動態規劃
### 使用時機
* 根據定義實做
* 窮舉暴搜

---

## 1.2. 實作遞迴定義
### [例題 P-1-1 合成函數(1)](https://judge.tcirc.tw/ShowProblem?problemid=d001)
:::spoiler 程式碼

#include <iostream>
using namespace std;

int eval(){
    int x, y;
    string token;
    cin >> token;
    if(token[0] == 'f'){
        x = eval();
        return 2*x - 1;
    } else if(token[0] == 'g'){
        x = eval();
        y = eval();
        return x + 2*y - 3;
    } else {
        return stoi(token);
    }
}

int main(){
    cout << eval();
}

> AC (2ms, 324KB)
:::
### [習題 Q-1-2 合成函數(2)](https://judge.tcirc.tw/ShowProblem?problemid=d002)
:::spoiler 程式碼

#include <iostream>
using namespace std;

int eval(){
    int x, y, z;
    string token;
    cin >> token;
    if(token[0] == 'f'){
        x = eval();
        return 2*x - 3;
    } else if(token[0] == 'g'){
        x = eval();
        y = eval();
        return 2*x + y - 7;
    } else if(token[0] == 'h'){
        x = eval();
        y = eval();
        z = eval();
        return 3*x - 2*y + z;
    } else {
        return stoi(token);
    }
}

int main(){
    cout << eval();
}

> AC (2ms, 324KB)
:::