1 00:00:06,550 --> 00:00:12,280 The last recursive example we're going to look at is the Tower of Hanoi. 2 00:00:12,760 --> 00:00:19,360 And you may or may not be familiar with this, but this is a game where you have three stands. 3 00:00:19,360 --> 00:00:25,690 This is stand, we'll say l four left center and right. 4 00:00:26,230 --> 00:00:37,630 And what this game is, is you want to get all the disk from stand l all the way over to stand R And 5 00:00:37,630 --> 00:00:41,080 there are a couple of rules you can only move. 6 00:00:41,840 --> 00:00:43,130 One disk at a time. 7 00:00:48,470 --> 00:00:50,750 And a larger disk. 8 00:00:54,620 --> 00:00:55,700 Cannot. 9 00:00:58,330 --> 00:01:02,800 Sit on a smaller. 10 00:01:04,490 --> 00:01:05,270 Disk. 11 00:01:05,870 --> 00:01:06,110 Right. 12 00:01:06,110 --> 00:01:07,520 So we have two rules here. 13 00:01:11,090 --> 00:01:18,680 So what we want to do is get one, two, three, four in this order all the way over to one, two, 14 00:01:18,680 --> 00:01:19,280 three, four. 15 00:01:19,310 --> 00:01:20,120 Over here. 16 00:01:20,270 --> 00:01:27,290 So we quite literally want to replicate it to three. 17 00:01:28,400 --> 00:01:29,720 And then four. 18 00:01:29,750 --> 00:01:30,140 Right. 19 00:01:30,140 --> 00:01:33,800 So we want right to eventually become left. 20 00:01:35,300 --> 00:01:43,160 So for us to do this, we can start over here. 21 00:01:49,090 --> 00:01:51,820 And we can say that this is block in. 22 00:01:52,480 --> 00:01:52,990 Right. 23 00:01:52,990 --> 00:01:57,850 And then we also have so this is left center. 24 00:02:00,460 --> 00:02:00,760 And. 25 00:02:00,760 --> 00:02:01,360 Right. 26 00:02:03,980 --> 00:02:10,760 So these are always going to be in minus one because once we get this in over here. 27 00:02:11,720 --> 00:02:13,820 Now the block above it becomes in. 28 00:02:14,630 --> 00:02:23,840 So step one for us is going to be get these three blocks right here into the center, right, because 29 00:02:23,840 --> 00:02:28,130 this is a a helper stand for us. 30 00:02:28,130 --> 00:02:32,000 So we want to get these three blocks to the center. 31 00:02:33,590 --> 00:02:42,410 And now when we have those three blocks in the center, we're going to take our in and plop it over 32 00:02:42,410 --> 00:02:43,100 here. 33 00:02:43,100 --> 00:02:45,530 And that's always going to be step two. 34 00:02:45,830 --> 00:02:53,750 Take this in block and bring it over here, because now that is our biggest block and we now have it 35 00:02:54,170 --> 00:02:55,130 over here. 36 00:02:57,350 --> 00:03:03,650 And so now that we have these three blocks over here from our first step. 37 00:03:07,640 --> 00:03:16,130 We now have to get all of the N minus one blocks over here, and that is step three. 38 00:03:16,520 --> 00:03:22,580 So what you're seeing is a little bit of a pattern of in minus one. 39 00:03:23,900 --> 00:03:27,970 This account is one and then in minus one again, Right. 40 00:03:27,980 --> 00:03:35,270 So what our function is going to try to do is count how many steps it takes to get these blocks from 41 00:03:35,270 --> 00:03:36,980 the left to the right. 42 00:03:38,480 --> 00:03:44,000 Well, so we can have our function and we see that we have n minus one steps. 43 00:03:45,650 --> 00:03:51,380 So now we can do our recursive call of the function of n minus one. 44 00:03:52,130 --> 00:03:59,300 And then we know we always have one for sure step right here at step two, because this end block is 45 00:03:59,300 --> 00:04:01,100 going to go all the way over to the right. 46 00:04:03,140 --> 00:04:08,090 And then we also see that we have in minus one from the center. 47 00:04:08,390 --> 00:04:13,580 So we can say F in of N minus one from here. 48 00:04:13,760 --> 00:04:21,650 And simply put, this right here is going from left to center. 49 00:04:22,520 --> 00:04:26,450 This right here is step two. 50 00:04:27,770 --> 00:04:32,960 And then this right here is going from center. 51 00:04:34,390 --> 00:04:35,410 To the right. 52 00:04:35,440 --> 00:04:35,890 Right. 53 00:04:35,890 --> 00:04:36,970 So step three. 54 00:04:37,330 --> 00:04:40,510 So step three, Step two and step one. 55 00:04:41,710 --> 00:04:43,510 So these two. 56 00:04:45,380 --> 00:04:49,340 Calls are going to be our recursive function calls. 57 00:04:49,430 --> 00:04:57,860 So now we have a general idea of how this needs to look, and we can implement this recursively using 58 00:04:57,860 --> 00:05:05,480 the function return value that we have established right here. 59 00:05:07,460 --> 00:05:16,820 So if we come over and I created a function called TIO for Tower of Hanoi, we're going to have a number. 60 00:05:18,140 --> 00:05:25,730 And this is going to be how many blocks we contain, and then we're going to return an integer of type 61 00:05:25,940 --> 00:05:33,680 32 because we want to see how many steps it took to get from the left stand all the way to the right. 62 00:05:33,980 --> 00:05:41,600 So our base case is if N is equal to zero, then we want to return zero because there is nothing for 63 00:05:41,600 --> 00:05:42,320 us to do. 64 00:05:43,250 --> 00:05:46,460 Otherwise we're going to return that. 65 00:05:47,370 --> 00:05:50,310 Formula that we found where it is. 66 00:05:50,550 --> 00:06:01,860 N minus one for step one, plus one for step two, and then in minus one, again for step three. 67 00:06:04,560 --> 00:06:11,430 And now we can come down here and we can print out a couple of tower of 68 00:06:14,370 --> 00:06:15,040 inputs for. 69 00:06:15,060 --> 00:06:21,630 So again, we want to test out zero and we expect zero to be returned. 70 00:06:23,550 --> 00:06:28,830 We'll test out one and we expect one to be returned. 71 00:06:31,140 --> 00:06:36,060 We'll test out two and we would expect two to be returned. 72 00:06:36,810 --> 00:06:41,150 And then we'll test out three and see what gets returned there. 73 00:06:41,160 --> 00:06:44,250 And then lastly, we'll also test out for. 74 00:06:46,950 --> 00:06:52,560 And we see we have zero one, three, seven and 15. 75 00:06:53,540 --> 00:06:55,370 So we can actually evaluate. 76 00:06:56,680 --> 00:07:00,460 Blocks two and three pretty easily ourselves. 77 00:07:00,460 --> 00:07:01,810 So let's go ahead and do that. 78 00:07:01,810 --> 00:07:06,640 That way we can validate our results and make sure that our function is working correctly. 79 00:07:07,150 --> 00:07:08,680 So if we come down here. 80 00:07:10,820 --> 00:07:16,940 And we will say for this case, our test in is equal to two. 81 00:07:17,660 --> 00:07:18,590 We have. 82 00:07:19,350 --> 00:07:21,330 One, two. 83 00:07:22,420 --> 00:07:23,020 Three. 84 00:07:24,010 --> 00:07:25,750 So we have one. 85 00:07:28,360 --> 00:07:33,340 So we're going to move this block here, right there. 86 00:07:33,700 --> 00:07:34,960 So that is one. 87 00:07:35,470 --> 00:07:36,700 So now we can. 88 00:07:38,690 --> 00:07:39,560 Remove. 89 00:07:41,110 --> 00:07:43,090 At block because it is here. 90 00:07:43,090 --> 00:07:49,870 So let's just label them to keep them simple A and B, So now we're going to move A over here. 91 00:07:52,810 --> 00:07:53,940 And that's another move. 92 00:07:53,950 --> 00:07:55,450 And then we will move B. 93 00:07:56,320 --> 00:07:57,220 On top of it. 94 00:07:58,510 --> 00:08:03,010 So our output of three four in equals two is correct. 95 00:08:04,850 --> 00:08:08,080 Now if we do test in equals three. 96 00:08:10,490 --> 00:08:13,370 We will do the same thing where we go a. 97 00:08:14,570 --> 00:08:15,320 Be. 98 00:08:16,760 --> 00:08:20,150 See have our. 99 00:08:21,680 --> 00:08:22,490 Walks here. 100 00:08:22,910 --> 00:08:24,950 So we will move. 101 00:08:24,980 --> 00:08:25,970 See? 102 00:08:27,430 --> 00:08:28,390 All the way over. 103 00:08:29,240 --> 00:08:39,170 We will move, be all the way over and then we will take C and put it back on top of B so we can get 104 00:08:39,170 --> 00:08:44,270 rid of that and we can get rid of that and now we can move a. 105 00:08:45,230 --> 00:08:46,220 All the way over. 106 00:08:47,150 --> 00:08:48,890 So we can get rid of a here. 107 00:08:51,710 --> 00:08:56,750 And now we have C here, which means that we can remove. 108 00:08:58,630 --> 00:08:59,590 See from here. 109 00:09:02,610 --> 00:09:04,380 We can now put be here. 110 00:09:05,380 --> 00:09:07,210 And we can now put see here. 111 00:09:07,900 --> 00:09:10,090 And we successfully moved it over. 112 00:09:10,300 --> 00:09:16,780 And that was seven moves, just like our program outputted. 113 00:09:17,230 --> 00:09:24,550 So we can see that we do have a correctly functioning Tower of Hanoi recursive function. 114 00:09:25,270 --> 00:09:31,440 So that concludes all of the recursive examples that I'm going to show you. 115 00:09:31,450 --> 00:09:38,860 If you have any questions regarding recursion, please ask them in the Q&A section and I will respond 116 00:09:38,860 --> 00:09:46,390 to you very quickly to provide you with clarification as to what your question might entail.