Fibonnaci sequence calculation Below are two ways to calculate an element of the Fibonacci series. Can someone please help me understand why fib1 is so much faster (over 60x) than fib2 ?

fib2 is just an assignment and a decrement whereas fib1 involves a dictionary and recursive calls.

Thanks.

import timeit

def fib1(n, lookup=dict()):
    if n == 0 or n == 1:
        lookup[n] = n

    elif n not in lookup:
        lookup[n] = fib1(n - 1, lookup) + fib1(n - 2, lookup)

    return lookup[n]


def fib2(n):
    n1, n2 = 0, 1
    while n &gt; 1:
        n -= 1
        n1, n2 = n2, n1 + n2
    return n2


n = 1000
recursive = timeit.timeit(lambda: fib1(984), number=n)
iterative = timeit.timeit(lambda: fib2(984), number=n)

print("recursive:", recursive)
print("iterative:", iterative)

"""
output:

recursive: 0.0012962640030309558
iterative: 0.08570116000191774
"""
The key difference is in a technic called "memoization". According to Wikipedia:
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
So basically, in the first function, you save all the previous results while on the second function you need to calculate everything again from the beginning for every new call.
A quick search on the internet gives this tutorial if you wish to learn more.