Speaker 1: The following is a videotape module from the learning system Seymour Papert on Logo. The tape series has two parts, the first New Mindstorms focuses on the process and the principals of learning. The second, Logo Hurdles focuses on specific technical aspects of Logo. This is Hurdles tape number three, Images of Recursion. Like the other Hurdles modules, it is intended for use with On Logo study guides and computer diskettes.
Speaker 13: Great camera! What is that, a polaroid?
Speaker 2: Jack and Jill, what are you doing?
Speaker 13: I’m taking a picture of her taking a picture of her taking a picture of her taking a picture of me taking a picture of her taking a picture of me.
Speaker 2: Stop it! Why don’t you just take the picture?
Speaker 13: Because I’m not finished. I’ve got a saying I’m going to say before I can do it. I’m taking a picture of her taking a picture of me taking a picture of her taking a picture of me taking a picture of her taking a picture of me taking a picture of her taking a picture of me.
Seymour Papert: The story of Jack and Jill is of course a joke but it’s a serious joke, almost a philosophical one. In this tape, we’ll see how this joke is quite closely related to an idea of great power for solving problems and for understanding the world around us. An idea called recursion. We’ll be studying recursion primarily as a technique for Logo programming, but through Logo programs, I think you’ll get some deeper insights into the use of recursion beyond the computer.
The tape is divided into three parts. Three ways of approaching recursion which we’ve kept as separate as possible to allow people with different tastes and styles to choose the one they like best, so spin through the tape quickly and then choose the one you want to focus on, come back to the others later.
We see from Jack and Jill that there’s a lot about recursion that paradoxical and among the paradoxes, one is related to learning. Some concepts are hard to learn because they’re so complex. To get at them we have to penetrate success of layers, veils of complexity that stand between us and the concept we want to grasp. If recursion is difficult at all, it’s difficult because it’s so simple. I like to think of learning it as drawing a side, a veil, not of complexity but a veil of simplicity.
I’m fond of approaching recursion with children in an extremely simple way. In fact, through a joke not unrelated to what we saw Jack and Jill doing to one another, these children are playing a game which I’ve played with many groups.
When I say “wow” that’s the name of the procedure, when you hear “wow” you put your hand up and you put it down. Let’s try that. Wow. Wow. Okay, now we’re going to change it. When you hear “wow” you put your hand up, you put it down, and you say “wow”. Let’s have one person start. Who would like to do it? Okay, you do it. Wow.
Speaker 3: Wow.
Speaker 4: Wow.
Seymour Papert: Let’s try some [inaudible 00:04:18] else. You do it. Wow.
Speaker 5: Wow.
Seymour Papert: Hey, when I said “wow” to her, why didn’t you put your hand up? Let’s try again. Whenever you hear the word “wow”…
Speaker 6: Okay.
Seymour Papert: You put your hand up, you put it down, and you say “wow”.
Speaker 6: All right.
Seymour Papert: Wow.
Speaker 6: Wow.
Seymour Papert: Wow.
Speaker 6: Wow.
Seymour Papert: What are you waiting for? What do you think is happening?
Speaker 6: [crosstalk 00:04:47] Supposed to do it again.
Speaker 7: She’s supposed to keep going.
Seymour Papert: Why?
Speaker 7: Because I said “wow”.
Seymour Papert: Okay. Let’s try again. Wow.
Speaker 6: Wow. Wow. Wow. Wow.
Seymour Papert: Of course one can’t get a computer to put up its hand, nor can it hear its own voice, but I think you’ll agree that the program I’m going to show you works by the same kind of process as these children met in their people procedure called “Wow”. We use it here to make forever programs, ones that go on and on and on without stopping. Look at this one.
When this procedure is run by this instruction, the procedures first action is to note the dot side is 50, so at forward . side will become forward 50 and the turtle’s action will be forward 50 right 90. The procedures next action is square 50, which will start the cycle over again. Side is of course still 50. The turtle does once more forward 50, right 90, and you might be asking yourself why do we need such a fancy thing as recursion to draw a square? Surely, repeat would be good enough. Indeed, repeat would be adequate if our interest were in the product but if our interest is in exploration, recursion allows us to make such changes as this.
I replaced square . side by square . side plus ten and this small modification will give rise to the most surprising and interesting mathematical results. Side is now 60, forward is 60, right 90 is going to bring the total down below that line. We will now do square 70, side will be 70, forward 70, right 90. You guessed it, square 80. Side will now become 80. Forward 80, right 90, and where’s it going to lead?
A full screen version shows the pattern. Forward the distance, right 90, increase the distance, repeat. We got this quite interesting result by making a small change to the procedure for square. Let’s follow that rule. Make a small change to this. Instead of 90 as the angle, let’s try 93. Notice how we get this effect of twisted squares. Notice that curved line that appears, an emergent phenomenon. Quite interesting.
Let’s try to do the same thing with triangles. First, straight triangles using 120. Same process, 123 forward a distance, right 123, increase the distance, repeat. A very interesting result. Since 90 and 120 gave something interesting, let’s try 180. It’s sort of in the same family but the result as a product anyway doesn’t look so interesting. Think about the process though. Maybe if you rotated that as it went up and down. For example, by trying 177 instead of 180, look how it turns as it goes backwards and forwards.
I see this as a result that’s interesting in lots of ways, visually, mathematically, and as an example of what happens when you follow a powerful [inaudible 00:08:41]. I think it’s pretty enough to try again without being cluttered with all that text on the screen. It’s worth thinking about too.
In all these spirals, there’s a common pattern. You draw a line, you turn, maybe 90, maybe 93, some other angle. We have been exploring what happens when you vary the angle, but you could vary something else. Instead of a line, you could have another figure. In fact, in the example I have on this other computer, the figure is a triangle. What’s going on in this program is draw the triangle, turn, draw a slightly larger triangle, turn, draw a slightly larger triangle. What comes out looks like a seashell.
I chose spirals as an entry point to recursion because such simple, such small changes can so often produce interesting, surprising, and beautiful results. The possibilities are endless, like recursion. Why don’t you go and try some yourselves and come back when you’re ready to move on.
We began part one watching children, enact a procedure. Very simple one, to “wow,” hands up, hands down, “wow”. We’ll begin part two revisiting the same children as they enact a rather more complex procedure which I have written on this piece of paper. This is a procedure that draws a spiral and does some other things as well. Without this last line I’m covering with my fingers, this is a perfectly familiar spiral procedure.
Spiral, does a forward, does a right, and runs spiral with side plus ten as input. That’s what makes it spiral. But what about that? What does print wow have to do with a spiral? What it has to do with is the difference between the intention of part one and part two. In part one, we tried to make our procedures simple in order to put spirals on the screen so we could study them. Here, our intention is to understand what goes on inside the procedures. Particularly to make mental models and to make mental models, we’ll sometimes, a little perversely, put tricky features into the procedures in order to check out how well we think about them.
Speaker 8: Okay, let’s get started. Laura, I want you to be the [inaudible 00:11:40]. We’ll need more actors, so I want all of you to stand in line over here and wait until you’re called. Laura. Here is your script, spiral ten.
Laura: My input is ten. Ten is not more than 50 so I don’t stop. Forward 10, right 90. Ten plus ten is 20, spiral 20.
Speaker 9: My input is less than 50, so I don’t stop. Forward 20, right 90. Twenty plus ten is 30, spiral 30.
Speaker 10: My input is 30 and 30 is less than 50, so I don’t stop. Forward 30, right 90. Thirty plus ten, spiral 40.
Speaker 11: My input is 40 and less than 50 so I keep going. Forward 40, right 90. Ten plus 40 is 50, spiral 50.
Speaker 12: My input is 50. It is not larger than 50 so I keep going. Forward 50. Ten, 20, 30, 40, 50, right 90.
Seymour Papert: Put yourself in the position of one of these children. Maybe the second to last with input 50, . side is 50, it’s not greater than 50, although it’s pretty close. You don’t stop. Forward, you do it, you ask the turtle do it, it doesn’t matter how you think about that, it’s all very straightforward. This is where there’s a tricky part. You need to find a subordinate. You yell “spiral”. Somebody comes and you give the input 50 plus 10 is 60.
Meantime, you go to sleep. You know when you wake up, this is where you’ll be and you’ll continue. Meanwhile, your subordinate is the one who’s going to stop. When your subordinate stops, you’ll woken up. You’re told, “Wake up. My job is done.” At this point you go ahead here, you’ll print wow, so wow is going to be printed many times, and then you wake up the one who appointed you to do a spiral.
What I’d like you to note particularly is the two way movement. Somebody appointed you, your boss, you appointed a subordinate. The subordinate woke you up, you woke up your boss. Note the two way movement, which is about to turnaround in the game.
Speaker 12: Fifty plus ten is 60. Spiral 60.
Speaker 13: My input is 60, 60 is more than 50 so I stop. Wake up, I’m finished.
Speaker 12: I’m not finished. Print wow. End. Wake up, I’m finished.
Speaker 11: Print wow.
Seymour Papert: Notice the two way action. The action rolls out as they do the forwards and rights, as they do the wows, it’s rolling back.
Speaker 10: Print wow. End.
Seymour Papert: All recursive procedures have this two way action. Though often, there is no visible effect of the roll back part.
Speaker 9: [crosstalk 00:15:33] Print wow. End. Wake up, I’m finished.
Speaker 8: Print wow.
Seymour Papert: I bring this segment to a close by suggesting an exercise which may help you appropriate acting out as a technique for your own mental modeling.
Speaker 8: Now I’m finished. [crosstalk 00:15:45]
Laura: [crosstalk 00:15:47] We did it.
Seymour Papert: Watch the performance again, but this time imagine that a change has been made. Print quote wow has been replaced by print . distance. What will the children put on the chalkboard? Test your prediction by writing the procedure and running it. Try some other modifications. Write a procedure that will do this. The turtle draws the spiral and then eats it back again. I’d like you to achieve this by replacing print quote wow by something else and leaving the rest of the procedure unchanged.
Imagine what would happen if you left out the stop rule. Think as you imagine this about the two children taking photographs, each taking a photograph of the other. One last piece of advice, end such a session as this with a brief discussion focused on a few salient points. Just as I’m trying to do with you now, just as in the next segment you will see us doing with the children you’ve just been watching.
One of the things that’s fun, in fact funny, about recursion, is that you solve a problem by getting somebody else to do most of the work. I call it ‘passing the buck’. You see this very clearly in an informant interview with two of the participants.
Speaker 13: Laura, that must’ve been a lot of work for you to draw this spiral.
Laura: No, actually I just did this line right here. Alex did the rest.
Speaker 13: Was it a lot of work for you?
Speaker 14: No, because I just did this line. I guess Matt must have done the rest.
Seymour Papert: The technique of ‘passing the buck’ has a lot of applications. For example, someone wants me to add up some numbers. Here’s a list of numbers. Looks like a lot of work, but I’m not going to do it. I’m going to take the first of the list and I’m going to hand on the rest. Add up those numbers for me please. All I need to know is that I’ve kept two and when I get the sum of the rest, I just have to add that on to two. There it comes, 37. Two plus 37 is 39. Your answer is 39. That’s my output.
We’ve seen the technique in the geometry of spirals, we’ve seen it in dealing with numbers. I’m going to make it really concrete now by looking at it in a problem involving sorting children’s building blocks. It’s really the same thing, however unsophisticated it seems.
I’ve recruited some people to help me find the largest of the set of five blocks. Of course I can see which is the largest, this is a toy problem we’re doing for the principal. Issues of method would be the same if there were 5,000. One method would be to compare them two by two. The recursive method is very different. Look at it like this, I have a problem, find the largest of a set of five.
I reduce the problem by taking one out and it doesn’t matter which, it could be a random choice, it doesn’t matter how I choose it. I have four blocks, which I pass on and so someone else has the simpler problem of finding the larger of a set of four blocks, and there the largest of a set of three blocks, and the largest of a set of two blocks, and he has no problem at all. He gives what he got. Now each player makes one comparison and passes back the larger.
Notice the two way movement typical of recursion. Eventually something comes back to me. I passed off a set, I got back a block. I make one comparison. This block which I know to be the largest of the set of four that I passed off and so the larger of these two must be the largest of the lot. This is it, the largest of the five blocks.
The two activities we’ve just seen, adding up a list of numbers and finding the smallest sticks are members of a very important family of tasks of algorithms that come up over and over again in mathematics and science and linguistics, in play and in programming. In Logo, we think of them as recursive reporters. What they have in common is this, they take a list, list of numbers, list of sticks, and from this they make a new Logo object which they give back to you. They have an output, that’s what makes them reporters.
I’m going to dig a little more deeply into this family of tasks and to how recursive reporters work by programming a particular case of which I happen to be rather fond.
I want to make a Logo version of the procedure I used to add up those numbers, or rather to avoid adding up those numbers which I did by passing the buck. A first golden rule in designing a procedure like this is exercise your options and here I can do that by at least choosing the language. I call the procedure ‘Addup’ and I call it’s input numbers so I can read the whole thing as ‘Addup the numbers’ or ‘Addup of the numbers’.
A next golden rule is to put down whatever bits and pieces of information you have. This is a reporter, it’s bound to have an output. The output is bound to be the sum of something, we’ll come back to what it might be, and it has end. All Logo procedures do. Not much? Yes, it is. It’s a skeleton that will help ground our thinking and I’ve left holes to fill in the missing parts.
Output sum of what? Remember concretely and that’s another golden rule, the situation most like this. When I was adding up the numbers on the paper list, I kept the first of the numbers and then I said to somebody else, “Add up,” and gave but first of the numbers, what was left when I tore off the first, and so just remembering that concrete situation guides us in making the core part of this Logo procedure.
Think concretely now of the process of playing it out. For example, the spiral game. Each actor passes the buck to the next. One addup says, “Add up. Add up this for me.” That one says, “Add up. Add this one for me.” That’s going to stop somewhere, there has to be a part of the procedure. That’s what this hole is for where the buck stops. I don’t know what it is yet so I put down vaguely what I know about it.
It’s going to be if something or another, well an easy case. Do something. Now we can focus bit by bit, if what. Think of the block situation. The easy case was when there was one block left. If one of numbers left, what happens? Well, give what you got, there’s no problem there. Adding up one number isn’t a problem. What is a problem is that this isn’t yet Logo but that’s not much of a problem. If one of numbers left we can translate into if one equals count of numbers and that is Logo, and give what you got, give turns into output, first of numbers. When there’s only one number in the list, first of the numbers is it.
That’s our procedure and one last step remains, another golden rule. I’m going to label the two parts. This part is called ‘pass the buck’, that is called ‘the buck stops here’. I’m setting up a private language, something you should do in any problem. A private language for the micro world of the problem that I use not only to talk to others but to talk to myself in thinking about the problem.
What you see on the screen is the output of a visualization procedure which I’ll use to follow the way addup works. You’ll see this run in a moment but please don’t try and follow the details, get the general [inaudible 00:25:08]. Then go to the diskette, run this procedure which you’ll find there, focus on the details, and then come back to review the tape afterwards.
This procedure is a little bit like a simulation of the children simulating the way a procedure works. It’s going to run a series of actors which will carry out addup and addup and addup. Let’s see how it goes. We begin with a Logo instruction of print, addup, 3, 4, 5, and of course this has to print 12, but let’s look at the process. The color coding you’ll pick up; green means the act of procedure, blue means its input. Running this procedure requires an actor and the copy of the procedure in gold will always represent an actor carrying it out.
This actor gets the input 3, 4, 5, and dots numbers will be replaced line by line by 3, 4, 5 as we need it. There’s the first line. If one is equal to count 3, 4, 5, which of course it isn’t, and so if is going to get false, and this isn’t going to happen, the part we called ‘the buck stops’ is not going to be operative here, the work will be done by the ‘passing the buck’ section. Output sum, sum of what, first, 3, 4, 5 is just three and here is the important part, addup but first 3, 4, 5, addup 4, 5, addup, and a new actor appears.
This one will get as its input 4, 5. Notice the problem simplifying as the list gets smaller, but it’s not at the end yet. Count 4, 5 is true so if once more we’ll get false, this won’t operate, we’ll move to the ‘pass the buck’ section. Sum of what. First 4, 5 is of course 4, and then finally, add up but first 4, 5 is addup 5. If this procedure had any sense it would realize that there’s no problem there, but it’s dumb and so it calls another addup. Addup and tells it 5 is the input.
This time one will be count of numbers. Count of a list with one thing in it is one so one equals one and if gets input true. We will see output first of what? First of this list is just 5 and now 5 will be passed back. The trail of green shows where information was requested. This 5 was requested there and it’s passed back to there. This sum now has its two inputs, 4 and 5, you can add them together to get 9. It’s now ready to report to its boss, the previous actor. Nine will go back there, addup 4, 5 of course is 9. This sum gets 3, 9 as inputs, that’s 12. Aren’t they smart? Output 12 goes up there and print prints 12. That is the product we expected.
This module was called Images of Recursion but in fact turned out to be an essay on solving problems. There’s no conflict. In fact for me, recursion and Logo and computers are all interesting mainly because they provide us with such rich areas to explore in search of techniques and skills and images for solving problems of every kind.