Рекурсия бо мемоизатсия

Memoization in Recursion

Sometimes, a recursive function computes the same value many times.

A classic example is the Fibonacci sequence. Let us look at what happens when we compute $F(5)$ using the naive recursive formula.

Notice that:

• $F(3)$ is computed twice;
• $F(2)$ is computed three times.

But these values never change, so recomputing them again and again is unnecessary.

How can we avoid this?

Idea

The solution is memoization.

We create a data structure that stores already computed values. Then, when the recursive function is called:

• if we are at a base case, return the answer immediately;
• if the value has already been computed, return the stored result;
• otherwise, compute it recursively, save it, and return it.

For Fibonacci numbers, this means:

• if $$, return ;