Caching

Python · Unit 21: Advanced Python

A recursive function can redo the very same work a huge number of times. To see it, write down every call in a list and count them.

fib(6) has only seven numbers behind it, but look at the calls.

calls = []

def fib(n):
    calls.append(n)
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(fib(6), len(calls))

Prints

8 25

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
What does this code print?
2. Predict the output
done records every calculation that actually happened.
3. Complete the code
Fill in the cache check.
4. Predict the output
seen records every time the body of fib actually runs.
5. Find the bug
It should print 8 and 8, because the second time comes from the cache. Which line has the error?
6. Multiple choice
Why is @cache a bad idea on this function?
7. Find the case that fails
how_many(x) should say how many items x has, whether it is a text or a list. Which call crashes?
8. Put the lines in order
Put the lines in order to count how many ways there are to climb n steps, going up 1 or 2 at a time.

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.