LeetCode 509： 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) = 1F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

Example：

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

題法：
這題是要算Fibonacci數列
由上面公式可以看出，算到0跟1才會有值
不然就減1繼續算f(n)
這個可以用遞迴算
因為每一次的疊代計算都是一樣的

程式碼：

func fib(N int) int {
    if N == 0 || N ==1 {
        return N
    }
        
    return fib(N-1) + fib(N-2)
}