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 次！
