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 is just an assignment and a decrement whereas
fib1 involves a dictionary and recursive calls.
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 > 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 """