Welcome back.
So in this video we are going to continue our discussion on recursion with arrays.
We are going to solve another question as that will help us to better understand how we can use the
concept of recursion whenever we are given an array or a list.
So let us understand the question.
The question is actually pretty easy, and it asks you to find the sum of an array using recursion.
These kind of question I will be also giving you in an assignment, so that you can try and make sure
that you are able to test your understanding.
So please make sure that you are solving it in a similar way, and also try to actually follow the framework
the way I am coding, and draw the recursion tree and write the recurrence relation as well.
Okay, so the question again is the same right?
The recursion relation and draw recursion tree as well.
Give head and tail recursion solution.
Okay.
So now let us see this question everyone.
Record this.
So let us go here.
Let us create a new file.
And just add Python.
Yeah.
So 2.2 Some of any using recursion.
Right?
Right.
So I can make some array as a function.
And let us pass a easy input in this 12345.
Okay.
So we can run this.
Yeah everything is running.
Now let us break down this problem as well the way we actually see the problem.
So let us move forward everyone.
So pay attention.
What's going to happen.
The very first is going to be the base case.
So the way I'm thinking of doing this problem is that of course I will have a list here.
Right.
So I will have a list here.
I'm going to make sure that I'm able to work on the first element and the rest I'm going to ask recursion
to worry on.
Okay.
So the very first step everyone is going to be the base case.
So base case is going to be our first step I think in this as well.
The base case is pretty easy.
So it can either be that if size is zero the overall sum is be zero.
Okay.
Rather, I think that is the best base case to take.
Okay.
Or it can be.
If size is.
One, then we can return the first element.
We can just return the first element.
So basically L1 of zero.
Now if you actually think about this this is not the right base case.
This is not the right base case okay.
The reason for that is if our list is empty okay.
So let me just showcase it to you as well.
So if my LN of and let me make it L1L1 is equals equals to one return L one of zero okay.
So we are going to do something.
But I want to show you how this is not the right use case.
Now pay attention here everyone.
So what's going to happen now is because uh the other base case which we took was if size the second
if size is zero, then we can comfortably say that our sum is going to be zero, right?
So that actually helps a lot.
Let me just remove it because I'm going to.
Right.
Size is equals to one.
Then it is L of zero.
Else the answer is zero.
Now the second thing is I need to actually make a recursive call.
So I am going to call my sum function on the left over list on the left over list.
And I will assume that I'm going to get my answer.
Once I got my answer, then I think it's pretty straightforward and intuitive to understand.
I can just make sure that I am able to write.
I am able to do my calculation, which is just adding this thing right.
Sum of L one.
Okay, so this particular sum.
Now again let us just code this first and we will understand a few things.
So let me just say sum of left over array.
some array and it can be L1 of this.
So again this will give me the answer.
The answer can now be sum of left over.
Array plus whatever is there in by zero.
And I can return this answer right.
So yes I think this should work perfectly.
Well let me just run it.
We should print the answer as well.
Okay.
Let it save.
Yeah.
So answer I am getting is 15.
Now if you will actually see the reason I was saying that this is not a good test cases.
Because the second I make or pass an empty list, it will not be able to handle it.
It saved once.
Yeah, I am getting an error.
Okay then it is saying that recursion depth is exceeded.
Now the reason for that is because uh, L1 is basically an empty list.
It should have stopped there.
Right.
So these are some, I would say, very subtle things which I do not want you all to miss.
I know that 95% of students, they will have an idea when I say that, okay, this is not the best use
case, but I still want to make sure that, you know, each and every one of you understand this very
properly, that these are the minute, minute error which actually, you know, wastes your time and
everything.
So I want that when you are learning these things, you are actually very much focused on each and every
part of the framework or the problem the way I have asked you to solve a problem.
So with that particular thing, we should actually make sure that we are handling it in this way, okay?
Because see it will actually be keep on calling this function sum of array L one with one is to this.
So it will become an infinite call.
It will actually become an infinite call okay.
And I can just show you that as well.
So just let me show you the same as well.
Maybe what we can do is we can print l one here.
And if I run it now, see, it's an empty list.
Simply an empty list.
Now if you are thinking that why this is not giving an error again, slicing does not give you an error,
okay?
It tries to give you an answer.
Please make sure that you revise the slicing part again.
It's a very important concept and we use it a lot.
So yeah, with that I hope this is clear as well.
Let me make it remove it.
Let me make it zero.
Let me make the sum zero as well.
Okay.
And it is going to work perfectly fine.
Now of course, one more thing we can even change.
So I am just making summary two.
We can just, I would say take it upwards as well.
One second.
So I can just have this thing.
The answer here.
Okay.
Answer something like this.
And I can just make my answer is equal to answer plus summary I can return my answer like this.
So here just what I am doing is I am just actually.
Yeah.
Or let me actually just get rid of this one second.
Yeah.
This one, this is something which I want to do.
So I am doing my work first okay.
And then just calling this particular method again this is not a tail recursion.
I have already told all of you guys this that this is not tail recursion.
Still.
Okay.
Don't get confused in that.
If I actually want to write a tail recursion code for this, if I actually want to write a tail recursion
code for this, it would be something like this.
Again, I will be getting an I would be needing an accumulator.
Okay, so let us keep it accurate.
It should be fine.
Initially I can take it as zero right?
So if my L1 of my length of L1 is equals to zero right, then I need to return the accumulator.
Okay.
This kind of handles all is the value is actually equal to the base case.
Majorly okay.
Else what I will be doing is I'm going to make sure that I'm adding in my accumulator the zeroth element.
And now I am just calling this particular function.
So I am just returning this.
L1 one and the accumulator okay.
This is actually the perfect I would say tail function code for this.
Once I have called this function I'm not doing anything after this.
Right.
So in this I was actually calling this.
Then I would have calculated answer.
Even if you remove this answer and return this directly, I have shown you already in the last I think
some class where we have discussed that this is not going to be the case.
It is still a head recursion, but this actually using the accumulator.
This is the tail recursion.
And we can now actually run on multiple use cases.
Let me just do the same one second here.
Let me copy this once again okay.
So just let us have 12345.
Here we can do summary 212345.
And we can just call summary tail with this.
With this 12345.
Right.
Let me run it now.
So the answer should be 15.
For first we are getting the right answer for this.
It should be zero.
We are getting the right answer.
No errors.
Summary two we are getting the right answer 15 zero.
And finally the 15 answer is there.
Okay, so I showed you this.
But of course again we should be good to even draw and I should rather draw the.
This was an easy question, but as I told you initially, when you will be coding after code and before
running the code, like in between that you have to make sure that you are writing the.
Recursion tree for your problem.
So this is actually how the problem is going to start.
You are going to make a call.
You are going to make a call downwards.
Okay.
Did we make a circle.
Okay.
Not sure why this is making ovals now but yeah.
So we are calling for 2345.
I know it is easy, but I still want to have that.
I would say practice and I want to make sure that you also draw the same.
So I am also spending this time because now as we will move forward, some of the problems are going
to be a little bit tough.
And if you have done this practice of making, I would say recursion tree, that will actually help
you a lot in solving those problems.
Okay, so on LeetCode as well.
Many questions are there where if you actually have this habit of solving with like making the tea,
then you will see that yeah, everything is actually happening nicely.
Okay.
So yeah now pay attention everyone.
This is going to return zero.
Now once I get zero I am going to add five to it.
And I am going to return five here.
then nine is going to get returned.
Then you are going to return nine plus three.
So I am adding this first element every time, right?
Again I can handle it by the last element as well.
Totally on you.
I would rather appreciate or just encourage you to write the code.
If you are able to write that code, it will be really great that you are able to understand.
So just write the code by taking the last element.
Okay, so slice your list such that you are sending the first two.
I would say second first two second last element okay.
So just you make sure that you are keeping the last element with yourself.
And recursion is taking care of the rest of the list.
So this is going to return 12.
This is going to return 14.
And finally we are going to return the answer which is going to be 15.
Now in your tail recursion solution which I have given, what is going to happen is that you have to
maintain a accumulator or answer variable okay.
So you have to make sure that you are making changes into that as we go forward.
And again that because that is tail recursion, you will be doing everything before I would say sending
or before making the recursion call.
Right.
So this is again your recursive tree.
You are going to write the recursive relation.
We have written this or done this in all the forms.
Right.
I do not think we need to see the that visually.
I have shown you here as well that visually what is going to happen.
And this is going to be exactly the case.
Right.
And we are able to solve this question.
Now, the reason I have taken this easy question and written the code so that I can now build on this
in the next few classes, I will be actually discussing a single question, but we will be doing it
in different, different ways so that I am able to explain you the complexities which can arise when
we are solving recursion and list question right.
And the same actually will be a lot helpful when we move forward and solve questions with recursion
and strings, right?
So please make sure that till now you are doing all the questions which have been given in assignment.
You are watching the recordings again.
If you have any doubt, and please make sure that you are following the framework whenever you are solving
the question given in assignment or any other recursion question otherwise.
Right?
So yeah, thanks a lot everyone.
Let's meet in the next class and we are going to solve much more question to solidify our understanding
of recursion.
Thank you.