最后3个数字的Fibbonaci样序列

Question

是否存在非递归方式,我可以通过添加最后3个数字来制作"斐波那契"序列？

这是我尝试这样做的递归方式.

def fib3(n):
    if n < 3:
        return 1
    else:
        return fib3(n-1) + fib3(n-2) + fib3(n-3)

回报 1+1+1+3+5+9+17...+(n-1) + (n-2) + (n-3)

任何帮助将不胜感激.

提前致谢

Answer 1

是的,非常优雅,具有Python的多重赋值功能:

>>> def fib3(n):
...     if n < 3:
...         return 1
...     a = b = c = 1
...     for i in range(3, n):
...         # We "shift" a, b, and c to the next values of the sequence.
...         a, b, c = b, c, (a + b + c)
...     return c
...
>>> fib3(4)
3
>>> fib3(5)
5
>>> fib3(6)
9
>>> fib3(7)
17

并且迭代方法肯定比递归方法更受欢迎 - 正如@mu写的那样,递归实现的运行时间大约是O(3 ^ n),而这个方法是O(n).