Remembering what you already worked out

Take Ravi's four-line function and add a notebook.

memo = {}

ways(n):
    if n <= 1: return 1
    if n in memo: return memo[n]
    memo[n] = ways(n - 1) + ways(n - 2)
    return memo[n]

Three lines added. ways(50) now answers instantly, and so does ways(50000) if the language allows recursion that deep.

Why the change is so large

Before: every call branches into two, so the work doubles with each step.

After: each distinct n is computed once. There are n of them, so the whole thing is O(n). Twenty-five billion calls become fifty.

The recursion is unchanged. The only new idea is not doing the same work twice.

This is the route to take

Most courses teach the table first. That is backwards for almost everybody, because the table is an optimisation of something you have not written yet.

Do it in this order, every time:

1. 1Write the honest recursion. Get it correct with no thought for speed.
2. 2Add a memo keyed on exactly the arguments that vary.
3. 3Only if you need to, convert it into a table.

Step one is where the thinking is. Steps two and three are mechanical, and step three is often unnecessary.

The one thing to get right

The memo key must be every argument that changes, and nothing else. A function of (index, remaining) needs both in the key. Keying on index alone silently returns an answer computed for a different remaining, and the result is wrong rather than slow, which is far harder to notice.