Fun Python Project. Recursion and the Towers of Hanoi

what is recursion let's look at why it's important how it works and how we can use recursion and Python to solve the towers of Hanoi problem recursion is really important to understand because it can be a neat and elegant little trick to solve complex problems and it is used you know in lots of different places in computer science and data science so divide and conquer algorithms they are usually recursive so something like binary search that is a recursive way of searching through a list of numbers and in data science decision trees they are recursive too so it's as well that you understand them but they're also quite interesting and fun in the way that they work a recursive function is a function that calls itself so when you call the function for the first time and that function executes as part of the execution of that function it calls the function again from inside the function it calls itself let's have a look at an example the mathematical function factorial you know the one that's written with an exclamation mark that gives a nice introduction into how recursion works because it's quite a simple function so you remember factorial okay it's too calculated you take the number whose factorial you want to calculate and you multiply it by all the lower numbers so 3 factorial is 3 times 2 times 1 4 factorial is 4 times 3 times 2 times 1 a 5 factorial is 5 times 4 times 3 times 2 times 1 and so one way of doing that if we wanted to write a Python function that was going to calculate factorial we could do that by using a loop but a much better way or a more interesting way not always better because recursion can use more memory but a very interesting way of writing that is to use recursion and the way to think about that is if we want to calculate 5 factorial 5 factorial which is 5 times 4 three times two times one well that's just 5 times 4 factorial so if we were writing a function we could say take the number that you want to calculate whose factorial you want to calculate and multiply it by the factorial of the number below it so you could say that 5 factorial is just 5 times 4 factorial but then you have to calculate 4 factorial so there's a function called a 4 factorial but what's 4 factorial we'll 4 factorial in this function that we're creating is just 4 times 3 factorial and 3 factorial is just 3 times 2 factorial and 2 factorial is just 2 times 1 factorial but when do you stop you don't want this this function to keep going down by 1 you know to be trying to calculate factorials of negative numbers that's not going to work so this has to stop and it has to stop at the simplest version of whatever it is you're trying to calculate and that's known as the base case so whenever you're writing a recursive function whenever you're using recursion you have to know where the recursion ends what is that base case at what point do you stop and return a value and in the case of factorial this function that we're calculating here that's going to be at well I never know actually because 0 factorial is 1 so it could be at 0 I guess but let's for the sake of this let's call it 1 so 1 factorial is 1 right so you've probably noticed that the colors changed a bit on the screen and that's because I just noticed that the white balance hadn't been set up properly I did it before I started recording but then the battery ran out and when I changed the battery the white balance or reset so anyway it looks a bit better now what I want to do now is use Python I want to write a Python function to use recursion to calculate factorial and you'll see just how simple it is so this is how we'll do it let's start by writing the name of the function we will call it factorial and it's gonna take an integer we'll call that integer n now if N equals one that's our base case right so if N equals one we just return n so if N equals one we return one in every other case we return n multiplied by the factorials at this function that we're writing of n minus 1 now you could also put a check in there to make sure that you're not getting a negative number and you could do that but I didn't want to do that here I just wanted to show you how easy it was to calculate factorial using recursion in Python so in a room in a temple in Hanoi in Vietnam legend has it that there are three posts and on one of these posts are 64 disks and it's the job of the priests of the temple to move these disks according to a certain set of rules from one post to another post and once they complete that task the legend says the world will end so what I want to know is how long is this going to take are we in imminent danger of the world ending because this task is almost being completed now the truth is a little less mystical than that actually this is a puzzle that was created by a French mathematician in 1883 his name was Edward Lucas and he was famous for his work on prime numbers and this problem is related to prime numbers in a way that we will look at a little later on but this is a problem that can be solved using recursion and so what I want to do is I want to go over the rules of the problem with you and then I want to see how we can solve this problem using recursion and we'll write a function in Python and then count how many moves it would take to transfer those 64 disks from one post to another post and see how long if the legend is correct we have until the world comes to an end let's do that now so I have a little Tower of Hanoi set here we've got the three posts and on one of the posts we have five disks and the rules are quite simple you can only remove the top dish from a stack of disks so the only disk you can remove from any stack is the top disk and you can't put a large disk over a small disk so this would be an illegal move you can't do that you always have to put a small disk over a large disk and that's it those are the only rules there are so thinking about this recursively now what's the base case well the base case is when we have just one disk to move so if I take these five disks away and put them there for now and I just put one disk on that pose the base case is just moving that disk from one post to another post so now that we know the base case how do we use recursion to move just two disks what we want to do this time is move these disks from the source post to the target post how are we going to do that well we know the rules and we know the base case the base case is that we can just move one disk pretty much wherever we want it so why don't we do that here we could move this top disk out of the way so that we can move this bottom disk underneath where we want it let's try that so we'll move this disk out of the way we know we can do that that's the base case it doesn't break any rules and now we can move this disk to the target pose and now we just move the disk that's on the middle post to the target post and we have moved two disks from the post that we started from to the target post and that was quite easy and that really provides the key to move any number of disks so let's look at the case where N equals three now can we think about how we solve the two disk problem and apply that to three disks well with two disks we just move the top disk out of the way and then move the second disk to the target now if we were to do that with this we'd have to move these two disks because the bottom disk now has two disks on top of it we'd have to move these two disks out of the way to the middle post and then we move the bottom disk to the target and then we can move these two disks on the middle post back on top but that breaks the rules because we can only move one disk at a time but if we go back to this again and look at how we're trying to solve this we want to move these two disks out of the way so that we can move this disk to the target so we need to move these two disks here but we already know how to do that because we've move two disks before from the source to the target now we want to move these two disks out of the way so that we can move this bottom disk to the target but we know how to move two disks would have you've already done it so if we want to move these two disks to this this is the target now for these two disks well we just moved the top disk to the spare this is the new spare now because in this case this is the target we move the second disk to the target and then we move the top disk back and we've done what we wanted we've moved those two disks now here so that we can just move this disk across and then we need to move these two across to here but doing so two at a time breaks the rules but we know how to do this now this is a problem that we've already solved so we need to move this one here so that we can move this one here and so that we can move this one here and we've achieved our aim of moving the three disks from the source to the target and now N equals four applying the logic that we applied before and knowing the rules what we'd like to do is move these three top disks out of the way to put them in the middle so that we can move this bottom disk across where it needs to go and then move these three disks on top of that bottom disk on the target post and we've done the job so that's gonna be the approach but of course that breaks the rules because we're not allowed to move three discs at a time we want to move these three discs here but we can't do it all at once but we've already solved the case where you move three discs and we solve that by looking at the case where you move two discs and we could solve that because we knew how to move one disk so this is the recursion coming into play we want to move these three discs now to this one before when we just have three on this post here we wanted to move the three discs here but now we want to move these three disks out of the way onto this spare post so that we can move this bottom disc to the target post and then move the three disks on top of the bottom disk so now we need to move these three disks here and we know how to do that we've already solved that problem in order to move these three disks here we need to move two disks we know how to move to this but we need to move these two disks here and in order to do that we have to put one disk here and then we put this disk here and then we move this disk here now we've moved the two disks where we want them and then we can move out third disk here and now we just need to move these two disks back on top of this well again this is a problem that we've already solved recursively so we have to move the first disk out of the way and then the second disk goes here and then this disk comes back here and now we've cleared a space for this final disk here this fourth disk we can move that across just as we wanted to and now we can move these three on top of this but of course we can't move three at a time so we have to use recursion so now we want to move these two disks out of the way so that we can move this one across the bottom disk to here we have to move these out of the way but that breaks the rules so we have to go back to the base case and the base cases that we just move one and we move it there and then we move this one here and then we take this one and we move here and now we've moved the two discs out of the way we can put discs three there and then we just need to move these two back here now we've done this we've solved this already so you can see now how we're building up a recursive solution and we can go on and on solving it in that way just by taking as look at the case for N equals 5 we want to move the bottom disc here so that means we have to move these four discs across to here and then we can move this one across to here now of course that breaks the rules so what we need to do is we need to find a way of moving the four discs whoops we need to be able to move these four discs to here but we've already solved that problem we know how to do that and we do that by moving these three discs to here but we can't do that because that brings the rule so we need to move these two discs here but that breaks the rules and the answer is that we start by moving this disc here now I'm not going to work through this solution but you get the idea we now need to find a general way of expressing our thoughts so where we've been looking at the examples we've been looking at concrete examples where N equals two or three or four but we need to express this generally now so how do we do that for n well we have three posts let's call them a B and C and we want to move n disks from A to C now the way we're doing that is we're moving n minus one disks from A to B so we're moving all but the last disc from A to B we're then moving that last disc n from A to C and then we're moving those n minus one disks from B to C and that's how we can generalize what we've been doing in those specific examples so now we've generalized our solution we can write some Python code right a function that will be able to do this for us and it'll be able to count how many moves it takes to transfer the discs from one post to another let's have a think about how we're going to write this function we have this little visualization here we've got our three posts source spare and target now these are the generic names of these posts that are going to go into this function so this function has placeholders for the parameters that eventually will go into the function and these placeholder names these placeholder variables are source target and spare now the actual variables that will be going in here are these lists a B and C and in this case a is a stack or a list with five discs and B and C are empty and what we're going to be doing is moving these n disks from the source to the target now how do we do that we take n minus one disks that's the ones apart from the bottom one and we move these to the spare so that we can then move the nth disc to the target and then we have these n minus one disks here and we're going to move those across to the target so we've already started writing this function so let me just add to it now so if n is greater than zero we want to take this time the n minus one disks that are here and we want to move them from the source but this time we don't want to move them to the target we want to move them to the spare using the target as the spare this time that will move them out of the way when we've done that what we want to do next is we want to move this bottom disk from here to the target so the first thing we have to do is we have to get hold of that disk and we can do that by using pop in python pop will return the top of a stack or the last item of a list and so we have source dot pop so that works but we need to put that on the target and the way we can do that target is a list so we can append that target dot append the whatever's popped here from the source will then be appended to the target now I haven't kept this aligned properly this needs to be aligned in here like this but you get the idea so we've now moved this across so we've moved the N minus one disks from the source to the spare we've now moved the the bottom disc from the source to the target and now we just need to move the N minus one disks that are here we need to move them from the spare to the target using the source as the auxilary and that's it now Wikipedia has a really good explanation of the towers of Hanoi and I adapted the code that we've just seen from the code on the Wikipedia page so let's run this code now because we've sought to answer that question haven't we how long would it take those priests to move the 64 disks from one post to another post so here's the code that I have written and what I've done is I've created a loop as well so that it will run with varying stack length starting from one and going up to well only goes up to 25 because as you will see if you run this code yourself it'll cause problems for your computer because the numbers just get too big too quickly the number of moves required as we increase the number of disks goes from one to three then to seven then to 15 and 31 then 63 then 127 and that pattern should seem a little familiar because it's just one less than powers of 2 so powers of 2 are 2 4 8 16 32 64 128 and what we have here is 2 to the N minus 1 now these are interesting numbers they are called Mersenne numbers after another mathematician and some of these are prime numbers and it's a way of generating prime numbers and you can read up about that on Wikipedia but if you were to use 64 discs it would take approximately 600 billion years if those monks if those priests were moving one disk per second so take quite a long time anyway I hope that's helped you understand the towers of Hanoi when I first started studying computer science and programming I found the towers of Hanoi quite a difficult problem to understand well and I hope now if you practice go away and write that code yourself and don't look at it every night understand it and then go away and try to write it yourself and see if you can do it from scratch think about what the base case is what's the base case in that code that we've written which line is the base case and why and what's going on and try to think of the recursive calls as well as we go through the stack and that that function is called recursively and from inside the function those n minus 1 function calls what's going on there and why haven't we explicitly put if N equals 1 then do this how does the code that we have where we have if n is greater than 0 how does that account for the base case think about those questions and then go away once you've thought about them and my to recreate that code to yourself without looking at it and see if you can change it see if you can do two different way and also think about the data structure of the stack now the way this problem is set up the way the tales of Hanoi is set up it actually is a very good way for you to start understanding how stacks work I'm not going to talk about stacks in any detail here but it's a data structure that you should really know about and understanding this will really help you to understand what a stack is and how it works and if you've enjoyed this then go and check out my Python course on udemy it's a ten hour course or aimed at beginners now we cover this problem and other problems too and you know I think you'll like it

Channel: Python Programmer

Views: 31,213

Keywords: recursion

Id: buWXDMbY3Ww

Length: 22min 28sec (1348 seconds)

Published: Tue Feb 25 2020