Hello all and welcome back.
So in this video now let us try to delete the tail of our linked list using recursion.
Now the same thing we have done using iteration in the last video.
Pretty sure that you have also tried the same as an assignment.
When we have to do something using recursion again, we know the steps.
So first let us see what our head is right.
Now if I have to do this using recursion okay then let's see what are the steps.
So first is going to be the base case.
Then is going to be recursive call.
And lastly we have our work.
And as we have seen multiple times they can be changed right.
So first let us talk about base case everyone.
So base case I believe is pretty simple.
If our head is none.
So an empty list.
Right.
Let us write that.
So def delete at tail.
But using recursion we will again be getting an head and first base case.
If head is none, then all I have to do is I have to return none.
Okay, so this is my base case.
Great.
So yeah.
Cool.
Now let us see the recursive call.
And ah, so recursive call I think is pretty easy.
Again we just have to pass the linked list like this.
So I have to break the linked list and just pass the next node.
So recursive call we can easily write as well.
Delete head dot.
Next right.
Now let us see our work.
Our work I think is pretty easy as well.
If if we are at a node where head dot next, if we are the last node, the tail node right is none,
then I think we should just return none.
So this can be our work.
So all I am handling is if I am the last node then please just return none because I should ideally
be deleted.
Okay, so just think of this particular node.
Let's say you get this as your input right.
Then the step which you will be taking is something like hey, I am the last node and you are asking
me to delete the last node, so I think I should be deleted, right?
So that's the overall understanding there everyone.
So if that's the case, if that's the case then let us do our work first.
Because if I am the last node then why should I call recursion again?
It can be done in any ways.
So if head dot next is none right?
Then all I have to do is again I have to return none.
Now the two conditions can, of course, be clubbed together.
That is not a problem.
Now I have also done my work.
So head dot next is going to be delete tail and recursive.
And I've already explained you.
Please make sure that you see the video where I've explained why we have to rejoin this connection.
Okay.
If you don't rejoin this, then maybe let's say the next overall node is the tail, right?
If we don't rejoin this, then we will not have the changes in our linked list.
And once this is done, we can just return head.
Yeah.
So I think this will be more than enough.
Okay.
We have just done all the work.
So we have handled the base case, we have done our work.
And then if we are not the tail node then we are just asking recursion to do the same.
Okay great.
So let us just try this quickly everyone.
Cool.
Let me clear this and let us run this.
So ten 2030 minus one we are getting the last node deleted.
So 30 was the last node.
Now we are getting 20.
Let's check it for one more case.
Ten and minus one.
We are getting the node deleted and for an empty linked list as well, we are able to see this.
Okay, so now let us see what would have happened exactly.
Let us see the recursive call as well so that it is clear a lot.
We have already done this exercise, but I still want to make sure that you understand this.
So if you have a clear idea, you can actually skip this.
But for students who are still facing issue, please make sure that you understand how recursion behaves
with a linked list.
Okay, great.
So what would have happened is we would have first checked okay.
So we would have first checked.
If it is none or not, it is not none and not till.
Right.
So I am just calling forward.
Same is the case here right?
Not none.
Not till.
So not none.
Not till.
Calling forward again.
Not none.
Not tail falling forward.
This now seems to be the tail.
This seems to be the tail.
Right.
So here, if you will see, I have just checked for these two conditions.
Right.
As of now, I have just checked for these two conditions.
Now, if this condition is not true, then we are just recursively calling for the leftover linked list.
That is what we have done.
So first we called for this linked list.
Then this particular function call for this linked list.
And like this.
Right now finally when we reach the tail finally when we reach the tail is one second.
Yeah.
So this is a tail right is a tail.
Now if this is a tail then that basically means that I am going to return none.
So I will make it none.
Because if you are a tail, then I should just return you as it is.
And once I return this as none this overall 30 node, this 30 node should just remake its connection,
right?
So the connection is going to get made.
Maybe we can draw it by green.
So yeah, this connection is going to get made right.
Something like this.
The connection is going to get made because none is getting returned, okay.
None is getting returned.
And we have to make sure to catch it.
Now once this is done again just 30 is going to return here.
The connection is same here 20 is going to get return, connection is same.
And finally I'm going to return my head which is ten.
But if you will see here what has happened because of recursion, this is now my linked list ten, 20,
30 and none.
Right.
So I hope each and every one of you are able to visualize that.
What exactly happened?
Why this last node when the recursion was called on a single node, on a single node linked list, it
was able to return me none.
And how?
Because I rejoined the connection on this line on this particular line head dot.
Next how I was actually then able to make sure that the whole linked list is getting changed because
I am returning the head and I am rejoining this connection as well.
Okay everyone, so I hope you are able to actually imagine how the recursive calls are.
Again.
Uh, you have to use a mix of visualization and python tutor.
I will not suggest to use Python Tutor always.
Uh, neither.
I would suggest that if you are not able to visualize, then draw always.
But yes, overall you should be able to understand properly and for that you will have to draw and actually
see what are the calls which are getting made.
So here the important thing was when just a single node linked list is passed, because it is a tale
based on my condition, I am returning none and I am rejoining this connection because after that everything
is same.
30 going to get return, 20 going to get returned right?
This is how this code and this line number 40 efficiently is actually handling all the things.
If I just remove this condition then also also it's a problem because I have not done my work properly.
Right.
So cool everyone.
I hope with that it is clear.
Now let's meet in the next video where we are going to do delete at any given index.
Thank you.