Recursion With Memoization - Resources

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Resources/Misc/Recursion With Memoization

Recursion With Memoization

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 ;

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

ATCODERD. Yet Another Recursive Function

n

=

0

n = 0

n = 0

0

if

n = 1

, return 1;

if

F(n)

has already been computed, return it;

otherwise, compute

F(n) = F(n-1) + F(n-2)

store the result, and return it.

This reduces the complexity from exponential time to:

O(n)

Implementation

Result

With memoization, each value of F(n) is computed only once.

So instead of building a large recursive tree with many repeated calls, we reuse answers that were already found.

The new recursion scheme looks like this:

unordered_map<int, int> mem;

int F(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (mem.find(n) != mem.end()) {
        return mem[n];
    } else {
        return mem[n] = F(n - 1) + F(n - 2);
    }
}