Hey everyone!
Welcome back!
We have discussed so far various interesting things regarding recursion.
Another important thing to know about recursion is that you can write recursive solutions, either going
from zero to n or n to zero.
Now remember, it's interesting to know that this is possible, but if you can practice writing solutions
in both ways, it's very helpful because it will help you develop a good grip on solving coding interview
questions.
So let's go ahead and try this out together.
So let's say the question at hand is given n find the value of one plus, two plus, etc. up to n.
So this is the question at hand.
Let's try to solve this question in both ways.
We are going to do it recursively, and we will do it from zero to n as well as n to zero.
First let's write the recursive solution where we are going from zero to n.
Let's write the pseudocode for this okay.
So let's get started.
Now let's say I have a function and I call it sum.
And I have the parameters the current sum and n over here.
And I'm passing the initial sum as zero.
And I want to add up till five.
So zero comma five are my inputs.
And then the recursive case is that I'm just gonna return curr plus sum of cr plus one up to n okay.
And again let's draw out the recursion tree for this.
And the base case is going to be that if I hit five right.
If I reach five if cr is equal to n.
And in this case that's five.
So if CR is equal to n then I'm just gonna return n.
So let's see if this will work.
So initially I'm going to call sum with the parameters zero and five.
So sum zero comma five.
And inside the body of the function cr at this point is zero which is not equal to five.
So it's gonna recursively call sum of cr plus one and again pass n as five.
So that's sum of one comma five and cr at this point is zero right.
So again when we return it's going to be zero plus sum of one comma five.
So this sum of zero comma five is gonna recursively call sum of one comma five.
And then again we are inside the function cr is one.
It's not equal to five.
So we're going to call recursively sum of two comma five.
This is going to recursively call sum of three comma five which again is going to call sum of four comma
five.
And this is going to call sum of five comma five.
At this point CR is equal to n or five is equal to five.
So we have said that we have hit the base or terminating condition and let's just return n.
So n is equal to five.
So this over here.
Is gonna return five.
Okay.
So this the value of this is going to be four plus five.
Okay.
So sum of four comma five is going to give the value nine okay.
So this over here will become three plus nine which is.
12.
Okay.
So some of three comma five is going to be 12.
And this is going to return two plus 12 which is 14.
So some of two comma five will be 1414 plus one is 15.
So some of one comma five is 15.
And then we're going to add zero to it.
And thus some of zero comma five is gonna return the value 15 okay.
So one plus two up to five has the value 15.
So we have solved this question using recursion.
And notice that we went from zero to n over here it's zero car is one, two, three, four and five.
Right.
So we solve this question by going from zero to n.
Now let's try to solve the same question by going from n to zero.
Let's write the pseudo code for it.
So.
Let's write it over here.
Now I could write the function sum as sum and the input is n, and I'm calling it with the input parameter
five.
And then the recursive case could be returned n plus sum of n minus one.
And the base case is.
If n is zero return just return.
All right.
So notice that the base case changes based on how you write it over here.
The last valid case is going to be one.
Or the first invalid case is going to be zero.
Right.
So you can think of the base case as the first as the last valid case or the first invalid case.
And in this case because we were going from zero to n, so zero one up to five.
So we had five over here, which was the last valid case.
So the base case changes based on how you write it.
Now let's draw the recursion tree for this solution over here.
So initially we call sum of five.
And this is going to call sum of four right n plus sum of four.
And this is going to call sum of three.
And this over here is going to call sum of two.
Which in turn will call some of one, which in turn will call some of zero.
And at this point we will hit our base condition and we will just return.
So this is just going to return.
Okay.
So we could say return zero okay.
So let's say return zero.
So this value over here is going to be one plus zero which is equal to one.
So this is going to be one.
And this is going to return two plus one which is three.
So s of two is going to be three.
Now S of three is going to be three plus three which is six S of four is going to be four plus six which
is ten.
And S of five is going to be five plus ten which is 15.
So in this way notice that we went from five to 4 to 3 up to zero.
Or we went from n to zero.
So you can write recursive solutions going from zero to n or n to zero.
So try to write at least a few questions.
Try to practice writing the solution in both ways, so that you get a good grip on solving coding.
Interview questions using recursion.