The Tower of Hanoi problem is a classical problem where we can use recursion to come up with solving
the problem.
But in this video, let's try to think together about how can one identify that recursion is a good
technique to solve this question.
For this, let's think whether solving a subproblem can help us to solve the original problem.
Now over here, for example, we have three roads and we have let's say n disks.
What would be a subproblem for this?
Of course, the rods are not going to change.
Even for a smaller problem.
The number of rods is going to be the same, but the number of disks is going to be lesser.
So a subproblem could be having n minus one disks.
Now let's say we have n minus one disks over here.
So notice I've removed one disk.
So we have n minus one disks.
Now let's think whether if we could move these n minus one disks or if we had the solution to move these
n minus one disks to the required to a required rod.
Could we use that to solve the original problem, which is to move n disks from r one to r three.
Now notice that if I could move the n minus one disks from this rod over here to this rod over here,
it would look like this.
Right.
So I I'll have all the N minus one disks over here.
Now if I could achieve this then I could just move this disk from rod one to rod three.
And then these n minus one disks could just be placed on top of it.
And that would help me solve the question.
Right.
So notice that by solving a sub problem I was able to solve the original problem okay.
So again but there is an interesting observation over here.
We are not moving the n minus one disks from rod one to rod three.
Because in that case we would have all these over here.
And then the biggest rod could not be placed on top.
So again it's this question over here is not having something called optimal substructure, which is
something that we will discuss when we discuss dynamic programming.
Now, because it does not have optimal substructure.
We cannot use dynamic programming for this question.
But again this is just a side note.
But over here we are just trying to identify that we can use recursion to solve this question.
So we were able to solve the original problem by doing something about the subproblem.
And hence we have seen that we can solve this question using recursion.
In the next video, let's try to understand the approach which can be adopted to solve this question,
and let's also develop the intuition behind that approach.