Swift 实现斐波那契 (Fibonacci) 数列

Fibonacci 数列是一系列数字，除了第一个和第二个数字以外，任何数字都是前两个数字之和：

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

数列中的第一个 Fibonacci 数的值为 0，第四个 Fibonacci 数的值为 2，数列中第 n 个 Fibonacci 数的值可以通过下述公式计算：

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

1.通过递归实现

通过上述公式机械的翻译为 Fibonacci 函数第一版

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

注：如果调用一个值来运行这个函数，则这个函数将会永远不停的运行，不会返回最终结果，我们称这种情况为无穷递归。

2.添加终止条件

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

3.增加缓存，减少计算量

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 数列性能更高的方法，还有老是迭代发。

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 循环的主体最多只需要运行 n-1 次！