題目連結: https://leetcode.com/problems/fibonacci-number/

練習提問:

Q: n的range? Ans: 0 ~ 30

Note: 假設Int是64 bits,則fib(93)會大於Int64.max
Note: 假設Int是32 bits,則fib(47)會大於Int32.max

法ㄧ(Recursive version):

    func fib(_ n: Int) -> Int {
        if n == 0 { return 0 }
        else if n == 1 { return 1 }
        else {
            return fib(n-1) + fib(n-2)
        }
    }

法二(Iterative version):

    func fib(_ n: Int) -> Int {
        if n == 0 { return 0 }
        else if n == 1 { return 1 }
        else {
            var arr = Array(repeating: 0, count: n + 1)
            arr[1] = 1
            for i in 2 ... n {
                arr[i] = arr[i-1] + arr[i-2]
            }
            return arr[n]
        }
    }