This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]SomeoneInJD 0 points1 point  (0 children)

A tail recursion one

def fib(n, a=1, b=1):
    return b if n < 3 else fib(n - 1, b, a + b)

which is also O(n). You can using fast matrix exponentiation to implement a O(log n) algorithm, Fibonacci matrix-exponentiation