定义
- 斐波那契数列是一系列数字，除了第一个和第二个数字之外，任何数字都是前两个数字之和：
0、1、1、2、3、5、8、13、21...... - 数列中的第一个斐波那契数的值为0，第四个斐波那契数为2，第n个斐波那契数的值可以通过下述公式计算：
fib(n) = fib(n-1) + fib(n-2)
迭代计算
/*
* prev与curr分别代表f(n-1)和f(n)
* 计算prev+curr赋值给curr，curr赋值给prev，经过n次赋值后可以算出结果
*/
func fib(_ n: UInt) -> UInt {
var (prev, curr) = (0, 1)
for _ in 0..<n {
(curr, prev) = (curr + prev, curr)
}
return curr
}
这个算法是解决斐波那契数列问题的最优算法，计算出fib(n)只需要n-1次循环即可.
尝试使用递归
在这个算法中，需要注意的是要注意fib方法的边界值，即做好终止点的计算
/*
* 斐波那契数列的数字都是基于fib(0)和fib(1)计算出来的，所以在递归方法里面，只要计算出fib(0)和fib(1)，其他情况调用递归即可。
*/
func fib(_ n: UInt) -> UInt {
if n < 2 {
return n
}
return fib(n-1) + fib(n-2)
}
递归优化
在斐波那契数列的递归计算中，因为所有的斐波那契数都是通过对其前两个数计算出来的，所以递归算法中，fib(n)的调用次数是与n相关的指数增长，在fib(20)的时候，就调用了21891次。基于这个情况，可以对递归算法进行缓存，即每调用计算出一个数，就缓存到cache中，这样可以有效避免指数级的调用，这是典型的用空间换时间的做法。
/*
* 在优化算法里，将fib(0)、fib(1)两个斐波那契数作为初始值放到cache里，可以减少两次调用，并且在递归算法中，不用再额外计算这两个数
* 判断如果数组中没有fib(n)的结果，就用递归算法去计算fib(n)，放到数组里面，并返回数组的值
*/
var fibCache: [UInt: UInt] = [0: 0, 1: 1]
func fib(_ n: UInt) -> UInt {
if fibCache[n] == nil {
fibCache[n] = fibCache[n-1] + fibCache[n-2]
}
return fibCache[n]!
}
在这个算法中，计算出fib(n)需要2n-1次递归计算，相对于第一个迭代算法来说，还是稍微复杂一点。
其他注意点
计算斐波那契数列，其他需要注意的情况就是注意负值和溢出的情况，上述算法中，fib函数中的参数n的类型是UInt非负整数，这样避免了负值情况。而溢出情况本文不做赘述。
