Next, we're going to look at a classic example of the use of recursion. There's actually a number of examples that are very much like this, that indicate the basic recursive structure that's often useful. One of these examples is our subdivisions of a ruler problem, where we want to print out the lengths of the subdivisions of a ruler, down to one over two to the n inches. So, we did a function like this that do not use recursion for small values of n, and we did over the loop. Here's the recursive solution to that problem. To print out, to create a ruler string for n, if a zero, we just return a space. Otherwise, we sandwich the integer n between two copies of the ruler function for n minus one. So, again, we can do these small examples and get exactly the same way as we got before. Of course, if we try a huge example, then there's not going to be enough space for that string. Because it's recursive, we get out of memory error of that form. But, it's a simple expression of this computation, which we can use for small values of n, which is sometimes what we might want to do in practice. But keeping that one in mind, first of all, let's look at the idea of tracing a recursive program to understand the structure of this computation, and then we'll look at another one that's similar but more interesting. So, what we use is and we can use this for any program that calls function, but for recursive functions, it's particularly useful. We're going to have a tree, so we're going to have a node for each recursive call and we're going to label that node with the return value after the children are all labeled because we don't know what we're going to return until our children have returned. So, if we call ruler four, it calls ruler three, it calls ruler two, it calls ruler one, ruler zero returns the space. Then, ruler one makes another call on ruler zero and that returns a space. When those are both done, then ruler one is going to return space one space. So, now, ruler two makes it's second recursive call, computes the same thing and then makes its return value which is one, two, one, with spaces in between. Then ruler three, and that's going to compute the same value in the same way and then we have ruler three. Now, we do the right half of the tree to get the second copy of ruler three. That's the second copy of ruler three and then we put those together to get ruler four. So dynamically, it shows us what's happening with the computation, and statically it shows all the function calls. It's a very natural way to visualize what happens in a recursive program. So, now, let's look at a classic puzzle called the Towers of Hanoi puzzle. This is a legend where we've got 64 discs of differing size. We have three posts and the discs are sitting on one of the posts from largest to smallest. So, there's a prophecy that says the monks have to move the discs to another post, but they have to follow some certain rules. When the task is completed, the world will end. The rules are, you can never put a bigger disk on top of a smaller one. So, you got to move them all over and follow these rules. You move the discs one at a time, never put a larger one on a smaller one. So, that's our question, what sequence do we move the discs? How do we actually do it? Can we generate a list of instruction for the monks to get the discs moved? Then, if we have that list of instructions, maybe we'll have some idea when the world will end. So, that's our practical problem, if you believe the prophecy. So, to make the instructions simple, we're going to use cyclic wraparound. So, all that means is we're always going to say either move the disc right or left. So, move right means, one to two, two to three or three going around to one. Move left means the opposite, it means one going around to three, three to two or two to one. So, always, we'll say move right or move left, and if you're at the left edge and you are told to move left, you go around to the right edge. So, now, our instructions can just be in the name of a disc, the neighbor post containing a disc and either an L or an R for right or left. So, what we're going to look at now is a recursive solution to this Towers of Hanoi problem. So, we have our n disc to move, and what we're going to do is recursively move n minus one disc to the left. That leaves the biggest disc still on the middle post. Then, we move that one to the right and then we move those n minus one discs to the left again and put it recursively and then we've accomplished the move of the whole pile. So, that's our recursive solution to the Towers of Hanoi problem. So, let's just see what it looks like for n equals three. So, we move the little one to the right, then the next one to the left and we move the little one to the right. Now, we've got the whole pile moved from the center to the left. Now, we move the big one over. Now, we're supposed to accomplish the task of moving those two discs to the left back onto the big one. To do that, first, we have to move the little one to the right. Then, the blue one to the left or cyclic wraparound and then the little one to the right again. So, we accomplish the task of moving the discs from the center pole over to the right pole using that sequence of seven moves. So, that's what it looks like for n equals three. Now, let's look at a code for printing out these instructions. So, just following that exact scheme, so to get the string of the moves to the end this is for n equals zero, we'll just return a space. Otherwise, we'll make the specified move for disk n which is either right or left, and then we sandwich that between two copies of the moves for n minus one. We move the pile will move one direction, when we move the disc, we move another direction. That's the entire code, recursive code to print out this list of instructions. The recursive program takes a second argument direction, which left if it's true, you go left, otherwise, you go right. Then, that's the direction that you move the big disc and then you move the pile of disc in the recursive call the other direction. Now, you notice that this is very much like the ruler program, it's just got the lefts and right added into it, but that's a complete solution that'll do the job and it will give that an exact set of instructions for three and we can do more. So, now, looking at the recursive call tree, it's instructive, it's the same as for the ruler function. Let's look at what the tree is and then we'll look at some interesting facts that it suggests. So, this is the same process that we went through for the ruler function, except that we're keeping track of the right and left, and switching directions at each level. So, let's look at what the tree looks like. So, that's the full instructions. Now, one thing that you noticed looking at this, is that disc one, for example, always moves right, disc two always moves left and so forth. Every disc always moves in the same direction. Then you can easily convince yourself of that fact. The other thing is that every other move involves moving the smallest disc to the right. When you think about it, if you just move the smallest disc, then the next move that doesn't involve the smallest disc, one of the two discs has to be larger. So, it's determined what the unique legal move is. You don't need the instructions, move the smallest disc to the right, then make whatever move is necessary. So, that's a very interesting insight that we can get by studying the recursive program. That happens on lots of occasions. We use a recursive formulation to understand the computation and then find a better way to do it. Now you've probably figured out that it's not too difficult to add sound to that, just play a tone according to the size of the disk. So, generate list of instructions for the monks? Yeah, we can do that. But really, the short form is that I wish you could write on this small, you could chisel on stone next to the pile, tell them what to do. So, the question now is, when might the world end? Well, for 64 discs, you need two to the 64th minus one moves and that's easy to prove from the recursive program. You have to actually also prove that there's no better way to do it, but anyway, we're fine. If you could do one move per second, it would be 5.8 billion centuries, until the world ends. If you have a really fast monks and you can do a billion moves per second, we still have 5.84 centuries. So, our world's not going to end for a while.
