Fibonacci 數(shù)列是一系列數(shù)字，除了第一個(gè)和第二個(gè)數(shù)字以外，任何數(shù)字都是前兩個(gè)數(shù)字之和：

0、1、1、2、3、5、8、13、21、……

數(shù)列中的第一個(gè) Fibonacci 數(shù)的值為 0，第四個(gè) Fibonacci 數(shù)的值為 2，數(shù)列中第 n 個(gè) Fibonacci 數(shù)的值可以通過下述公式計(jì)算：

fib(n) = fib(n - 1) + fib(n - 2)

1.通過遞歸實(shí)現(xiàn)

通過上述公式機(jī)械的翻譯為 Fibonacci 函數(shù)第一版

func fib(n:UInt) -> UInt {
    return fib1(n: n-1) + fib1(n: n-2)
}

注：如果調(diào)用一個(gè)值來運(yùn)行這個(gè)函數(shù)，則這個(gè)函數(shù)將會永遠(yuǎn)不停的運(yùn)行，不會返回最終結(jié)果，我們稱這種情況為無窮遞歸。

2.添加終止條件

func fib(n:UInt) -> UInt {
    if n < 2 {
        return n
    }
    return fib2(n: n - 1) + fib2(n: n - 2)
}

3.增加緩存，減少計(jì)算量

var fibMemo : [UInt : UInt] = [0:0, 1:1]
func fib(n:UInt) -> UInt {
    if let result = fibMemo[n] {
        return result
    } else {
        fibMemo[n] = fib3(n: n - 1) + fib3(n: n - 2)
    }
    return fibMemo[n]!
}

4.保持 Fibonacci 簡單

解決 Fibonacci 數(shù)列性能更高的方法，還有老是迭代發(fā)。

func fib(n: UInt) -> UInt {
    if n == 0 {
        return n
    }
    
    var last :UInt = 0, next :UInt = 1
    for _ in 1..<n {
        (last, next) = (next, next + last)
     }
    return next
}

通過這種方法，for 循環(huán)的主體最多只需要運(yùn)行 n-1 次！