费波那契数列由0和1开始，之后的数就由之前的两数相加 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,……….

用递归算法来求值,非常好理解.伪代码:

实现:

功能实现了,但是代码比较冗长,函数是要对前两项做特殊判断.现在优化一下,如何才能更通用,即使是第0个和第1个也能运用到for循环呢?假设在 0, 1, 1, 2, 3, 5, 8, 13... 之前还有两项, 是-1和1, 即: -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,这样就通用了:

现在评估一下他们的性能: 写一个性能装饰器.

他不能用在递归方法中. 所以最终还是写了这么个方法:

看出性能对比了吧:

所以用递归弊端还是不少