1
00:00:00,480 --> 00:00:07,950
The Tower of Hanoi problem is a classical problem where we can use recursion to come up with solving

2
00:00:07,950 --> 00:00:08,640
the problem.

3
00:00:08,640 --> 00:00:16,290
But in this video, let's try to think together about how can one identify that recursion is a good

4
00:00:16,290 --> 00:00:17,910
technique to solve this question.

5
00:00:17,910 --> 00:00:26,910
For this, let's think whether solving a subproblem can help us to solve the original problem.

6
00:00:26,910 --> 00:00:33,330
Now over here, for example, we have three roads and we have let's say n disks.

7
00:00:34,850 --> 00:00:37,310
What would be a subproblem for this?

8
00:00:37,340 --> 00:00:40,310
Of course, the rods are not going to change.

9
00:00:40,310 --> 00:00:42,560
Even for a smaller problem.

10
00:00:42,560 --> 00:00:48,860
The number of rods is going to be the same, but the number of disks is going to be lesser.

11
00:00:48,860 --> 00:00:52,970
So a subproblem could be having n minus one disks.

12
00:00:53,210 --> 00:00:56,570
Now let's say we have n minus one disks over here.

13
00:00:56,570 --> 00:00:59,120
So notice I've removed one disk.

14
00:00:59,120 --> 00:01:01,130
So we have n minus one disks.

15
00:01:01,130 --> 00:01:09,560
Now let's think whether if we could move these n minus one disks or if we had the solution to move these

16
00:01:09,560 --> 00:01:12,830
n minus one disks to the required to a required rod.

17
00:01:12,830 --> 00:01:19,700
Could we use that to solve the original problem, which is to move n disks from r one to r three.

18
00:01:20,810 --> 00:01:29,150
Now notice that if I could move the n minus one disks from this rod over here to this rod over here,

19
00:01:29,300 --> 00:01:30,590
it would look like this.

20
00:01:30,590 --> 00:01:30,800
Right.

21
00:01:30,800 --> 00:01:33,650
So I I'll have all the N minus one disks over here.

22
00:01:33,680 --> 00:01:42,410
Now if I could achieve this then I could just move this disk from rod one to rod three.

23
00:01:42,560 --> 00:01:47,840
And then these n minus one disks could just be placed on top of it.

24
00:01:48,080 --> 00:01:50,120
And that would help me solve the question.

25
00:01:50,120 --> 00:01:50,660
Right.

26
00:01:50,660 --> 00:01:58,400
So notice that by solving a sub problem I was able to solve the original problem okay.

27
00:01:58,400 --> 00:02:01,610
So again but there is an interesting observation over here.

28
00:02:01,610 --> 00:02:05,570
We are not moving the n minus one disks from rod one to rod three.

29
00:02:05,570 --> 00:02:08,480
Because in that case we would have all these over here.

30
00:02:08,480 --> 00:02:11,900
And then the biggest rod could not be placed on top.

31
00:02:11,900 --> 00:02:18,170
So again it's this question over here is not having something called optimal substructure, which is

32
00:02:18,170 --> 00:02:21,410
something that we will discuss when we discuss dynamic programming.

33
00:02:21,410 --> 00:02:24,440
Now, because it does not have optimal substructure.

34
00:02:24,440 --> 00:02:27,530
We cannot use dynamic programming for this question.

35
00:02:27,530 --> 00:02:29,480
But again this is just a side note.

36
00:02:29,480 --> 00:02:35,090
But over here we are just trying to identify that we can use recursion to solve this question.

37
00:02:35,090 --> 00:02:41,120
So we were able to solve the original problem by doing something about the subproblem.

38
00:02:41,120 --> 00:02:46,550
And hence we have seen that we can solve this question using recursion.

39
00:02:47,090 --> 00:02:53,990
In the next video, let's try to understand the approach which can be adopted to solve this question,

40
00:02:53,990 --> 00:02:58,070
and let's also develop the intuition behind that approach.