###### tags: `ADA 2.2` `Recurrence`

# ADA 2.2 Recurrence

解決問題一定要用Recurrence方式做，遞迴

## Recurrence Relation

* Definition
A recurrence is an equation or inequality that describes a function in
terms of its value on smaller inputs.

等式或是不等式，這個式子不管是等式或不等式，它描述一個function，是根據他比較小的input數值，會寫在func裡面

* Example
Fibonaccisequence(費波那契數列)
**Base case: F(0) = F(1)= 1
**Recursive case: F(n) = F(n-1) +F(n-2)
左邊跟右邊是一樣的func，只是裡面的數值比較小（右邊比左邊小）

**需注意數列上要定義base case，什麼時候要足夠小，將來在Recursive case才知道切到什麼時候停下來**

| ｎ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... |
| ---- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| F(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | ... |

*螺，黃金比例

---

## Recurrent Neural Network (RNN)


AI 類神經網路一個公式

也是一個遞迴相關的公式
St藉由St-1 ，t前一個時間的資訊拿來用，後面的時間會拿來沿用前面的時間資訊

---

## Recurrent Benefits


有效率，較容易思考
比較容易思緒清楚跟簡單
因為只需要定義base case跟recursive case，就等同於定義了一連串的數字


把程式寫進去
**注意：base case一定要定義，否則程式會一直跑

---

## Recurrence v.s. Non-Recurrence


分析：
結構清楚，但是效能不好，會有同一個func被不同的情況call一次


先準備一個表單，a0跟a1先填上，之後迴圈將數值填入，達到一樣的效果

分析：
因為從前面往後填，不會有上述重複扣的情況，雖然結構可能沒有上面的明確，但效能比較好

---


原則上能定義base case跟recursive case就可以去解決剛剛的問題

但不是所有問題都容易被解決，需要思考什麼是何用Recurrence去解決

舉例：河內塔
當盤子數量很多時，會很難去思考
但當盤子數量很少的時候，比較簡單，就容易定義出base case
就可以把大問題切成小問題，慢慢的去解決

如果n很小還是找不到，就不適合

---