> For the complete documentation index, see [llms.txt](https://hannahpun.gitbook.io/leetcode-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hannahpun.gitbook.io/leetcode-note/dynamic-programing/509-fibonacci-number.md).

# # 509 Fibonacci Number (有圖)

最基本的 Recursion 範例，一定要記清楚

[LeetCode](https://leetcode.com/problems/fibonacci-number/)

```
The Fibonacci numbers, commonly denoted F(n) form a sequence, 
called the Fibonacci sequence, such that each number is the sum of the two preceding ones, 
starting from 0 and 1. That is,

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

寫出 Fibonacci sequence
```

```
Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    
};
```

### 解釋

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrA5ypHyWHpL3PQ03EV%2F-LrAHjQJ2xm_8jBdF41Y%2Ff1.jpg?alt=media\&token=e68a24cf-f28e-4cb5-b721-de1b98b25969)

```
F(0) : 0
F(1) : 1
F(2) : 1
F(6) : 8
```

每個數字都是前兩個的總和, 0 + 1 = 1, 1+1 = 2, 2+1 = 3 以此類推

* 第 0 項 F(0) = 0
* 第 1 項 F(1) = 1
* 第 n 項 F(n ) = f( n-1 ) + f( n-2 ) // 第 n-1 項 + 第 n-2 項

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrA5ypHyWHpL3PQ03EV%2F-LrAHud8EIflK3VgKyW1%2Ff2.jpg?alt=media\&token=adf2b445-15c2-4fa5-aa74-a167afda5c56)

![](https://1787585077-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LqirD3iAZIDk4oDCfwS%2F-LrA5ypHyWHpL3PQ03EV%2F-LrAI-JjAtsb9_MwmUwA%2Ff3.jpg?alt=media\&token=a0fe640a-13e2-46fa-b58d-ddf1ef68c04e)

每一項都分成 f(n-1) + f(n-2) 一直拆到 f(1) = 1, f(0) =0 為止, 然後再把它全部加起來 (黃色數字) 就等於 5，而總共要執行 15 次這個函式

### Code

```
var fib = function(N) {
	if(num == 0){
		return 0;
	}else if(num == 1){
		return 1;
	}else{
		return F(num - 1) + F(num - 2)
	}
}
fib(5); // 5
```

### 改善

優化，把算過的儲存進 cache

```
let cacheSet = new Map();
 // basic
var fib = function(N) {
    if(cacheSet.has(N)){
        return cacheSet.get(N)
    }
    if(N==0){
        cacheSet.set(N, 0)
    }else if(N==1){
        cacheSet.set(N, 1)
    }else{
        cacheSet.set(N, fib(N - 1) + fib(N - 2))
    }
    return cacheSet.get(N)
};

```