ProgrammingAbstractions-Lecture09

Instructor (Julie Zelenski):Hey. Good afternoon. Assignment two coming in today so hopefully you brought some paper copies and did some E-submits and are ready to immediately take on your next assignment. Thereís no rest for the weary in this class. My understanding is that Miron calls the version where we just chat about some of the assignment the pain pole. I think thatís really just much too negative and Iím gonna call it the joy pole instead, and Iím interested in getting a little bit of feedback on how much joy you had in doing your last assignment. First, letís just do the quick counts of time spent.

How many people think they managed to get the whole thing done in less than 10 hours? All right. Thatís a few of you. Thatís very good. Very good. Ten to 15? Kind of more of my target range, right, and so that looks like a big healthy chunk in there. Fifteen to 20? Okay. A little bit smaller and then more than 20? Anybody willing to Ė maybe not. Hereís another question, which is how many of you think Ė so thereís two halves, right, the random writer, the maze generating and solving, how many of you think you spent more time or found it more difficult or more time consuming to get the first one done, the random writer than the maze? How many people thought the maze is where you spent your time? Yeah. And of the maze part, how many thought it was harder to generate the maze than to solve the maze? A little bit. How many thought it was harder to solve the maze than generate the maze? Okay. So it looks like solving the maze may be where it comes down to taking the biggest chunk of joy was spent. Okay. Good to know. Hopefully one of the experiences or one of the take home points right after the end of that was certainly that templates provide a lot of leverage. Having these container classes, you can get a lot of things done; write these sophisticated programs with a small amount of code.

I saw a lot of people write who had a comparison function that just did not reliably compare things, all right, for example did not order them. The set really needs to know ordering and whoís first, whoís last, whoís in between because thatís how it stores them to later look them up. If your comparison function is not reliable, if you pass A and B and itíll say oh, A is less than B and if you pass B and A, itíll say B is less than A, right, you have a total inconsistency in your system, which the set will then make a hash of, right, itíll throw things in places that it doesnít look later because it took your word at it when it said it should go to this side or that side and it wonít find it when it goes looking for it this next time so you do really have to have an ordering function thatís reliable that every single time you pass it, itís the same things.

No matter which order they are, theyíre gonna tell you the same truth about their relative positions. Thatís one of the lesson learned from that. Assignment 3 is going out today and assignment three is basically a problem set. There are six problems on it. Each of them requires one recursive function and in a couple cases, a little tiny bit of support code around it. Those recursive functions are short. Typically, 10 lines at most. Some of them, six or seven in some of the easier ones. But that code is hard one. Right. You wonít find those lines easy to knock out the way you could write out four loop and be done with it, right; there really is some thinking and careful planning and doing the recursive thing and getting your head around it. So it is a small amount of code, but a very dense and complicated bit of code to generate so hopefully you will start that one early and give it time to gel because sometimes I think youíll see the problem the first time and not see the recursive insight. A day or two later, it will start to make more sense to you, but if you try to compress that all into the night before itís due you may not have enough time to let everything come together well. It is really important to get recursion started now. This is gonna be the recursion problem set.

The next problem we will do is the big venerable boggle that has recursion at the heart of it, plus a lot of other things going on so if you donít spend the time this week getting your recursive footing right, itís gonna start to snowball because recursion shows up from here all the way out through the quarter so this is the time. When youíre working on this homework, be sure to get the help you need to make sure the concepts start to come together for you because this is kind of a key to doing well in the rest of the quarter.

So today Iím going, Iím talking about [inaudible] recursion. This is kind of corresponding to reader chapter five. I will do a bunch of examples today that kind of get at this idea with different domains. And then we will go on to recursive backtracking which is the topic from chapter six for Friday. We wonít cover the later sections of chapter six. Weíre mostly gonna focus on the first two sections. There is a later section about game playing and strategy and stuff. Itís very interesting and itís worth reading, but we wonít formally cover it and use that material in this course right now. Okay. So kind of remind ourselves about thinking recursively and where weíre trying to work out way toward.

Recursive [inaudible] is really the hard part. Somebody gives you a problem and they say solve this recursively, where are you gonna find you spend your time is saying, well, given this problem how can I find that self similarity in it, how can I break it apart in such a way that a smaller form of the problem within, right, if I made that recursive call and then used it was gonna solve the whole problem for me. Maybe thereís more than one solve problem, maybe itís a divide in half, something like that, but that part is usually where youíll spend a lot of your time is trying to figure out how it is you can structure it to divide it in a self similar way. Once you have that plan about how youíre getting a little bit smaller, a little bit simpler, itís usually not so hard to follow that to the logical conclusion and say well, if I keep doing that enough times, what do I get to that will really allow me to terminate this, the simplest possible case that all of those, you know, minimizing of the problem might eventually lead to something so simple we can directly solve it that weíre working toward. Sometimes thereís more than one base case, but ideally, thereís exactly one that everything comes to. It kind of cleans up your code if you can make it come out that way.

Thereís a couple common patterns and weíve seen some of these already and weíre gonna see them again and again, but partly what youíre trying to develop is a set of examples youíve seen before that help you to kind of use those patterns to explore further problems in the future and so a very common way of dividing stuff is you have some collection, whether itís a vector or a string or a set of paths or something like that that part of the recursion often is that you somehow separate one from them so when we were trying to choose the people to go to the flicks, right, we picked some student at random and said okay, this student is either in or out and so we separated one from the mass, leaving us an N minus 1 and then that N minus 1, right, was that recursive piece about that substructure saying, well, if I had the answer for the remaining N minus 1, right, I could use the information about this 1 Iíve separated out to join it together. So sometimes, thatís the first person, sometimes thatís the last person. Sometimes itís almost a random person that youíre picking, but the idea of separating one or some small number leaving the N minus that number to work on. Sometimes itís a bigger chunk, itís a division in half or in thirds or something where Iím dividing and conquering the binary search doing that saying. Weíve got some information from the middle that tells us about what these two halves are in the case of binary search, we only do recurring one.

Weíll see some cases weíre actually able to divide it in half and recur on both, but where weíre still just dividing the problem in easier, in this case, half as big versions of the same problem, but then we can attack recursively. And sometimes thereís more like a choice. This is maybe the thematic thing for some of the later things when [inaudible] is that thereís some choice of the options that remain and the recursions that attack it to make it one of those choices, which then kind of leads you to a state that has fewer choices to be made, fewer decisions and allows you try decisions from there to work your way to some base case. One of the things Iím also gonna be talking about today is some of the implications of the relationship between when you process this part youíve separated out and when you make the recursive call. But itís actually totally not irrelevant whether I make the recursive and then try to process the one, or whether I process it and then do the recursion. In some situations, theyíll produce different results and different answers that are interesting to know about how those things play out. So today, the theme is procedure recursion and procedural is differentiated from functional in a very minute almost a bit semantic about the definition, but itís worth telling you.

A functional recursion problem is one where you have a function returning an answer like is [inaudible] true/false. The factorial is a raised power telling you what the answer is. In a procedural recursion, we have functions that donít return anything so thereís not an answer being computed in result of that, but there is recursive in [inaudible] so thereís a procedure here that calls itself eventually bottoming out at some base case and as a result of all that recursion being done, something happens. The one Iím gonna do at the beginning here is some drawing pictures, some graphics that draw fractal graphics where thereís not an answer being computed, but thereís something being illustrated on the graphics window. So Iím gonna look at two examples of this because I think sometimes for some students the numbers and the strings arenít the best way to get it; sometimes visually really helps to open up the enlightenment for what recursion means in terms of the structure. Weíre gonna look at some pictures that have a self similar structure that repeat within itself that you if you look at it at one level of detail youíll see certain elements that, actually, if you look a little closer, youíll see that same element, but just repeated on a smaller scale within that and then within that again kind of moving down to that base case.

The way these things that weíve written in code will give us some outer fractal that you draw that is part of its handling then makes recursive calls to draw these inner, smaller versions of the fractal within itself. Okay. So here is a little bit of code. So Iím not gonna tell you what it goes, but weíre gonna sort of just imagine thinking it through and looking at this to see what kind of things it could produce. Draw fractal, letís give it an X, Y in width and height, which Iíll assume is the bounding rectangle of whatís being drawn and then it makes a call to some helper called draw triangle. If I assume that does what it seems like it does it says oh, it draws a triangle, right, thatís inscribed within that rectangle. Next up Iím seeing this base case thatís, like, well, if that triangle was particularly small, in this case, two tenths of an inch or smaller in either dimension, then we donít do anything further with it. We leave it alone. Otherwise, we do a little bit of computation here, a little bit of math to compute some coordinates and theyíre labeled the left, top and right, which is basically itís making a call on the left sort of sub region of this rectangle thatís at the lower left corner, but half as tall, half as wide. Hereís one that starts in the middle and is also half as tall, half as wide that represents a chunk out of the top, and then one thatís to the right.

This produced something youíve seen before, but you generated it a very different way last time. Right. In assignment one, we had you do the chaos demonstration, it produced this drawing, which is due to Sirpinski from a different mechanism, but in fact, it is a very recursive drawing when you look at it. Right. Thereís this outer triangle and then within it, there is a left most, a top most and a right most reproduction kind of the outer triangle at a smaller level of scale. If I look in each of those triangles, would I see that same self-similarity? If I just keep going down at each level of scale, I see the same thing, that thereís a triangle which itself has these three left, right, top regions that exhibit the same structure the outer one did, but just a little bit smaller. It eventually gets so small that it stops drawing and thatís what terminates our recursion. So that is one of the aspects weíll be looking at. Okay. I did the work first. What happens if I turn it around so I have the same base case right and the same order of left, top, right here, but I wait to draw the big triangle until after Iíve drawn all the other interior fractals so doing the processing for this one after Iíve done those. Iím gonna get the same picture, but itís gonna grow in a different way that only Iíve done the whole thing is the outer triangle; in this case, drawn on top which isnít actually very noticeable because the inner piece is kind of already made up the outer boundaries anyway.

Student:

Can you go slower?

Instructor (Julie Zelenski):Yeah, I slowed this one down a little bit. It isnít any slower in real life. I was kind of screwing with the pausing because I wanted to get it just right and then one of the pauses I think the pause is slightly faster than the other. But growing right from that lower left corner up then working all the way through the top and then all the way through the right and then the outer most something only being built is an after effect of once the inners have been constructed, so the very first one appearing way down here. Now, let me change my three recursive calls. It currently goes left, top, right. Iím gonna change the code to go top, left, right. Iíll get the same picture, but where is the very first triangle drawn? Is it small or big? Itís small and where does it live within the triangle? The very, very top, right? So the top most pointÖthe top small little triangle, it goes there. What is the second triangle thatís drawn? The one thatís just down to the left of that one so I should see the top most one, itís left most neighbor and itís right most neighbor and then weíll start working our way down from there. One thing that is sometimes helpful to think about in terms of visualizing what a recursive procedure is doing is to think of it as a kind of an upside down tree where hereís my draw fractal to the outer one and then it makes these calls, right to top to left to right.

Realize that the way that the recursion proceeds is that it makes the call to the draw fractal of top, which then makes a call to the draw fractal of its top, which makes the call to the draw fractal of this top so it goes deep, right, until it hits that base case and so this was where I went top, top, top, top, top, top, top, right to the very top most one. Well, after it bottoms out here, it comes back to this one that said, okay, well, I drew the little tiny top, now, I need to draw the left and the right and so the ones that are fleshed out at the bottom here are the left and right of the top most one. And after those, it kind of comes back.

So sometimes thinking about it in terms of a tree and realizing that it is not sort of level by level or [inaudible], itís not like it draws all the outer ones and then the inner side of that, it really goes all the way down to that base case before it start unwinding and backing up and revisiting the pieces that kind of deferred as part of the recursion to come back to. So the very first call to draw fractal is sitting on the stack frame while all these other ones are active and when they finish their work and unwind, it picks up where it left off in drawing the other two thirds of the fractal. So this one should grow down from the top from there and then it should start to go to the left also from the top working its way down and then once itís worked out the whole of the left, do the right also from the top working its way down. So same picture in all these cases, right, am I doing the big triangle first, the inner triangle first, the left, the top, the right, but they show you that kind of the processing and how it would evolve is different. In some cases, this is gonna really matter to us. Itís gonna actually change the outcome of the recursion how weíre doing this so itís good to have a little bit of an idea how to visualize the different tracing through the calls. Any questions?

Student:Is it possible to draw by joining in three different places at the same time? Instructor

Well, I mean, [inaudible] control, right, and so at any given point weíre doing one thing at a time, so really without more fancy things, the answer is basically no. Let me show you more little recursive fractal. And this is based on a famous Dutch painter Mondrian, right, who was alive in the first half of the 20th Century there, one of the Cubists, the group he belongs to, and youíve probably seen some of these paintings. They might look familiar to you with these very bright primary colors, a lot of horizontal and vertical lines bisecting the canvas and then some of those squares being filled in with bright colors. This is sort of one of the more famous of the pieces that he did.

And his little philosophy I quoted from there, right, was this idea that this is about harmony and beauty and you can just through lines and colors produce things that really have an aesthetic component to them. I think itís a pretty neat thing. But Iím not an artist, by any means, so I think the solution to that is if I want to create beautiful things I need to write computer programs that do them for me because if it was up to me, I wonít do it with my own hands. So what Iím gonna show you is a technique for thinking of this as a recursive problem. If you look at what a Mondrian is and if youíre sitting down to start this, you have a big canvas in front of you. It starts blank and you say, well, where should I begin? Well, let me just pick a random direction, horizontal or vertical, and then Iíll pick a random placement for it so I decide Iím gonna bisect vertically and I pick a spot somewhere in the middle of the thing and then I do a bisection of that with my big black line and now I look at the thing that I have left and Iíve got well two smaller canvases; one to the left of the line, one to the right, which themselves I could imagine using that same strategy for. Well, look at it and decide whether to make a horizontal or a vertical line and then, occasionally, along the way decide to throw in a little color so when I have a canvas maybe wash it in red or blue before I go through my division.

And sometimes, I decide not to divide it at all. So this canvas that Iíve sectioned off here, I might just decide to leave it there and say, okay, thatís good enough. I donít want to go any further on that one. Thatís not what I wanted to do. So it has these three options, divide the canvas horizontally, divide it vertically, do nothing and then when I have those two smaller canvases, I recursively can apply the same kind of Mondrian style affect to it and when I get to something thatís too small, I can stop trying to divide it further. So Iíll show you what the code looks like here and then Iíll show it running to you. Most of it actually is a little bit gunky just because thereís a little math of adding and moving and stuff like that around, but it has this idea of oh, hereís the rectangle youíre trying to draw a Mondrian in. If itís too small, in this case, anything under an inch I decided was too small. Otherwise, I fill the rectangle in the random color, which often, is white, sometimes yellow, sometimes blue, and then based on three cases of a random choice, I either decide to just leave it as is filled with whatever color I chose or I make a line, vertically in this case or horizontally in that case, and then recursively section off the two portions Iíve made to recursively apply a drawn Mondrian to draw some more Mondrian in those pieces.

Does it work? Any by work, the code works, but does it actually produce art? You can be the judge. Now, the good thing is see itís easy to make new ones if you donít like that one. I donít like that one either. A little too much blue. Thatís getting somewhere. I might put that on my wall and then at this point, I just started making them just as many as you want and just keep going. Some of them it stops early, it has nothing to do. My mother-in-law is an artist and I feel like I have to apologize to her whenever I do this because Iím really not trying to make fun of art as though actually a computer can do anything. The truth is, when you do this actually what you realize is that itís not art, right, whatís truly aesthetic is something that actually is not generated by randomness and recursion, but itís still interesting how [inaudible] have that pattern to them that are sort of Mondrianesque just by simply taking this recursive strategy and saying thatís a little Mondrian, this is a little Mondrian and if you assemble them all together, youíve built a big Mondrian. Millions of dollars right here Iím generating. I tell you, when I retire from teaching, thatís gonna be my next career, turning out fake Mondrianís. All right. So any questions about little pictures and graphics and things?

Student:On the previous one, could you go over whatís passed in each of recursive or draw a Mondrian?

Instructor (Julie Zelenski):Yeah. So the only thing it takes is itís just a rectangle. It says, this rectangle you should fill with Mondrian like things, so the outer rectangle is the whole canvas and then once Iíve done a bisection, right, Iíve picked some point in the middle, Iíve divided the rectangle into two smaller rectangles, the left and the right. Itís not necessarily exactly, but I have one that starts in the origin and goes to the midpoint, one that starts in the midpoint and goes to the right side and so itís just basically taking the outer rectangle and dividing it. If I drew a picture here, it might help. Youíve got this thing.

You choose to bisect this way and so what youíre passing, is this rectangle and that rectangle, and when this one decides to bisect this way, then itíll pass this rectangle and that rectangle and so at each stage youíll have these smaller rectangles that were pieces of the outer rectangle that youíre continuing to draw Mondrian into and eventually they get so small that you say I wonít further divide that up anymore. Iíll just stop right here. And so the line actually is drawn on the way down it turns out. If youíll notice, the draw black line happens before it draws the thing, so draw the line and then draw a background on top around it and stuff. Either way it doesnít actually really matter. You could draw it on the way out and youíd end up with the same picture. If just would appear differently.

Student:Explain why you havenít returned something, like, a break or some other leads?

Instructor (Julie Zelenski):Well, in general, I just need something that says donít go through the rest of this code. Iím not trying to get out of a loop or a switch statement, right, so if I really want to leave the function, return is the quickest way to do that. The alternative is I couldíve inverted the sense of this task and said, well, if itís at least an inch wide and an inch tall, then get into this code and effectively it would say if, and it didnít pass if you didnít put a drop in the bottom and falling off, but either way, right. So I think I probably tend to prefer to do it this way just because I like to get my base case up from the front of my eyes seeing what it does and, typically, the right thing for the base case to do is identify that youíre at the base case, do whatever simple processing is required in that case and then return the answer or just return right away saying, Iíve handled the base case and now let the rest of the code be and now in the recursive case going on.

This is very much the style I tend to use. If weíre at the base case, do the base case stuff and return. Now Iím gonna hit you with the most classic recursion example known to all cs students worldwide. I wouldnít be doing my duty if I didnít teach you a little bit about the legend of Brahmin and its towers and how relevant it is in todayís world that you know how to move graduated discs around. All right. So Iíll give you the set up. Apparently, there are these monks and thereís a legend of the tower Brahmin that these monks, apparently, big troublemakers, monks, you know how they are, you gotta keep them out of trouble so the dyad here had this idea. Well, Iím gonna give them this task thatís gonna keep them busy for a long time and that way they wonít be causing problems. So what he did was he stacked up these three spindles, A, B, and C, big poles and he had these big heavy discs, they were made of solid gold apparently in the Brahmin religion and they are graduated so the big disc at the bottom and a slightly smaller one on top and then so on, and theyíre all stacked up letís say on tower A. Iíve labeled them, A, B and C just to keep track of which is which, and the dyad says yeah, I got all these discs all stacked up on this in A, but it turns out Iíd really much rather have them on tower B.

Sorry. What can you do? I accidently put them there and Iím so strong and big and heavy I could move them, you on the other hand, right, puny little human beings that you are, are restricted to being able to only move one disc at a time because they are so inordinately heavy that it takes everybodyís strength to move just even the smallest of the discs from one place to another. And he further in states these rules that the discs all have to live on a spindle so you canít actually just pick them up and start throwing them around in the desert. Youíre trying to move this whole tower from A to B. You can move one at a time. And in addition, because theyíre so heavy, if you were ever to put a small disc on a spindle and put a larger disc on top it would immediately crush the one underneath it. So thatís disallowed as well. So you always have to keep an ordering of large ones on the bottom to smaller ones on the top. All right. Thatís the deal. Thatís the set up. Those trouble-making monks. Apparently, thereís 64 of these things. All right. In computer science, I donít have any solid gold heavy discs, but I do have some very brightly colored plastic discs. So this is not so much the towers of Brahmin or the towers of [inaudible], I changed locations somewhere along the point of history; this is the towers of Fischer Price.

I did not actually steal these from my children, but they have one at home, which I keep waiting to see them show evidence of their recursive nature and I must say very, very disappointing. Okay. So Iíve got a tower, in this case, of six. This is A, this is B, this is C and I want to get this from here to here and I donít want to violate all those rules. I canít just start throwing the discs around and making a mess. I have to move it from here to here. I donít have a lot of choices here, but once itís there, for example, this yellow guy canít go on top of it because it would squash it, right? So I could kind of move yellow in there, so thereís something a little bit about this idea that somehow thereís gonna have to be some back and forth that is a part of whatís going on. So letís go back and look at this for a second. So as I said, many of your classic recursive patterns involve sort of looking at the problem you have at hand and trying to decide is there some way you could separate it a little bit and one of the more likely ways to do it is say is there some way I can move one disc out of the way leaving N minus 1 that could be worked on recursively? Okay.

So itís probably not likely that Iím gonna be able to get, letís say the blue disc out of the middle very easily, so it seems like probably the two most likely candidates for that are either the top most disc somehow gets moved out of the way to uncover the bottom part or the bottomless one, somehow I get this other tower out of the way. So letís start by thinking about the top one because thatís certainly the easiest. I can get this top guy, as I said, and stick it somewhere. Well, letís say I put it over here in the temporary one. Okay. I get it out of the way and now I have the tower of N minus 1 left. Okay. That seems like itís kind of getting me somewhere and now I need to move that tower, N minus 1, over here, but the situation I made is Iíve actually made the problem, not easier in the situation, itís a little bit smaller but itís actually further complicated by the fact that given this small disc is over here occupying the small spindle means that, suddenly, this spindle is out of commission. So the purpose of moving this spindle might as not exact, right, because this guy is blocking anybody from getting there. So it seems like I have a problem that looks what I started with, but itís not actually any easier, in fact, it actually got a little bit harder. So let me back up from that.

Let me just let that be a dead end for now. What about this purple disc that is down here on the bottom? Iíd like to get to the purple disc. Well, I canít just pick up the whole tower and move it, or can I? Well, letís think. Iíve got this tower of N minus 1 on top of the purple tower. If I were able to produce a delegate, a clone, a co-worker, right, who I could say, Hey, by the way, you know how to move towers, could you please move the N minus 1 discs that are on top of the purple one over to the temporary spindle using this other one as the spare? Well, thatís kind of interesting. So if I could move that N minus 1 out of my way and over to that temporary spindle, then it would uncover this bottomless one which then is one step away from where it wants to be; it wants to move to the middle. So this is really where recursions are kind of buying us a lot of the heavy lifting. I want to get this tower from here to there. Thereís all these rules. Itís very complicated. I canít think about it, it makes my head hurt, but if I just believed that I was in the midst of solving this problem that I havenít yet solved and if I had that solution and I believed and I had faith, right, and I believe that it will work, I move these guys out of the way, I move this over here, I move it back.

So letís see how much I can do without blowing it. All done. Donít ask to see it again. Iíll show you a little code. Iíll show you the code. Tiny, tiny little piece of code that solves the whole problem. Iíve got a [inaudible] coming in here, which is the height of the tower to move and Iím identifying the source destination attempt, the three spindles that are currently in play here with these letters, characters; if thereís something to move Ė so Iím gonna talk about the base case in a second, but in the general case where Iíve got five things to move it says move the four discs that are on the source. So the source, letís say is A in this case, and now instead of moving them to the destination, move them aside to the temporary spindle using the destination as the temporary. Once youíve gotten those out of the way, you move that single disc, the bottom of the disc from the source of the destination, and then you go pick up N minus 1 tower you left on temporary and stack it on top of you in the destination now using the source as your temporary. At any given stage, youíve got three to go and then you have to move the tower of height off of you.

When youíve got two to go, you have to move the tower of height of 1 off you. Base case you could imagine being pretty easy while single height tower, just one disc, could be exactly moved, this actually prefers going to even a simpler case, right, which is if youíre asking to move a zero height tower thereís nothing to do. In fact, the base case for the zero is if N equals zero, do nothing for any positive number then it goes through the process of shuffling the ones off of you to uncover your bottomless disc and then moving them back on. So five little lines and all the power in the world. Question?

Student:Why use the destination as a temporary?

Instructor (Julie Zelenski):The idea is that if weíre moving here from A to B, right, I need to leave this one open, right, so that Iíll be able to move the purple one when the time comes. So Iím trying to move this out of the way, right, so hereís where itís trying to go and in the process, right, you have these two places you can kind of shuffle things back and forth, where they came from, where theyíre not going and where they are going, so thereís also the source of destination and itís pretty obvious; and then what happens is that whatever is left over is the one that gets used as a temp.

Student:Why canít you put those on the second one?

Instructor (Julie Zelenski):Well, if I put them on the second one, how am I gonna get the purple one underneath them?

Student:Well, you wanted to put them on the last one.

Instructor (Julie Zelenski):Well, my plan was to move from A to B actually. It doesnít really matter.

Student:Oh, okay.

Instructor (Julie Zelenski):Iím trying to move from A to B so in fact, C is the place where Iím just leaving stuff temporarily.

Student:Okay.

Instructor (Julie Zelenski):So youíre gonna see that the stack frames here show how deep the recursion ever gets at any given point, right, at this case, having four discs it gets about four deep, actually five because it goes to the zero case and that youíll see it kind of go down and back as it shows it kind of moving the tower away and then getting back to moving the bottomless disc and then doing another deep recursion to move that tower back on top. And so at any given stage, right, theyíre all stacked up and the start/finish attempts start switching positions depending on what level of the recursion weíre at. Each time we get to zero we hit our base case and unwind. Let me make it go a little bit faster because itís a little bit slow.

Student:[Inaudible]

Instructor (Julie Zelenski):[Inaudible]. All right. So I just moved the tower of height three all the way away and now letís move the bottomless one back and now itís gonna start moving the tower that was shuffled away back on to it and then it will eventually stack it back up on the B where it wants to go. I can make him move the tower.

Student:Sixty-four.

Instructor (Julie Zelenski):Yeah. Sixty-four. Weíll talk a little bit about why I wouldnít want to put in the number 64. You can see Iím kind of it around. Dancing, dancing, much better than I would do. I actually maintained the rules at all times. No discs getting smashed. I go up to six and so never getting lost, always keeping track of what itís up to, right, itís a very tricky thing for a human to do, but a very easy thing for a computer to be able to identify what part of the recursion weíre at and what weíre trying to do right now without getting confused about the other things that are also kind of ongoing.

Theyíre all very neatly kept apart. So when people will ask you about recursion, everyone will want to know have you been exposed to the towers problem, and now, you have. So very powerful little piece of code, right, and it feels very much like a trick. I can remember sitting in a room, not unlike yourselves, a gazillion years ago and having someone explain the towers of Hanoi to me and just not believing. Just saying that canít work. You didnít do anything. All you did was call yourself before you were even done and thatís just nonsense and thatís just not right. And then after some amount of thinking about it and working it through, I did conclude that it actually did work, but at first, it really did seem like a trick. So if youíre feeling that way, this is par for the course. It is a little wacky to get your head around, but it is sort of relying on this idea of the mathematical induction; if you can do it for the smaller version of the problem and then build on that to solve the bigger problem, as long as you make that logical progression from this problem to the smaller one down to that simple case, you will eventually solve the whole thing.

Student:[Inaudible]

Instructor (Julie Zelenski):Source destination in this case. Okay. So then there are two problems I want to do. Iíll probably only do one today and Iíll do one on Friday that are what I think of as the mother problems of all recursions that many, many problems in the end just boil down to an instance of either the permutations problem or the subset problem. So Iím gonna show you permutations and subsets sort of in gory detail and then Iíll try to build with you about how many things actually are just a permutations problem or subset problem when looked at the right way and so once you kind of have these two in your arsenal, youíre very much prepared to attack a lot of different recursion things using those same patterns. So the one Iím looking at here is permutations. You have an input string, letís say itís the alphabet A through Z, 26 letters, what youíd like to do is enumerate or print or list all of the ways you could permute the alphabet. So thereís 26 letters in the alphabet, if you know anything about combinations and permutations, you realize thereís 26 ways you can choose the first letters, A, B, C, all the way to Z and then that leaves you with 25 letters from which to pick the next one, right, so thereís 25 ways to do that and then 24 ways to pick after that and so at each step you have one fewer choices remaining to conclude the permutation; and then the number of permutations is then factorials in the length of the input, so 26 factorial, which is an enormous number.

It tells you about all the different ways you could rearrange the alphabet. For a smaller string, you know, A, B, C, right, there are three factorials for that, six different ways you could permute that. The same principle applies no matter how large the string is. So our goal is to write a function that, given an input string, will print all of the permutations of that string. Thatís the goal. Okay. So Iíve got A, B, C, D coming in, I want to be able to print D, C, B, A and C, A B, D and all these other variations. Iím gonna use the strategy that actually I described just the way I did kind of intuitively about how permutations are constructed. That at any given point, right, I have a choice to make, and that choice in this case, will be whatís the next letter to attach to the permutations. So if I measure my goal by trying to build the permutation up one letter at a time. I start with an empty string so Iím gonna have the input and the output. The input is the letters I havenít yet used, so in the case of the string, A, B, C, it might be the whole string, A, B, C. Iíve got this output, which is what letters Iíve chosen so far. It starts empty. I look at my A, B, C and I say, Well, each of those letters could be the next one thatís here, why donít I go ahead and pick one, pick A for that matter, put it on the output and then recursively call myself to say well given A is in the front, because you also print all the things that you can permute the remaining letters, B, C, behind it.

After the magic recursion has done what itís gonna do I can come back to the call I was at and say okay, well, now itís not just A in the front I need to try; I also need to try B in the front. So I tried B in the front and now permute the A, C, that I leave behind. I try C in the front and permute the A, B, thatís left behind. So at any given stage of this recursion, right, I have these options, which are of all the letters remaining in the input, each of them needs to be tried as the next one to go and then I need to recursively permute on this slightly smaller form of the same problem where the output is one shorter of. Iíve removed one letter from consideration because Iíve picked it and the input is one longer. So at each level of the recursion, one letter is shuffled from the output to the input after Iíve done that N times, right, I will have created a permutation and then I can just print it. So Iíve talked about this. Let me just show you the code because I think that is where we can spend the most time illuminating whatís trying to go on. So hereís recursive permute. The form that Iím gonna use here is gonna take two arguments. Iíll explain the need for it in a second, but largely what Iím gonna be tracking is that input and output.

What I have assembled so far is in that first parameter, so the things I have committed in the permutation Iím building right now, the rest is those letters that havenít been chosen that have been passed over so far that are remaining to be permuted and attached on to so far. If the rest is empty, that means everything has been attached in so far, I have a permutation and then I just print it. If itís not empty, then for every letter that remains in the rest Ė so imagine Iím starting with the whole alphabet and so far was empty, this four loop is going to iterate 26 times, itís going to take out the [inaudible] character and itís gonna append it to the permutation and then itís gonna remove it from the rest to show that itís been used so we wonít accidently repeat it later in the permutation.

And then we make this recursive call saying okay, now having picked the letter N and put it in the front, hereís the whole alphabet without N. So at the beginning we have everything in the input, nothing in the output. Well, once we pick something that shuffles on character from here to there. A subsequent call down here moves another character and then eventually weíve emptied out the rest. There are other alternatives though, for example, up here it could be that we picked B and left behind A, C, it could be that we picked C and left behind A, B. Before itís all done, weíre gonna have to try all of those things and so the very first level of the recursion is gonna make a number of calls equal to the length of the input. Each subsequent level, right, in here makes one fewer call at each branch. So if I had a 26 at the top, each of those 26 then makes a 25 underneath so thereís 26 25s branching down there and then each of the 25 makes a 24. So this is an enormously wide tree. The depth is bounded by the total number of characters, but very, very wide. Iím just gonna show you a little part of the tree to get an idea. If Iím permuting A, B, C, D in the so far for the input, [inaudible] starts empty and there are four calls that are being made, first with A, then with B, then with C, then with D and in each case, removing that letter from what remains and then exploring.

So if I kind of further expand this call, it makes three calls, right, one having pulling B to attach on, one having attached C on, and one having attached D on leaving the remaining two characters. And then underneath that, picking that third character and then eventually pocking the fourth character which thereís no choices there. So this is only a partial part of the tree, but it gives you an idea of what the shape of that recursion looks like. This is a tricky thing to get your head around. But it is a critical pattern to get in your arsenals to you know how to apply it. So what this is sort of that choice pattern, right; of the choices I have, I need to go through the process of making those choices, updating my state to show that choice has been made and then recursing from there Ė making that recursive call to further explore whatever choices remain having made this one, which caused there to be one fewer choices to be made. And in a permutation, you have to make 26 choices, right, for the alphabet. Well, you make one and then you have 25 to go, you make one, you have 24 to go. Each of those calls, right, is working its way down.

Thereís one little detail Iíll mention and then weíll finish on Friday, which is that probably the way this function would be presented to a client or a user who wanted to get the permutations is it makes more sense for them to say hereís the string I have, could you please just list the permutations. This notion that somehow I need to track what Iíve generated so far is very much an internal housekeeping part and so it effects permutations to look like this and then just immediately turn around and make a call to the real recursive function that set up the state, the housekeeping that was being tracked through it, so weíll call this thing a wrapper function. All it is one line of code that just sets up the right state to get the recursion going and kind of state managed. We will see that quite a lot in a lot of codes. They just know about it. Come Friday, weíll talk about subsets and then weíll start looking at recursive backtracking.

[End of Audio]

Duration: 52 minutes