Hello all and welcome back.
So in this video, let's continue our discussion on recursion and solve one of the most famous problem
in recursion which is Tower of Hanoi.
So first I will explain you the problem.
Now again this was given to you as an assignment as well.
So I hope you have done the same.
Your end at once.
This is a little tricky to get, but once you actually apply recursion to it, you will realize the
power of recursion.
Plus, actually you understand that how great recursion is like how nicely it can solve questions of
these type as well.
Okay, so great everyone, let me now try to explain you this problem in Tower of Hanoi.
What happens is that we have three towers in front of us.
Okay.
We have these three towers in front of us.
Let us say this is source.
Let me write it.
On top of that, let us say this is source.
This is destination.
And this is your auxiliary or extra auxiliary.
Now our aim is to make sure that we are able to move these disks from source to destination using our
auxiliary bar.
Okay.
Auxiliary tower.
Now, many of you might be thinking that why Oxley Tower is required.
Why can't I just put and just have these disks like this?
Well, the problem with that is that there are some rules, okay?
There are some rules.
The rule says that A you can only move one disk at a time.
Second, nowhere in the middle okay.
Nowhere in the middle.
Should you have a case where a larger disk is on top of a smaller disk.
So if you try to move the three disk the way you are asking without auxiliary, then there is no way
to do that, okay?
There is no way, absolutely no way we can move them.
Okay.
So great.
Let us now try to solve this before actually moving forward with solving.
Uh, let me just show you some cases as well.
We have to tell the exact path that.
Let us say, for example, what we have to tell if, say, this is going to be my s, this is going
to be my D tower and this a tower.
Then I should basically tell, for example, for a single disk, if a single disk is there, I can just
directly move from S to D.
Okay, how I can do that?
Let me showcase and visualize help you visualize as we are solving everything by visualization.
So that would be helpful.
See this is the source one.
This is the destination.
This is the auxiliary.
If I have to move a single disk, I can just pick it up and move it.
Thus the answer is going to be A to B or source to destination.
Okay.
Now if I have to do the same thing for two disk, how it is going to be, first I have to make sure
that I move it this one disk to C, then I can move this disk to B and then finally this C.
So first I am making this disk move to auxiliary.
So source to auxiliary.
The first step second step source to destination and third step auxiliary to destination.
So the answer is going to be something like this.
Source to auxiliary source to destination, auxiliary to destination.
So anyone who sees my this particular answer, he will be able to finally move the same.
Okay.
Great everyone.
So now let us move forward.
We have seen two test cases.
Should be fine.
Let me set it.
Okay.
We have seen for one and two.
So great.
Now, many of you might be thinking that.
How are we going to go about the problem?
Well, we have to assume that.
Okay.
See, the first thing is that we have to assume so Def Tower of Hanoi okay.
We will be getting n disk.
You will be telling what the source is, what the destination is and what the auxiliary is.
Okay.
Like the name of these things.
Let me just, uh, for the timing because we are not printing anything when we pass it.
Tower of I am passing it for n disk.
Okay, so let me x n is equal to something.
Let us take three for the time being.
N source I am passing as s destination as d auxiliary as a.
Okay, so these are the just the names of my tower.
Okay everyone.
So I hope the problem is a lot clear.
I have shown you help you visualize the same.
I have shown you using example as well.
Now we have to just tell these paths for n number of disks like this n can be any much.
Now what exactly we have to do.
Let us understand the approach now.
Okay.
So we will have this thing.
We will have these towers right.
And I have to assume for n disk.
Now let us apply try to apply recursion for this because I think this is a very recursive kind of a
nature problem.
Right.
We can handle some disk, some part, and recursion can help us do the same.
This problem seems to be breaking like seems to be something which can be broken down.
The very first is going to be the base case.
Now, I think we have already seen what base case can be like.
We can either have a zero, like we have the number of things at zero, let us say, or the number of
things at one number of disk basically.
So if it is going to be n zero, then I can just return because I cannot print anything.
If n is equals to zero or sorry one, then I have to make sure that I am moving my disk from source
to destination and I will get my answer right.
So if I make it one, then all I have to do is move from source to destination.
Okay, for the time being, let me make it source destination so that you don't get confused and you
have a proper answer and auxiliary great.
Cool.
So now let us see how recursion can help us do that.
Now, my whole understanding with recursion is that I'm going to do some work, and I'm going to ask
my recursion to do other work for me.
And these are your base cases everyone.
Now second one is your recursive call.
Second one is your recursive call.
Right?
Now what I am actually thinking of what I am thinking of is that, see, I have this particular fixture.
I have this particular fixture.
Right.
So pay attention.
What I'm going to do.
Everyone is going to be a little bit different on the quotient we have done.
Let us say I have n disk here, I have n disk.
Now what I'm going to do is this is source, this is destination and this is auxiliary.
What I'm going to do is I'm going to ask my recursion that, hey, you take care of this n minus one
disk, and I'm going to take care of this one disk because it makes sense, right?
We are lazy.
We want to do less work.
So I will ask my recursion that hey, can you somehow do something for me?
I know that we have to move these disks.
We have to move all of these disks to destination here.
But can you for the timing, please move all these n minus one disks to this particular extra tower
or auxiliary tower instead of destination?
Now why am I asking the question to do it?
The reason is that if recursion is able to make all of these disks here, then I will be just left with
one disk.
And I know I can move this one disk easily from here to here to the destination.
Right?
So I will explain this again because this might become a little tricky.
So pay attention everyone.
What I am going to ask recursion to do is what I am going to ask recursion to do is.
These are going to be my N disk.
This is going to be my source, destination and auxiliary for the time being.
I will ask my recursion that hey, can you move these n minus one disk from source to auxiliary such
that my auxiliary will have these n minus one disk, right?
Now once recursion has moved the same, I will just be left with this one disk.
I will just be left with this one single disk.
Now this single disk to move from source to destination.
It is very easy.
I can just directly move from source to destination.
That is how we handle single disk, right everyone.
And if you have done this now once I move this single disk as well.
Okay.
Once I move this single disk as well here, then what can I ask my question to do is that hey, now
you do not have to do anything, just Move all these n minus one disks.
Assume that this is source destination.
Is this only and you can take this source tower, the initial source tower as an X store auxiliary one.
So use this tower and move everything to D to the destination.
Okay.
I hope this is clear.
I will repeat it one more time so that it becomes a more clear and just another analogy.
So pay attention everyone.
Let's say you have n disk here.
Let us say you have n disk here okay.
For the time being this is your source.
This is your destination.
This is your auxiliary.
Now let us say I ask that hey, instead of destination, move everything to auxiliary.
I think you can do that easily.
You do not have any problem in that.
The destination and auxiliary.
Both are an empty tower for us as of now.
So all I am saying is that.
Hey, move this n disk directly to auxiliary using destination.
I think you can do that.
Should be fine.
Great.
Now let's say I had a disk here as well, which was inside the ground.
This was a N plus one, which was.
Inside the ground.
Now, of course, I have to handle the same as well, right?
This is the n plus one th disk.
So all I am saying is imagine with respect to n, because I know that n minus one might be a little
difficult.
The good thing that I have taught you PMI.
So there we used to take for k plus one and k exactly right.
So let us say you are doing it for n.
And then I found that okay.
Hey there is another disk here.
What should I do to it.
What exactly should be done is I can move this this particular disk here easily.
Right?
To destination.
Moving a single disk from source to destination is easy for me.
When I will do this.
When I will do this, nothing has actually changed.
This is still the largest disk.
I can put anything on top of it.
I do not have any worry.
I have just move a single disk.
So all the rules I have made sure that I am following now because you will have all of these n disk
here.
You will have all of these disk here and I will just draw it again once more.
Now, because on your auxiliary all the indices are there.
These indices are on auxiliary.
What you have to do is now again and it should not bother you that destination is having this big disk
because it is anyway an bigger disk.
So you do not have to worry because you are not.
You can put anything on top of it, right?
The condition is that bigger disk cannot be on top of smaller disk, not the vice versa.
So now I am just saying that hey, move this end disk, assume this is a source and this is the auxiliary
and move from source to destination.
Okay, just this is the understanding now.
I hope this is a lot clear everyone okay.
So now let me write the code and it will become more clear.
So all I am asking my recursion to do is all I am asking my recursion to do is that hey, take these
n minus one disk.
Take this n minus one disk, move them from source Okay.
Move them from source to auxiliary to auxiliary, but use destination as your auxiliary.
So this time source will go to source.
Auxiliary will be the destination.
But and destination is going to be the auxiliary.
So this is some smart thing which I am doing once this have been done, I know that all these n disk
have been moved to this particular tower.
Now I found one extra disk.
What I have to do for that I know I can just print this actually source to destination because I can
move my disk.
And now all I have to do is I have to ask recursion that hey, recursion, can you please make sure
that all the disk which you kept on auxiliary, okay, all that is which you kept from auxiliary, please
move them to destination and use source tower as a extra tower.
And actually this is done like this is all you have to do.
Okay, just let me correct the indentation because all this is inside.
Yeah.
And now this whole thing is done actually, so I can test it out as well.
See source to destination.
Source to destination.
Right.
Okay.
One second.
How is it?
Two times.
Okay.
I'm not.
I'm doing pass.
I have to return it.
Right.
For two.
Source two.
Auxiliary source to destination.
Auxiliary two.
Destination.
This is what we saw here as well.
Right?
For two.
Now let us see for three.
What I'm going to do is I'm going to just check the count because it's going to be a lot high.
Seven is the steps.
So let us run for three.
It's saying the number of moves for three disk is seven.
Okay.
Let us do it for four.
Let us just check the steps.
Okay.
It's seven.
Oh, sorry.
My bad.
We have to increase it.
It's 15.
Right?
So for four, it is going to be 15.
What I can do to check it, maybe I can have some step is equals to one initially.
I can just print step one as well.
Step as well.
Okay, so this will help us count easily.
Great.
And when I'm doing this, whenever I'm doing this, I have to make sure that step should be plus equals
to one.
When I'm doing this, step should be plus equals one.
Yeah.
Now it should work fine.
Uh, what's it saying?
Okay.
My bad.
Global step.
So scope of variables.
We have already learned about them.
See, 15 steps are there.
Right, everyone.
So I hope you are able to understand what exactly happened here.
You are able to understand what exactly happened.
Let me just remove this by default.
Separator is there.
So I don't need this.
See 15 steps are there.
Now I can run for five as well.
Now one thing is there.
It is a very heavy problem like four.
I think some use case of 50 or something.
It will take forever to run.
Okay, so there are 31 steps and this is going to be right again.
Please make sure that you understand the intuition.
Here we are making two of these recursive calls.
We have asked to do the asked equation to do our work in a different way.
That's why two calls are there.
Okay.
We are dependent on recursion two times this time.
So this is a very, very famous problem which we solved using recursion.
So that is why I made sure that I discussed this.
This should have made your horizon a lot more clear on recursion and how exactly it can be used.
So yeah, I think that should help.
Please make sure that you understand the same.
Let me just write one second.
Great.
Okay.
Cool everyone.
So I hope this was clear.
Please make sure that you see it once again.
If it is not, it is a little bit tricky, but I have made sure that I am explaining you with the best
visualization and steps possible by even connecting you to the PMI and taking for n plus one as well.
So try to write your code once again yourself.
Okay, without referring to this code which I have written and let us meet in the next video.
Thank you.