Hello all and welcome back.
So in this video we are going to continue our discussion on recursion and see how recursion can be used
to solve problems related to strings.
So let us get started.
Now the basic idea is still the same.
Recursion for us is still actually a way through which we can solve a problem, which depends on a similar
smaller problems.
Now, the good thing about strings is that just like array or your list, your strings can also be broken
down into smaller version of itself.
And we know that for the same, slicing and indexing are the major concept which is supported in Python.
So I would highly suggest if you have not seen the videos which is included in this particular course,
please make sure that you see that and understand what exactly this is.
Now I will just help you to give a quick refresher.
Slicing is when we want a part of a string.
Okay, so let's say if a string is hello, then using slicing I can get.
Let us say.
The part hello of my string by reviewing H and by indexing, I can get a single element okay.
Indexing and slicing both works forward as well as backward, though if you are comfortable with either
one of them and majorly the positive one, we should be good to solve the question of recursion.
Now, the idea is that we will be working on some part of string and let recursion handle the rest.
A very easy question for this can be if we want to find if a particular character, let us say in this
particular hello world, if we have O present or not, then of course we can check on one part of the
string and let recursion take care of the rest.
So we will be solving more and more questions on this and the concept will get clear.
Moving forward, I will also make sure that I solve some hard problems on this as well, because in
strings many things are there which have to be mastered.
Okay, bye.
In case of recursion, which help us to solve other problems.
So please make sure that your overall concepts and idea of using string functions.
And this is a lot clear.
Okay, so now let us actually solve one question everyone.
Strings.
We have already established that they are just arrays or list of like continuous characters.
Right.
And we can break them.
So let us solve some questions.
Now the very first question which I want all of us to solve is to remove character.
We will be giving a string and we will be given a character.
Okay.
And what we have to do is we have to remove that particular character from that string.
So let me just solve this one second.
So first, as we do for each and every of the recursion problem which we are solving, or any problem
in algorithmic solving, what we do is we first try to see that, okay, what exactly will be the input
and the output.
Right.
So in this particular case, whenever you are given any string, right.
Whenever you are given any string, in this case good morning.
The final output the final output will have all the z removed.
Similarly, if let us say the string is Dragon Ball Z.
Then the final output is going to be Dragon Ball.
Okay.
So now let us try to solve this.
Everyone we are going to solve and use the recursion framework which we have learned.
Now the very first thing which we used to do is to write our base case.
Now base case as many of you can think of, just like list and arrays we have, if a string is empty,
right.
If the length of my string is zero.
Or I can say that if s is equals to an empty string, then of course I cannot remove anything, I cannot
add, I cannot remove anything from this.
Right?
It will not be having that character so I can return the string as it is.
Okay.
So that is our base case.
That is the first step.
Second can be a recursive call.
Now in the recursive call, I have to make sure that I can somehow divide my string and let recursion
take care of that.
So we can call our recursion remove character.
And we can call it say on Everything apart from the first character, because we are going to work on
the first character.
Okay.
And the last one is just r work.
So in this particular use case or sorry, in this particular problem, r work will just be check if
s one of zero that is going to be equal to z or character or not.
Okay.
So that's the whole work which we have to do.
Everyone.
Now I have already explained you this framework, this three steps a lot of time.
We are also aware that the second and the third step.
Right.
They are interchangeable.
So you can do either of one of them first.
So let us see the same everyone.
Now let us say first is if length of my s one is equals to zero or s one is an empty string, then we
can just return as it is.
Okay, so we have to make changes in our string only, right?
So we can return the string as it is.
Let me just get it into answer and we can print the answer in the end okay everyone.
So this is how we are going to do it.
Now the next thing is we have to.
So what we are saying is we are going to call recursion okay.
So let me make it small.
Answer or recursion answer which is going to be remove character.
I will be passing S1 and this and I will be passing CK as it is.
And finally, once I get my answer, there is just few things which I have to do before I can return
this answer.
If the first character, the character which I am dealing with, if it is equal to H, then we do not
need to include that, right?
So we can just return this small answer.
But if that is not the case, if that is not the case, what I can do is I can return s1 of zero, the
first character plus small answer.
Now strings are of course concatenated by adding this plus and I think this code will run a perfectly
fine.
It will run this and see the course.
Yeah.
So good morning is coming.
Now let me take another thing and show you the output.
So let us take a b c z z okay.
Let us try to run this.
It is working perfectly fine as well.
So let us see this once.
Everyone let me show you the same thing once by drawing the tree so that you understand the same.
Now please make sure that you write the recursion relation and everything because that's going to be
a lot helpful.
Okay.
So I will be getting my string second.
Yeah I will be getting my string.
S one equals to a b c z.
I want to check if the base case is there or not.
I think it is not.
The length is not zero.
I'm going to call it to the next recursive call, which will get b c and z z.
Similarly, it is still not the base case, so I'm going to call for c z z.
This is going to call for z z.
Z.
And finally an empty string.
Right now this right here is actually the base case.
So this I know is a base case.
And here we are returning the string as it is.
So let me return it.
It's going to be an empty string okay.
Now when I call when I see for this particular function, it will check if the first character which
is s one of zero.
So this is our s one here.
And s one of zero seems to be equal to c h, which is our z, right?
If that is the case, if that is the case, then we have to make sure that we return the answer, whichever
we are getting, because we do not have to include Z.
The whole aim of this question is to make sure that we can remove this character, right?
If that's the case, then I can actually just return whatever I'm getting from recursion, because I
have to make sure I'm just skipping this character.
Okay.
Similarly, in this case as well, because s one of zero is equal to z, I can return an empty string.
Now this time it is c.
It is not equal to z.
So we are not going to go in this particular line and instead append our character at the starting okay.
So now it is going to be C plus empty string which is nothing but your C.
Similarly here the first character is B.
So we are going to append our character in the starting the b c is something which you are going to
return, and finally we will return.
We will just combine A, B, C and return it.
Okay, so I hope everyone this thing is clear.
Now, please make sure that you don't think of this tree while writing your code.
But once you have written the code based on the PMI principle, which I have taught specifically in
recursion, then you should be good to write this code.
Okay.
So let us try to just visualize it quickly everyone.
Now I know I have shown this again, shown this already, but I want to still make sure that you understand
this very nicely.
Okay.
So pay attention everyone.
Let's remove character S1S.
So this is the s one.
Now we are going to make the call H is equal to z okay.
It is going to check for the base case here and then move forward.
Now to get the small answer.
To get the small answer it is going to make a function call okay.
So if you will see now the string has actually been shortened okay.
So let us call it now the next.
Again it is not a base case.
So it is going to call the function call.
Again it sees z z.
Then again it said z.
It z and z as of now no way we are checking it right?
We are nowhere checking it.
And finally, when my string will be an empty string with zero characters, connectors.
That is where I will hit the base case.
Everywhere you will see that it is just getting passed as Z only because I am passing it as it is.
Now what is going to happen?
Because it is an empty string.
I am going to return my s one as it is.
So let me return it.
Once it is returned, this particular function will get the small answer as an empty string and it will
check for itself.
Is the first character equal to Z?
Yes it is.
So I am just going to return my answer because I do not have to include that, right?
Same for this particular function, we are going to return the small answer which we are getting.
But in this function, when it is c, z, z, the first character, the s one of zero here is actually
c.
So I have to make sure that it is part of my final string and not skip that.
So if we do that, L statement is going to get run and we are going to append this C to my answer and
this is the return value.
Once I go upwards again b this time is the first character.
It is not equal to c h.
So I am going to move forward and b c is the answer which I am going to return.
And finally a is my answer.
Now C see everyone.
Please make sure that once you run on recursion, write this.
I've told you many times, but still I want you to make sure that you assume and understand this when
you call this particular function sorry.
When you call this particular recursive call for this function like this is the exact same function
which you are calling, right?
You have to divide your string so your string become b c z z.
Okay.
This is what's one of h is going to be.
And you have to assume that you will get your answer.
So you will get BC here and write all your code with this BC in mind as an answer.
Now how is that going to happen?
You don't have to worry about.
So assume this small answer is going to be BC.
And based on that, write your whole code.
And if you do your work properly, if you handle all the cases, all the edge cases, then for sure
PMI says that your answer is going to be right.
And that is something which we have done while writing our code right.
I didn't draw this tree while I was writing the code.
No, I just had this assumption, the same thing which I have taught you.
I just had this particular assumption that once I pass this string, I am going to get all the Z removed.
I don't need to question how recursion is going to do that.
Okay.
The same understanding is going to carry on in string as well.
Okay.
So once you have written the code perfectly then it's going to work fine.
And we can see the answer as well.
So finally when I do this my answer is a b, c where in the end I can just print a b c okay.
So yeah everyone, I hope this thing is clear how we have written this particular code, how the principle
of recursion is used here as well.
It's very I would say similar to how we were using it in list, but we have to just see and some different
questions are there.
So we are going to solve that and understand and master this particular way of doing recursion and strings.
Okay.
So cool.
Then everyone let's meet in the next video.
Just please make sure that you are doing all the questions which I am adding in your course, because
that will help you to understand and actually better do these questions yourself.
Okay, so I've added lots of assignments for you, so please make sure that you do that because these
assignments are added or crafted in such a way that they help you in understanding recursion a lot more
in depth.
Okay, so cool everyone, let's meet in the next video and continue our discussion.