Memoization: Turning Slow Fibonacci into fastFib

Why does naive recursive Fibonacci recompute the same values, and how does a dictionary memo make fib(120) instant?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Count the calls of naive fib

Every call fib(n) counts as one call, plus all the calls its two recursive children make; fib(0) and fib(1) make no further calls. Define a recursive function numCalls(n) that returns the total number of calls the naive fib makes when you call fib(n).

def numCalls(n):
    # number of calls naive fib(n) makes, counting itself
    return ...  # your code here

def numCalls(n):
    # number of calls naive fib(n) makes, counting itself
    return ...  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

returns an int

a base case is a single call

matches the call tree of fib(6)

equals 2·fib(n) − 1 for n up to 15

←Previous Recursive maxVal: An Exhaustive Search That Beats Greedy Next Overlapping Subproblems and the Memoized Knapsack →