# 509 Fibonacci Number (有圖)

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

LeetCode

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) {
    
};

解釋

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 項

每一項都分成 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)
};