Dynamic programming

Predict first

How many times is fib(1) called while computing fib(20)?

1def fib(n):
2    if n <= 1:
3        return n
4    return fib(n - 1) + fib(n - 2)

• Thousands of times

• Once

• About 20 times