###### tags: `FoShiShi`

# 遞迴

## What

就跟數學中的[遞迴](https://zh.m.wikipedia.org/zh-tw/%E9%81%9E%E8%BF%B4%E9%97%9C%E4%BF%82%E5%BC%8F)一樣
只是用程式做出來

**遞迴(recursion)** 的函式包含以下兩種性質

1. **該函式包含自己**：會在函式中呼叫自己，並**一直步步接近終止條件**
2. **該函式有一定的終止條件**：呼叫函式的**最後會終止**(**不然他就會無限的跑下去**然後爛掉)

### 例：費氏數列(Fibonacci Sequence)

費氏數列的性質如下

$\large{Fib(n) = \begin{cases} 1 \qquad \qquad \qquad \qquad \qquad if\ \ n=1 \\ 1 \qquad \qquad \qquad \qquad \qquad if\ \ n=2 \\ Fib(n-1)+Fib(n-2) \qquad else \\ \end{cases}}$

1. **該函式包含自己**：在`else`的時候會呼叫自己兩次
2. **該函式有一定的終止條件**：在`n = 1 or n = 2`時會終止並回傳`1`

可以想像成一個**樹狀圖**(以求$Fib(4)$為例)


## When

當我們問題**本身的答案需要他子問題的答案**來得知的時候
例：費氏數列(數列中前兩項相加)、階乘(`n! = n * (n - 1)! and 1! = 1`)

## How

這裡先用**階乘**的實作來做說明

首先我們需要一個**有引入值的函式**

int f(int x) {
    ;
}

再來宣告**終止條件**

int f(int x) {
    if(x == 1) {
        return 1;
    }
}

然後讓遞迴式**包含自己**並使其**趨近終止條件**

int f(int x) {
    if(x == 1) {
        return 1;
    }
    else {
        return x * f(x - 1);
    }
}

以上就是**階乘**的遞迴式

之後就可以在主函式呼叫這個遞迴式

#include<iostream>
using namespace std;

int f(int x) {
    if(x == 1) {
        return 1;
    }
    else {
        return x * f(x - 1);
    }
}

int main() {
    cout << f(1) << endl; // 1
    cout << f(5) << endl; // 120
}

補充：費氏數列數列遞迴式

int fib(int x) {
    if(x == 1 || x == 2) {
        return 1;
    }
    else {
        return fib(x - 1) + fib(x - 2);
    }
}

## 實際應用

### 題目1

建構一個遞迴函式
符合此遞迴式：

$\large{Fib(n) = \begin{cases} 1 \qquad \qquad \qquad \qquad \qquad if\ \ n=1 \\ 2 \qquad \qquad \qquad \qquad \qquad if\ \ n=2 \\ 3 \qquad \qquad \qquad \qquad \qquad if\ \ n=3 \\ Fib(n-1)+Fib(n-2)*Fib(n-3) \qquad else \\ \end{cases}}$

:::spoiler solution

照著上述遞迴式
設定終止條件與包含自己

#include<iostream>
using namespace std;

int Fib(int n) {
    if(n == 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    if(n == 3) {
        return 3;
    }
    else {
        return Fib(n - 1) + Fib(n - 2) * Fib(n - 3);
    }
}

int main() {
    ...
}

:::