# 遞迴(Recrusion)

## 前提

在講解函式時，有先提及過遞迴的概念
那這次主要以遞迴的實際運用為主軸

## 遞迴介紹 📖

將一個問題猜成許多相同方式的小問題
可以讓程式碼的可讀性大幅增加

介紹可能還是一頭霧水那直接實際演練遞迴
如果我們今天想做一個從 1 一直加到 x
除了 for 迴圈，就可以用上遞迴的概念

## 示範Code👉

計算 1 一直加到 10

#include <stdio.h>
int sumsum(int, int);
int main()
{
    int a = 1, b = 10;
    printf("%d\n", sumsum(a, b));
    return 0;
}
int sumsum(int n, int times)
{
    if (times == 0)
        return 1;
    return times + sumsum(n, times - 1);
}

## 基本遞迴題目(費氏數列)
相信程式寫久的人，對於費氏數列已經有很深的理解了
## 示範Code👉

#include <stdio.h>
int fibonacci(int i)
{
    if (i == 0)
    {
        return 0;
    }
    if (i == 1)
    {
        return 1;
    }
    if (i >= 2)
    {
        return fibonacci(i - 2) + fibonacci(i - 1);
    }
}

int main()
{
    int x;
    scanf("%d", &x);
    for (int i = 0; i <= x; i++)
    {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

# 進階遞迴 (遞迴與動態規劃的搭配)

## 動態規劃介紹 📖

Dynamic Programing 動態規劃(簡稱 DP )，跟遞迴有點類似，不過在進行 n 的運算時，
我們會將 n 資料存起來，之後的運算碰到 n 時，可以重複利用，就不用在運算一次。
運用電腦的空間去換取運算的時間

## 示範Code👉

計算費波那契數字時，如果用一般的遞迴，會發現很快
電腦就需要大量時間計算。因此以下為**遞迴**跟**動態規劃**
的示範

#include <stdio.h>
long long dp[1000] = {0};
long long dp_fib(int n)
{
    if (n == 0 || n == 1)
        return 1;
    dp[0] = 1;
    dp[1] = 1;
    for (long long i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
long long recru_fib(int n)
{
    if (n == 0 || n == 1)
        return 1;
    return (recru_fib(n - 1) + recru_fib(n - 2));
}
int main()
{
    long long n;
    scanf("%lld", &n);
    printf("%lld\n", dp_fib(n));
    printf("%lld\n", recru_fib(n));
    return 0;
}

## 上課練習
[OJ題目](https://hackmd.io/@FCU1B112/HyPAzRTHT)

## 參考
[遞迴](https://medium.com/appworks-school/%E9%80%B2%E5%85%A5%E9%81%9E%E8%BF%B4-recursion-%E7%9A%84%E4%B8%96%E7%95%8C-%E4%B8%80-59fa4b394ef6)
[DP動態規劃](https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-dynamic-programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83-de980ca4a2d3)