Why does naive recursive Fibonacci take exponential time while the memoised version is linear, and what does the call count show?
Because the naive version asks for the same answers over and over, and the memoised version asks for each one once.
def fib_naive(n, counter):
counter[0] += 1
if n < 2:
return n
return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)
def fib_memo(n, counter, cache=None):
counter[0] += 1
if cache is None:
cache = {}
if n < 2:
return n
if n in cache:
return cache[n]
result = fib_memo(n - 1, counter, cache) + fib_memo(n - 2, counter, cache)
cache[n] = result
return result
So here is what the call count shows. The naive version makes about one and a half to the power of n calls, so for a number of thirty it makes about a thousand calls and for a number of a hundred it makes an impossible number of calls. The memoised version makes exactly n calls, because each value is worked out once and then remembered.
the number asked for naive calls memoised calls
--------------------- ------------ --------------
10 177 10
20 21891 20
30 2692537 30
So why does the naive version grow like that? Because the recursion asks for the same numbers again and again. To work out the answer for n, it asks for n minus one, and to work out that it asks for n minus two, and to work out that it asks for n minus three, and that work is repeated over and over.
And the memoised version fixes it by keeping a note of every answer that it has worked out, so the second time a number is asked for it looks in the note instead of working it out again. That one extra line changes the shape from exponential to linear.
The next question in this topic looks at how to work out the bound of a recursive function in general.