And when you make a recursive call to solve some sub-problem, before

trying to solve it, you check in a table whether its solution is already stored.

And if its solution is already in the table which means that it was

already computed then you just return it immediately.

So this recursive call, turns out to be just a table look up.

So this is how a recursive algorithm with memoization works.

Let's see how a recursive algorithm with memoization for

the Knapsack problem looks like.

For simplicity let's assume that we're talking about the Knapsack

we use repetitions.

In this case, we need to compute our sub-problem for a Knapsack of size w,

is just the optimal rate of a Knapsack of total weight w.

So we computed as follows, we computed by recursive procedure.

First of all, we check whether its solution is already in a hash table.

We use hash table to store pairs of objects.

So, for weight w, we store value of w if it is already computed.

If it is already in the table, we return it immediately, otherwise we just

compute it and we make recursive calls to compute the values for

the sub-problem on w minus wi, okay?

And when the value is computed, we just store it in our hash table.

So this way, we use memoization by storing this in the hash table

to avoid recomputing the same thing once again.

So once again, an iterative algorithm solves all sub-problems

going from smaller ones to larger ones, right?

And eventually solves the initial problem.

On the other hand the recursive algorithm goes as follows.

So it stars from the initial problem and

it makes recursive calls to smaller sub-sub-problems, right?

So in some sense an iterative algorithm and the recursive algorithm are doing

the same job, especially if we need to solve just old range of sub-problems.

However, a recursive algorithm might turn to be slightly slower because