Lec 4 | MIT 6.00 Introduction to Computer Science and Programming, Fall 2008

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. As I've done in the previous lectures, let me set the stage for what we've been doing so we can use that to talk about what we're going to do today. So far, we have the following in our language. We have assignment, we have conditionals, we have input output, and we have looping constructs. These are things like for and while loops. And of course, we've got some data to go with that. One of the things we said last time was, with that set of things, the ability to give values, sorry, to give names to values, the ability to make decisions, the ability to loop as a function of that, the ability to get things in and out, we said that that actually gave us a language that we said was Turing-complete. And that meant, in English, that this was enough to write any program. Now that's a slight lie, or actually, in these days of political debates, a slight misspeaking. A wonderful word. It is technically correct. It is enough to allow us to write any program, but it's not enough to allow us to easily write any program. And so I joked, badly, I'll agree, at the end of last lecture, that we could just stop now, go straight to the final exam, because this is all you need to know. The point is, yes, it's enough to start with, but we want to add things to this that let us problem solve well. And one of the things to think about is, even though I've got all of that, let's think about what I could do if I wanted to write a piece of code. Right now, you've got to write it in one file. It's a long sequence of instructions. It starts at the beginning, walks through it, may jump around a little bit, but eventually comes down at the end. It's OK for the things you're doing for the early problem sets. 10 lines of code, 20 lines of code. Imagine instead you're writing code that's 100,000 lines, a million lines of code. You don't want to write it in this form, all right? And the reason you don't want to do that is, well, several. First of all, it's really hard to figure out where everything is, where everything goes, making sure I'm in the right place. To use an ancient expression from the 1970s, which only John and I will appreciate, it's really hard to grok what that code is doing, to understand what it's trying to make happen. And the reason that that's the case is, what we don't have are two important things. We don't have decomposition, and we don't have abstraction. And that's what we're going to add today. So what does that mean? Those are fancy terms. Decomposition is a way of putting structure onto the code. It's a way of breaking the code up into modules. Modules that make sense on their own. Modules that we can reuse in multiple places. Modules that, if you like, isolate components of the process. And abstraction is related to that. Abstraction is going to let us suppress details. It's going to let us bury away the specifics of something, and treat that computation like a black box. And by black box, I mean, literally behaves like a mysterious little black box. You put some inputs in, it has a contract that says if you put the right kind of inputs in, you'll get a specific output coming out. But you don't have to know what's inside of that box. And that abstraction is really important. Again, imagine if I'm writing a piece of code, I want to just use it, I shouldn't have to worry about what variables I use inside of it, I shouldn't have to worry about where that is in the code, I should be able to just abstract it away. And that's what we want to add today, are those two things. Now, our mechanism for doing that, or at least one mechanism, I shouldn't say the only one, one mechanism for doing that is going to be to add functions to our language. And the point of a function is, that it's going to provide both of these things. So the first thing it's going to do is, it's going to let us break up into modules. Second thing they're going to do is let us suppress detail. And in essence, what that does is, the functions, we're going to look at a bunch of examples in a second, these functions are going to give us a way to, in some, one way of thinking about it, is to create new primitives. And I'm going to put those in quotes, because it's generalization, but what do I mean by that? The idea of a function is, that I'm going to capture a common pattern of computation. Computing square root. I'm going to capture it in a piece of code, I'm going to be able to refer to it by a name, and I'm going to suppress the details, meaning inside of that computation, you don't need to know what it does, you just need to know if I give it the right kind of input, it'll give me back an output that satisfies the contract that I set up. And that, in essence, says, I've just created the equivalent of a new primitive. Same way that I have multiplication, or division as a primitive, functions are going to give me, or somebody else who wrote them for me as part of a library, a new primitive that I'm going to be able to use. And that gives me a lot of power, in terms of what I want to have inside of the language. OK. So, let's look at an example, to try and see what we're going to do with this. Before I do that, though, let me try and give you an analogy to keep this in mind, of why we want to basically build these abstractions, and what we need in order to have them work together. So here's the, I'm about to say silly analogy, you can tell my jokes are always bad. John's are much better, by the way, which is why Thursday will be a much better lecture. But here's the example. You've been hired by PBS to produce a nice 13-hour documentary, or drama, that's going to run. And, you know, you start by saying, OK, 13 hours, I'm going to break it up into 13 different chunks, I'm going to assign each chunk to a different writer. And they're going to go off and write that element, that hour's worth of stuff. You can imagine what you get. Each hour's worth of drama, if you like, may be great, but it may have absolutely nothing to do with the other 12 hours. And unless, you know, you've been hired to do Pirandello's six characters in search of an author, this is not a great thing, because you get something that is really confusing. Now, what's the point of the analogy? What do I need for those writers to all interact together? I need a specification. I need a contract that says, here's what I want, in terms of the things that you're going to take as input to begin your part of the drama, here's what you're going to produce at the output. And the details of what they do inside are up to them. That idea of abstraction, that idea of specification, is exactly what we want to use inside of our functions. We won't make you write dramas like Pirandello, but we're going to try and make you at least write good code, and that's what we're going to try and do. All right, let's set the stage for it. Up on the screen, I've got, I've commented it out, but I've got a piece of code that you've seen before, right up here. What is that? It's a piece of code we wrote for computing square root. Square roots of actually perfect squares. And we're going to, yeah, just remind you what it does. We've bound x to some value, we set up an initial variable, a variable called answer, answer, and then we run through a little loop, right, where, well, actually I should say that better, we first check to see, is x greater than or equal to 0, if it's not, then we come down here and we print something out, otherwise we run through a little loop to get the answer, and then we check it and we spit something up. Does the computation, that's fine. Suppose I want to compute square roots a lot of places in a big chunk of code. Right now, I have to take that piece of code and replicate it everywhere I want in my larger file. And I've got to worry about, is somebody else using a n s, answer, as a variable, in which case I've got to be really careful. Is somebody else using x as a variable? I've got to deal with a lot of those details. I want to abstract that, and the abstraction you see right here. I'm going to highlight it for a second so you can see it, I want you to look at it in the handout as well. This is the creation of a function, and I want to describe both the syntax, what we're doing, and then the semantics of how do we use it and what does it mean. So, here's the syntax of the function. First of all, we have a keyword, def, definition, or defined, depending on which sort of piece of history you come from. This is a keyword to Python that says, when it reads this in the file, it says, I'm creating a definition, I'm creating a function. And that's followed, so this is, let me say it this way, this is a keyword, that is followed immediately by a name. In this case, squirt, square root. I'm saying, this is the name I'm going to give to this function. This is the name to which I'm going to refer when I want to use this function. All right, and notice, immediately after that name, we have an open and closed paren with another variable name inside of that. And this defines the formal parameters of this function. It does indeed, thank you, this is me being a scheme hacker, not a Python hacker, yes, def has to be lowercase or it won't recognize it, thank you John. OK, def's the keyword, I'm creating a function, squirt, again, I've got to be careful about case sensitive, I'm using all lowercase here, followed by open paren, and I said formal parameters, we'll see there could be more than one there. We're going to come back to what they mean in a second, but for now, think of them as, or think of x in this case, as the placeholder. This placeholder is saying, if you give me a value for x inside the body of this function, I'm going to use that value everywhere I see x. Question? All right, we're going to come back to this in a second, but the question was, do I always need an input? I can have functions with no parameters, that's fine, I will still need the open and closed paren there, to identify that I have no parameters. And we're going to see an example in a second. Good question. Actually, I've got to get rid of this candy, so since it was a good question, here you go. Nice catch. Almost. Sorry. OK. No, I'm not, I'm sorry, I thought you had it, and then I got the wrong glasses on, and I realized you didn't, so I'll come back to that later. What are we doing here? We got definition, we got name, we got set of formal parameters, all right? If you look at the rest of that code, gee, it looks a lot like what I had elsewhere, what I had outside of it, right, it's running through a similar set of loops, so in some sense, as long as x has the value I wanted, it ought to do the right thing. However, there's a couple of other changes there that we want to highlight. And in particular, notice, let me highlight it for you, if I can find it with the wrong glasses on, we've got these return commands. So return is another keyword, and it basically says, when you get to this point in the computation, stop the computation, literally return the control from this function, and take the value of the next expression, and return that as the value of the whole computation. Now, the one that we're most interested in is the one where in fact, it gets out answers, so you'll see down here in the code, there's a spot where it's going to return the value of answer, which is what we'd want, right, that's the thing that holds the value that we intended to have. But there's another couple of places in that code where it's got this funky looking thing, return none, and notice none's in a different color. None is a special value, and it has the following slightly odd behavior. It is a value, and I'm going to return it, God bless. But what none says is, there is no value coming back from this computation. So when it is returned, and we'll see this in a second, to the interpreter, it doesn't print. OK? Simply doesn't print anything. Nonetheless, it is actually a value, and we can use it, for example, to do comparisons. If we want to know, did this function return a value or not, rather than reserving, say, minus 1, or some other special thing, which you might want to use some other ways, it literally returns this very special value that says, there is no actual value returned from this computation. OK. Note, by the way, if I chase through each possible path, right, there's some ifs in here, there's some places to go, at least in this piece of code, every possible path through this code ends in a return, and that's a good programming discipline to make sure that happens. There's an exception, which we'll see in a second, but I'll highlight, which is, if we get to the end of the procedure, there's sort of an implicit return there. In fact, a return of none in that case that comes out of it. But if I look at this, right, if I come into this code, I'm going to check this branch first, if it's not true, ah, there's a return at the end of that branch. If it is true, I do that, and then I've got a second test. If it's true, I return, otherwise I return. So there's a return branch on every possible path through the code. And that's valuable, and something you want to think about as you write your own. OK, what do I do to use this? In particular, how do I invoke this? OK, so I'm going to invoke a function by passing in values for the parameters. And in this case, that literally means typing squirt in some value inside the params. OK, now let's just try this out to see what happens. I'm going to make sure I've got it there. So if I type, for example, squirt, yeah, of 16, aha. What did it do? Well, let's talk about what it did. What this invocation does is the following. It binds, and I'm going to say this specifically for this example, rather than general, it binds x to 16. Just as you would have done with an assignment statement up in the top-level thing. But this binding is local, meaning it only holds within the confines of the code of this procedure. Relative to that, think of that as creating what I'm going to call a new environment. Relative to that, it does all the other execution we would do. Including, notice the first instruction there is to set up a binding for answer. So answer, or a n s, is also bound only locally, meaning inside the confines of this environment of this procedure. a n s starts off with the value zero, and then we just run through that loop, just like we did before, right? It increments it slowly, checking to see if a n s squared is bigger than x. When it gets to that point, it checks to see, is it actually a perfect square or not, and it returns it. And once it returns it, it returns a value from that return, that in this case is just printed out. All right? Now, I want to say a couple of things about these local bindings. I'm going to repeat this a second time, because it's important. These local bindings do not affect any global bindings. What does that mean? Let me show you a little example, and then we'll come back to this. I've got a little function here, I'll let you see it. I've defined f of x to be a function that takes a value of x in, changes x to x plus 1, and then just returns the value. OK, so it's just adding 1 to x. But I want you to see now what happens if I use this. Let's bind x to the value of 3. It's creating a binding for x in this global environment. This is what the interpreter sees, right? In fact, if I look at x, its value is 3. Let's bind z to be, if I could type it would help, say f of 3, it's the value of z. It's 4, which is what I expect, right? Locally, x got bound to 3, I added 1 to it, whoop-dee-doo, I get back out 4. But what's the value of x? It's still 3. And the way to think of this is, again, I've got multiple scopes, or multiple frames, and we're going to come back to those terms, I'm going to use the word environment, because I'm an old-time list packer, multiple environments in which there are bindings. So let me spell this out in just a little bit more detail. What this is saying is the following. When I'm talking to the interpreter, when I'm typing things in, as I just did to that Python environment, I am getting what I'm going to call global bindings. I'm going to draw a little chart here, think of this as the world of the interpreter, in that I've got things like x, it's bound to the value 3. When I call, or invoke, a function, think of it as creating a local table, and inside that local table, I bind the formal parameter, what I did, I did 16, right, to some value. This x only gets seen by squirt. Inside of there, I can bind other things, like a n s gets locally bound to 0, and then it increments around, and eventually we return that value out. When I get to a return from squirt, some value is returned back to the interpreter, and that table goes away. But that table does not affect any bindings for other instances of the variable, like x or a n s. OK. Let's look at a couple of examples just to sort of stress that. One of the things I wanted to show is, again, I can now use a function just as if it was a primitive, so this is just an assignment, I'm going to set take test to be the value of that. Of course, nothing gets printed, because that was an assignment statement, right, so if I called squirt alone, that return value is done, but in this case, I bound it to test, so I can go look at test, there it is. What happens if I do that? OK, if you look at the code, it printed out, it's not a perfect square, which is what I wanted, but now what's the value of test? OK, I bound test to something, if I look at it, it doesn't print anything, but, if I could type, I can ask, is test bound to that special name none, and the answer is yes. Boy, this seems like a nuance, right, but it's a valuable thing, it says, in each case, I return some useful value from this procedure, I can check it, so if this was part of some other computation, I want to know, did it find a perfect square or not, I don't have to have to go read what it printed out on the screen, this has returned a value that I can use, because I could do a test to say, is this a return value, if it's not, I'll do something else with it. So the binding is still there, it simply doesn't print it out. OK, what do we have out of this? Simple, seems like at least addition. We've added this notion of a function, and I've highlighted some of the key things we got here, right? We have that def keyword, we've got a name, we've got a list, I shouldn't say word list, we have a collection of formal parameters that we're going to use, we have a body, the body looks just like the normal instructions we'd use, although, by the way, we ought to be able to use functions inside the body, which we're going to do in a second, and then we're just simply going to return some values out of this. Now I started by saying, to build these functions, I'm trying to get both decomposition and abstraction. Well, you hopefully can see the decomposition, right? I now have a module. OK, let me set the stage. Imagine I wanted to do squirt, or square root, I'm not going to use squirt, that's the name I'm using, or square root, a hundred different places in some piece of code. Without function, I'd have to copy that piece of code everywhere. Now I got one just simple thing, and I simply have isolated that module inside of that function. What about abstraction? Well, I've got part of what I want for abstraction. Abstraction, again, says I'm going to suppress details. Now that I've written squirt, I can just use it anywhere I want in the code. You've got to rely on the fact that I wrote it correctly, but you can basically suppress the details of how it's used. But there's one more piece that we'd like to get out of that, and that is, you may have been wondering, what's with the funky stuttering here of three double quotes in a row? And that is a specification, which is a really valuable thing to have. So what is the specification going to do? It is my place, as a programmer, to write information to the user. This is me writing one hour of that episode of Pirandello and telling the other authors, here's what I'm assuming as you use it. So it's up to me to do it right, but if I do it, I'm going to specify, what does this function do, what does it expect as inputs, any other information I want to pass on. And notice, by the way, if I do that, and I come down here, and I type squirt and open the paren, it shows me what the creator, in this case, actually I stole this from John, so what Professor Guttag put up as his specification for this piece of code. Now, not guaranteed it's right, right, you're trusting the programmer did it right, but this now tells you something, what is this, this is a wonderful piece of abstraction. It is saying, you don't need to know squat about what's inside the body of this function, you don't have to worry about the parameter names, because they're going to be preserved, you don't need to worry about how I'm doing it, this tells you how you can use this, in order to use it correctly. Of course, I can then close it off, and off we go. Right, so that notion of abstraction, I know is going to come back, we're going to come back to multiple times during the term, and it's not just abstraction, it's the idea of a specification. And just to look ahead a little bit, you could easily imagine that I might want to not just put a statement in there of what the specs are, I might want to put some constraints, some specific things to check for, to make sure that you're calling the code right. That becomes a powerful way of reasoning about the code, a powerful way of using the code, so those notions of specs are really important. Look, part of the reason I'm flaming at you, is something like square root, it seems dumb to write specs on it, everybody knows what this is going to do, but you want to get into that discipline of good hygiene, good style, you want to write the specs so that everybody does, in fact, know what this piece of code is doing, and you're writing it each time around. OK. Now that we've got functions, let's see what we can do as a problem-solving tool using them. In particular, I've already said, I want to get this notion of modularity, it's a module I can isolate, I want to get the notion of abstracting away the details, let's see how we can actually use that to actually write some reasonably interesting pieces of code, but in particular, to see how we can use it to capture the ideas of decomposition and abstraction. So I'm going to shift gears. Start with a simple problem. Boy, we've suddenly been transported to Nebraska, or where I grew up, Saskatchewan, right? We've got a farmyard problem. I've got a farmer. Walks out into his yard one morning, this farmer has a bunch of pigs and a bunch of, it's been a long day, a bunch of pigs and a bunch of chickens. And he walks out into the farmyard, and he observes 20 heads and 56 legs. And for sake of argument, there are no amputees among the chickens and the pigs. And the question is, so how many pigs does he have, and how many chickens does he have? Wow, what a deep problem, right? But you're going to see why we're going to use this in a second. So you know how to solve it. This is a fifth grade problem, right? What's the way to solve this? System of linear equations. What are the equations here? Well, I could say, you know, the number of pigs plus the number of chickens equals 20, right, because I've got 20 heads, and then what else do I have? Four times the number of pigs plus two times the number of chickens, assuming they're not next to a nuclear reactor, is 56. And then how would you solve this? Well, you sort of know how you do it if this was grammar school, right? You'd pull out your pencil and paper, you could do it as a matrix inversion, if you know how to do that, or you could just simply do substitution of one equation into another to solve it. That's certainly one way to do it, but for computers, that's not necessarily the easiest way. So another way of solving it is to do something we already saw last time, which is basically, why not simply enumerate all possible examples and check them? I could say, I could have zero chickens and 20 pigs. Does that work? I got one chicken and 19 pigs, does that work? I got two chickens and 18 pigs, you get the idea. So I'm going to solve this by enumerate and check, which is an example of what's called a brute force algorithm. Meaning, I'm just going to write a little loop that does that. All right, so let's go back to our code. Sorry, let me pull this over a little bit so I can see it. What I'd like you to look at, I'm going to highlight it just for a second here, is those two pieces of code. Let's start with solve. OK, here's the idea of solve. I'm going to have it taken as input, how many legs I got, how many heads do I have, and I just want to write a little loop. OK, I know how to do that, right? Write a little loop, all I'm going to do is run a for loop here. I'm going to let the number of chickens be in this range. Remember what range does, it gives me a set, or a collection, or a tuple of integers from 0 up to 1 minus the last value, so it's going to give me everything from 0 up to the total number of heads. Knowing that, and I say, OK, how many pigs are there? Well, that's just however many I had total, minus that amount. And then I can see how many legs does that give, and then I can check the number of legs that I would get for that solution is equal to the number of legs I started with. Ah, interesting, a return. And in particular, I'm going to return a tuple. So a pair, or a collection of those two values. If it isn't, then I'm going to go back around the loop, and notice what happens. If I get all the way around the loop, that is all the way through that for loop, and I never find a path that takes me through here, then the last thing I'm going to do is return a pair, or a tuple, of the special simple number, none twice. Yep. You're telling me I want parens there, and not braces? All right, I hate this language, because I always want to have parens. Every time you see a square bracket, put a paren in. All right? Thank you, Christy, I'll get it eventually. Having done that, all right, notice what I've got. First of all, two parameters. It's OK. All it says is, when I call this, I need to pass in two parameters for this to work. Right? Now, if I want to use that, I'm going to use a second piece of code here, called Barnyard. I'm going to read in a couple of values, convert them into integers, and then I'm going to use solve to get a solution out. Now what do I know about solve? It is going to give me back a tuple, a collection of two things. And so, check out the syntax. I can give two names, which will get bound to the two parts of that return tuple. OK, pigs will be the first part, chickens will be the second part. OK, and then once I've got that, well, notice, I can then check to see, did I return that special symbol none as the first part? That says I took the branch through here that eventually got to the end and said there wasn't a solution, in which case I'm going to print out there ain't no solution, otherwise I'll print out the pieces. All right, let's check it out. What did I say? 20 and 56, right? OK, notice the form. I've got two parameters, they're separated by a comma. All right, but it's still, it's legs and heads, but it should not still have, oh, sorry, thank you, I'm doing the wrong thing, I want barnyard this way, and if I had looked when I opened the paren, it would have shown me a closed paren with no parameters. Aren't you glad I make mistakes so you can see how well I can fix from these? All right, now I call that, and it says, tell me how many heads you want, give it 20, tell me how many legs you want, give it 56, and it prints out the answers. I know, whoop-de-doo. But notice what's inside of here. First of all, notice the modularity. I've used solve, right? Right there. I've captured it as a computation. It's buried away, all the details are suppressed. I can use that to return values, which I can then use elsewhere, which I did, and if I just come back and highlight this, inside of that computation. But I don't have to know, inside of barnyard, what the values are used inside of solve. I don't know what the names of the variables are, I don't care, right? I can basically suppress away that detail. Second thing we saw is, that using this as a computation, I can return multiple values, which is actually a real value to me here, as I use that. OK. Yeah, question. The question was, when it returns, how does it distinguish between local and other things? So let me try and answer that. Inside of solve, solve creates an environment where, inside of that, it has bindings for the parameters it's going to use. Like number of, what did we call here? Where's solve? Number of legs and number of heads. OK, those are bound locally. When solve is done, it wraps up, if you like, a value that it returns, which is that. That expression, or that value, or that value, literally gets passed back out of that local environment to the value that comes back out of it. So in particular, what solve returns is a pair. Could be the pair of none, none, it could be the pair of, you know, whatever the answer was that we put up there. That value comes back out and is now available inside the scope of Barnyard. And Barnyard then uses that. Question. Here? So the question is, why is this return on the same level as the four? Why do you think? Good question, all right? So what's going to happen here? If I'm inside this four, and I'm running around, if I ever hit a place where this test is true, I'm going to execute that return, that return returns from the entire procedure. OK? So return comes back from the procedure. So the question was, why is this return down at this level? It says, well, if I ever execute out of this for loop, I get to the end of the for loop without hitting that branch that took me through the return, then, and only then, do I want to actually say, gee, I got to this place, there isn't any value to returning a return, none and none. I'm still trying to get rid of this candy. Halloween's coming. Where were we? There's one. Thank you. I don't think I'm going to make it. I did, thank you. Make sense? The answer is, no, I want parens to create tuples, and I get really confused about the difference between lists and tuples. For now, the code is working. Yes, is the answer, all right? And we're having a difference of opinion as to whether we should use a tuple or a list here, right? But the answer is, yes, you can. And my real answer is, go try it out, because obviously, you can tell I frequently do this the wrong way, and the TAs give me a hard time every time. John? Is the microphone on? Yeah. As you'll see next week, tuples and lists are very close to the same thing. And almost any place where you can get away with using tuples, you can use lists. Yes. But I want to emphasize the word is almost, because we'll see a couple of places where, if it expects a tuple, and you use a list, you'll get an error message. But we'll see all of that next week. Right. When the real pro comes in to pick up the pieces I'm leaving behind for him. OK. OK, let me pull this back up. What we're doing now is we're building this encapsulation. Now, one of the things you notice here, by the way, is, you know, this, in essence, just solves the simple problem. Suppose I now add one other piece to this. You know, the farmer's not keeping a great set of things. So in addition to pigs and chickens, he raises spiders. I have no idea why. I don't know, he's making silk, I guess. Right. Why am I giving this example? I want to show you how easy it is to change the code, but notice, once I've added this, I actually have a problem. This is now an under-constrained problem. I have more unknowns than I have equations. So you know from algebra, I can't actually solve this, or maybe multiple solutions to this. What would I have to do to change my code? And the answer is, fortunately, not a lot. So I'm going to ask you to look now at this set of things, which is solve 1 and barnyard 1. OK? The change is, well, on barnyard 1, it looks much the same as it did for barnyard, right? I'm going to read in the values of the number of heads and the number of legs. I'm going to use solve 1 as before, but now I'm going to bind out three variables, and then I'm going to do a similar thing to print things out. But what would the solver do? Well, here, what I'd like to do is to run through a couple of loops, right? How would I solve this problem? I can use the same kind of enumerate and check idea, but now say, gee, let me pick how many pigs there are. Is that the one I used first? Sorry, let me pick the number of spiders there are. Having chosen the number of spiders, let me pick how many chickens I have. With those two in place, I now know how many pigs I must have, and I can run through the same solution. The reason I'm showing you this is, this is another very standard structure. I now have two nested loops, right? One running through a choice for one parameter, another one running through a choice for a second parameter, and then the rest of the solution looks much like before. I'm going to get the total number of legs out, I'm going to check to see if it's right or not, and again, I'm going to return either a 3-tuple there, or a 3-tuple there. That's part of what I want, because I'm going to bind those values out. And if I run that, for example, barnyard 1, I don't know, we'll give it 20 heads, 56 legs, and it finds a solution. I ought to be able to run something else. I don't know, give me some numbers. How many heads? Pick an integer, somebody. 5? All right, how many legs? 10? All right, we got an easy one. Let's just, for the heck of it, I should have found some better examples before I tried this. No mutant spiders here. OK, so what have I done? I just add a little bit more. Now I'm now running through a pair of loops. Again, notice the encapsulation, that nice abstraction that's going on, which is what I want. Once I get to this stage, though, by the way, there might be more than one solution, right? It's an under-constrained problem, there could be multiple solutions. So suppose I want to capture all of them, or print all of them out. Well, I ought to be able to do that by simply generalizing the loop, and that's what the next piece of code on your handout shows you. If you look, I'm just going to let you look at this. If you look at solve 2, it's going to run through the same kind of loop, printing out all of the answers, but it's going to keep going. In other words, it doesn't just return when it finds one, it's going to run through all of them. All right? Sounds like a reasonable thing to do. Notice one last piece. If I'm going to do that, I'm going to run through all possible answers, I still want to know, gee, what if there aren't any answers, how do I return that case? And that shows you one other nice little thing we want to do, which is, if I look in this code, notice I set up a variable up here called solution found, initially bound to false. The rest of that code's a pair of loops. Pick the number of spiders, pick the number of chickens, that sets up the number of pigs, figure out the legs, see if it's right. If it is right, I'm going to print out the information, but I'm also going to change that variable to true. And that allows me then, at the end of that pair of loops, when I get down to this point, right here, I can check to see did I find any solution, and if not, in that case print out, there is no solution. So this gives you another nice piece, which is, I can now look for first solution, I can look for all solutions, and I can maintain some internal variables that let me know what I found, a trick that you're going to use a lot as you write your own functions. All right. I want to end up with the last 10 minutes with a different variation on how to use functions to think about problems. And that is to introduce the idea of recursion. How many of you heard the term used before? How many of you heard the term used before in terms of programming languages? Great. For the rest of you, don't sweat it. This is a highfalutin term that computer scientists use to try and make them look like they're smarter than they really are. All right, but it is a very handy way of thinking about not just how to program, but how to break problems down into nice sized chunks. And the idea behind recursion, I'm going to describe with a simple example, and then I'm going to show you how we can actually use it. Right. The idea of recursion is that I'm going to take a problem and break it down into a simpler version of the same problem, plus some steps that I can execute. I'm going to show you an example of a procedure, sorry, a function in a second, but let me give you actually an analogy. If you look at US law, and you look at the definition of the US legal code that defines the notion of a natural-born US citizen, it's actually a wonderful recursive definition. So what's the definition? If you're born in the United States, you are by definition a natural-born US citizen. And we call that a base case. It's basically the simplest possible solution to the problem. Now, if you were not born in the United States, you may still be, under definition, a natural-born US citizen if you're born outside this United States, both of your parents are citizens of the United States, and at least one parent has lived in the United States. There's a wonderful legal expression. But we'll notice what that is. It's a recursive definition. How do you know that your parents, or at least one of your parents, satisfies the definition? Well, I've reduced the problem from, am I a natural-born US citizen? To, is one of my parents a natural-born US citizen? And that may generalize again, and it keeps going until you either get back to Adam and Eve, I guess, I don't think they were born in the US, as far as I know, or you find somebody who satisfies that definition, or you find that none of your parents actually are in that category. But that second one is called the inductive step, or the recursive step. And in my words, it says, break the problem into a simpler version of the same problem, and some other steps. And I think this is best illustrated by giving you a simple little piece of code. I use simple advisedly here. This is actually a piece of code that is really easy to think about recursively. It's much more difficult to think about in other ways. And the piece of code is, suppose I have a string and I want to know if it's a palindrome. Right? Does it read the same thing left to right, right to left? How would I solve that? If the string has no elements in it, it's obviously a palindrome. If the string has one element in it, it's a palindrome. There's the base case. If it's longer than one, what do I want to do? Well, I'd like to check the two endpoints, to see, are they the same character? And if they are, then, oh, I just need to know, is everything else in the middle a palindrome? I know it sounds simple, but notice what I just did. I just used a recursive definition. I just reduced it to a smaller version of the same problem. That is, if I can write code that would solve all instances of smaller size strings, then what I just described will solve the larger size one. And in fact, that's exactly what I have. I would like you to look at this piece of code right here, called isPalindrome. Notice what it says. I'm going to pass in a string, call it s, binds it locally, and it says the following. It says, if this is a string of length 0 or 1, I'm done. I'm going to return the answer true. Otherwise, I'm going to check to see, is the first and last, there's that minus 1 indexing, is the first and last element of the string the same? And, if that's true, is everything in the string starting at the first element and removing the last element palindrome? I remind you, by saying first element, remember, we start at 0 as the initial indexing point. Wonderful recursive definition. OK? Let's try it out. Go back over here, and we're going to say, is, and how did I actually spell this palindrome with a capital P? Only in New York, in Canada, we pronounce it palindrome. So, you know, when you're teaching it, you get to call it your way, I'm going to call it my way. Sorry, John, you're absolutely right. OK? Notice, by the way, there's that nice spec going on, saying put a string in here, and it's going to return true if it's a palindrome, and false if it's a palindrome. And it says true. Now, maybe you're bugged by this. I know you're bugged by my bad humor, but too bad. Maybe you're bugged by this, saying, wait a minute, how does this thing stop? Right? This is the kind of definition that your, you know, high school geometry teacher would have wrapped your knuckles over. You can't define things in terms of themselves. This is an inductive definition. Actually, we could prove inductively that it holds, but how do we know it stops? Well, notice what the computation's doing. It's looking first to see, am I in the base case, which I'm done? If I'm not, I'm just going to reduce this to a smaller computation. And as long as that smaller computation reduces to another smaller computation, eventually I ought to get to the place where I'm down in that base case. And to see that, I've written another version of this, which I'm going to use here, where I'm going to give it a little indentation, oops, I want to call this palindrome one, sorry about that, palindrome one, I'm going to give it a little indentation, so that we can see this. OK, the code is right here, and all it's doing is, when I'm getting into the different places, I'm simply printing out information about where I am. What I want you to see is, notice what happened here. I'm calling palindrome with that. It first calls it on that problem. And the code over here says, OK, gee, if I'm in the base case, do something, I'm not, so come down here, check that the two endpoints, a and a, are the same, and call this a gain offset. Notice what happens, there's this nice unwrapping of the problem. Right? I just doubled the indentation each time, so you can see it. So each successive call, notice what's happening, right? The argument is getting reduced, and we're going another level in. When we get down to this point, we're calling it with just a string of length one, at that point we're in the base case, and we can unwrap this computation. We say, ah, that's now true, so I can retune true here, and given that that's true, and I already checked the two endpoints, that's true, that's true, and I unwrap the computation to get back up. You're going to have to go play with this, grok it, if you'd like to try and see where it goes, but I want to stress again, as long as I do the base case right, and my inductive or recursive step reduces it to a smaller version of the same problem, the code will, in fact, converge, and give me out an answer. All right, I want to show you one last example of using recursion, because we're going to come back to this. This is a classic example of using recursion, and that is dating from the 1200s, and is due to Fibonacci. Anybody know the history of what Fibonacci was trying to do? Sorry, let me re-ask that. Fibonacci, which actually is son of Bonacci, which is the name of his father, who was apparently a very friendly guy. Anybody know what, sorry, first of all, anybody know what a Fibonacci number is? Wow. OK, ah. Right, we're going to do that in a second, but the answer is, if Fibonacci numbers, if we define the first two, which are both defined to be, or I can define them, and I'll multiply 0 and 1, and then the next Fibonacci numbers are sum of the previous two, and the next Fibonacci numbers are sum of the previous two. Do you know the history of this? Exactly. Thank you. Ah, bad throw. I'm playing for the Yankees. Sorry, John. All right, the answer is, Fibonacci was actually trying to count rabbits, back in the 1200s, and the idea was, rabbits can mate after a month, at age one month, and so he said, if you start off with a male and a female, at the end of one month, they have an offspring, and let's assume they have two offspring. At the end of the next month, let's assume those offspring have offspring, again, a male and a female, and the question was, how many rabbits do you have at the end of a year, at the end of two years, at the end of more than that number of years? And so, we can do this, with the following level definition. We'll let pairs of 0, the number of pairs at month 0, actually not be 0, be 1, we'll let the number of pairs at month 1, be 1, and then the number of pairs at month n, is the number of pairs at month n minus 1, plus the number of pairs at month n minus 2, sum of the previous two. And if I write Fibonacci, you'll see it right there. And the reason I want to show you this, is to notice that the recursion can be doubled. So this says, given a value x, if it's either 0 or 1, either of those two cases, just return 1, otherwise, break this down into two versions of a simpler problem. Fib of x minus 1, and fib of x minus 2, and then take the sum of those, and return that as the value. Notice, if I'm going to have two different sub-problems, I need to have two base cases here, to catch this. And if I only had one, it would error out. As a consequence, I can go off and ask about rabbits. Let's see, at the end of 12 months, not so bad. At the end of two years, we're not looking so good. At the end of three years, we are now in Australia, overrun with rabbits. In fact, I don't think the thing ever comes back, so I'm going to stop it, because it really gets hung up here. I'm going to restart it. What's the point of this? Again, now that I can think about things recursively, I can similarly break things down into simpler versions of the same problem. Could be one version, could be multiple versions, and we're going to come back, throughout the term, to think about how to code programs that reflect this. The last point I want to make to you is, you've started writing programs that you would think of as being inherently iterative. They're running through a loop. It's a common way of thinking about problems. Some problems are naturally tackled that way. There are other problems that are much more naturally thought of in a recursive fashion. And I would suggest palindrome is a great example of that. That's easy to think about recursively, it's much harder to think about iteratively. And you want to get into the habit of deciding which is the right one for you to use. And with that, we'll see you next time.