Recursion with memoization

Recursion with memoization

It happens that when using recursion we compute the same value several times.
For example, consider Fibonacci numbers and the recursion workflow for computing the value $F(5)$.

Notice that $F(3)$ was computed twice, and $F(2)$ — as many as three times!
At the same time, their values never change, and we could avoid computing the same values over and over again. How can we improve this?

The solution to this problem is memoization (memoization).
The idea is to create an array and store already computed values.

Then, when calling the recursion $F(n)$, the following steps are performed: