---
# System prepended metadata

title: 第五章、遞迴
tags: [C++, APCS]

---

# 基本觀念
遞迴同數學的遞迴，都需要找到關係式，並且每個在範圍內的正整數都必須要對應一個值。

以費式數列為例，一個費式數列如下
$[1,1,2,3,5,8,……,F(n-1)+F(n-2)]$
我們可以定義一個關係式
$$
F[n]=\begin{cases}
F[0]=F[1]=1
\\[2ex]
F[n]=F[n-1]+F[n-2]
\end{cases}
$$
# 用法
## 範例程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
int h;
int f(int x)
{
    if(x>10)
        return x;
    else
        return f(x+1);
}
void d(int x,int y)
{
    if(x>y)
    {
        h++;
        return;
    }
    return;
}
void g()
{
    if(h>0)
    {
        h--;
        return;
    }
    return;
}
int main() {
    int a=10,b=50,c=10;
    h=0;
    cout<<f(a)<<endl;
    d(b,a);
    cout<<h<<endl;
    g();
    cout<<h<<endl;
    return 0;
}
```
## 解析
### f
以第4行為例
```cpp=
int f(int x)
```
:::info
前面的 **"int"** 表示 **"回傳"** 東西的型態
中間的 **"f"** 表示這個函式稱為 **"f"**
後面的 **"int x"** 表示這個函式需要 **"輸入"** 的一個值
:::
4到10行可以視為是一整個區塊
```cpp=
int f(int x)
{
    if(x>10)
        return x;
    else
        return f(x+1);
}
```
整個區塊的流程為
:::warning
$1. 輸入一個x$
$2. 如果x大於10 回傳x$
$3. 否則x+1直到x>10$
:::
### d
```cpp=
void d(int x,int y)
{
    if(x>y)
    {
        h++;
        return;
    }
    return;
}
```
以這個區塊來看
:::success
**型態=>void
名字=>d
輸入=>x,y**
:::

這裡有兩個重點
:::info
**void**
```
void(N.) 空洞；空間；空白(From Cambridge)
```
而這裡void便是表示回傳值為空，也就是**沒有**回傳值。
:::
:::info
**兩個輸入值**

對，兩個輸入就是得這樣，沒有為什麼。
:::

### g
```cpp=
void g()
{
    if(h>0)
    {
        h--;
        return;
    }
    return;
}
```
以這個區塊來看
:::success
**型態=>void
名字=>g
輸入=>???**
:::
事實上，這裡**不須要**任何輸入，直接呼叫即可。

### 變數
首先，每個區塊裡的變數都**不會**共用，所以f裡面的x跟d裡面的x是**不同的**x。
假使你需要一個每個區塊都可以使用的變數，在這個程式中就是h，你只需要宣告在所有程式碼區塊前即可。

## 流程
首先，程式碼必然是先從main開始，**一個程式只能有一個main**，這是規則，~~不能打破(梗)~~。
```cpp=
int main() {
    int a=10,b=50,c=10;
    h=0;
    cout<<f(a)<<endl;
    d(b,a);
    cout<<h<<endl;
    g();
    cout<<h<<endl;
    return 0;
}
```
假如是有回傳值的函數，例如f，可以指定給變數或是直接輸出，假如是無回傳值的函數，例如d,g，則**不可**指定給變數或是直接輸出，因為沒有回傳值。
(呼叫方法即為程式碼內容)

# 總結

遞迴在使用時複雜度是呈現指數型上升的，在未來，我們會利用動態規劃來優化這部分的複雜度，費式數列或階層的運算會有更好的解法。


