And 9, choose 4.

So it's calling the function, plus calling the function on 9 and 5, 9, 9 and 4.

Then when it comes here and says compute 9, 5, it's going to say,

okay, it is compute 8, 5 and 8, 4.

Here it is 8,4, 8,3.

Then it's going to continue.

7,5, 7,4, 7,4, 7,3, 7,4, 7,3, 7,3, 7, 2.

So each one of these here, when the parentheses

is really a call to this function.

So the function is being called over and over and over, so when we call it on

ten five, it's, it mean two codes to the function of these parameters, 9,5, 9,4.

When it called this, it called the function twice with eight comma five,

eight comma four.

And this again, 6,5, 6,4, 6,4,

6,3, 6,4, 6,3 6,3,

6,2, 6,4, 6,3.

Here.

6,3, 6,2, 6,3, 6,2, 6,2,

6,1 and it continues because it hasn't

reached any of these case now what is happening

here let's look at 6,4, 6,4, 6,4.

Okay?

And we have [SOUND] 6,3, 6,3,

6,3, 6,3, 6,3, 6,3.

So this function, this recursive algorithm is going to call itself.

Six times on the, on the same parameter.

6,3, 6,3, 6,3, 6,3, 6,3.

Okay? Because the recursive algorithm,

when it reaches this call here and

says okay, now I need the value on 6,3, it's going to call the function.

It doesn't know that somehow, somewhere else it had already computed it.

And this.

Example illustrates the problem, in this case, with recursive algorithms.

We have these overlapping sub-problems.

This sub-problem, 6 choose 3, is overlapping.

It's here, and here, and here, and here, and here, and here.

What this means is that this path, and this path, and

this path, and this, and this one and this one, they are overlapping at this problem.

Recursive algorithm is not going to keep track of that.

It doesn't know that this overlap.

It's going to keep computing them.

Suppose that computing 6 choose 3.

Right?

The function is going to take million seconds here.

It's going to do a million, plus million, plus million, plus million, plus million,

plus million.

Dynamic programming algorithm knows this, keeps track of this.

It has one entry in the matrix because it's building it so this is,

if this is the K, it has three here.

If this is the N, it has six here.

It has this value.

It might take million steps to compute it.

But it will take less, by the way, because again there's still some over-lapping here

that is being exploiting.

It, even if it takes a million steps, next time it's need it,

it's better, the computer is going to take one step to look up that value,

one step to look up that value, one step to look up that value, and so on.

Okay?

So this is the major difference between dynamic programming and recursion.

When we have this notice that to have a dynamic programming algorithm,

I had to had a, to I had to have a recursive formula.

I had OPT of I, J equal max of OPT I,J minus 1 and so on.

When I have recursive formula the natural thing for

me to think about is let me implement it recursively.

Let me have a recursive algorithm.

But when we have this nat, this nature of

the problem that the subproblems are overlapping, recursive is, recursion and

recursive implementation is going to be costly because the, this subproblems.

Are going to be computed over and over and over.

Every time we see that's a problem,

the function is going to compute from scratch whereas dynamic programming

overcomes this problem by storing the values in in a matrix.

And in it's nature of going from smaller sub-problems to larger sub-problems so

that by the time is comes to 9,5 it had already computed these values here.

So when it comes to compute 9,5 all it needs to do is look up this value,

look up this value, and add the two values.

When it comes to compute 8,5 it gets this, it gets this, and adds them.

Here when, when recursive algorithm comes to compute 7,4,

it's going to compute 6,4 take all the time to compute this, then it

will take all the time to compute this, and then it will add the two numbers.

Dynamic programming, when it wants to compute this, it just looks up this value,

looks up this value, and adds these two.