<HTML> <HEAD> <TITLE>Computer Science Logo Style vol 1 ch 9: How Recursion Works</TITLE> </HEAD> <BODY> <CITE>Computer Science Logo Style</CITE> volume 1: <CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT <H1>How Recursion Works</H1> <TABLE width="100%"><TR><TD> <IMG SRC="../csls1.jpg" ALT="cover photo"> <TD><TABLE> <TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian Harvey</A><BR>University of California, Berkeley</CITE> <TR><TD align="right"><BR> <TR><TD align="right"><A HREF="../pdf/v1ch09.pdf">Download PDF version</A> <TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A> <TR><TD align="right"><A HREF="../v1ch8/v1ch8.html"><STRONG>BACK</STRONG></A> chapter thread <A HREF="../v1ch10/v1ch10.html"><STRONG>NEXT</STRONG></A> <TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT Press web page for Computer Science Logo Style</A> </TABLE></TABLE> <HR> <P>The last two chapters were about how to write recursive procedures. This chapter is about how to <EM>believe in</EM> recursive procedures, and about understanding the process by which Logo carries them out. <P> <H2>Little People and Recursion</H2> <P> In Chapter 3, I introduced you to the metaphor of a computer full of little elves. Each elf is an expert on a particular procedure. I promised that this metaphor would be helpful later, when we'd have to think about two little people carrying out the same procedure at the same time. Well, "later" is now. <P>I want to use the elf metaphor to think about the <CODE>downup</CODE> example of the previous chapter: <PRE>to downup :word print :word if equalp count :word 1 [stop] downup butlast :word print :word end </PRE> <P>Recall that we are imagining the computer to be full of elves, each of whom is a specialist in carrying out some procedure. There are <CODE>print</CODE> elves, <CODE>count</CODE> elves, <CODE>stop</CODE> elves, and so on. Each elf has some number of pockets, used to hold the inputs for a particular invocation of a procedure. So a <CODE> print</CODE> elf will have one pocket, while an <CODE>equalp</CODE> elf needs two pockets. <P> <P>We're going to be most interested in the <CODE>downup</CODE> elves and the contents of their pockets. To help you keep straight which elf is which, I'm going to name the <CODE>downup</CODE> elves alphabetically: the first one will be Ann, then Bill, then Cathy, then David, and so on. Since we aren't so interested in the other elves, I won't bother naming them. <P>»If you're reading this with a group of other people, you may find it helpful for each of you to take on the role of one of the <CODE>downup</CODE> elves and actually stick words in your pockets. If you have enough people, some of you should also serve as elves for the primitive procedures used, like <CODE>print</CODE> and <CODE>if</CODE>. <P>What happens when you type the instruction <PRE>downup "hello </PRE> to Logo? The Chief Elf reads this instruction and sees that it calls for the use of the procedure named <CODE>downup</CODE>. She therefore recruits Ann, an elf who specializes in that procedure. Since <CODE>downup</CODE> has one input, the Chief Elf has to give Ann something to put in her one pocket. Fortunately, the input you provided is a quoted word, which evaluates to itself. No other elves are needed to compute the input. Ann gets the word <CODE>hello</CODE> in her pocket. <P>Ann's task is to carry out the instructions that make up the definition of <CODE>downup</CODE>. The first instruction is <PRE>print :word </PRE> This, you'll remember, is an abbreviation for <PRE>print thing "word </PRE> Ann must hire two more elves, a <CODE>print</CODE> specialist and a <CODE>thing</CODE> specialist. The <CODE>print</CODE> elf can't begin his work until he's given something to put in his pocket. Ann asks the <CODE> thing</CODE> elf to figure out what that input should be. The <CODE>thing</CODE> elf also gets an input, namely the word <CODE>word</CODE>. As we saw in Chapter 3, <CODE>word</CODE> is what's written on the name tag in Ann's pocket, since <CODE>word</CODE> is the name of <CODE>downup</CODE>'s input. So the <CODE>thing</CODE> elf looks in that pocket, where it finds the word <CODE>hello</CODE>. That word is then given to the <CODE>print</CODE> elf, who prints it on your computer screen. <P>Ann is now ready to evaluate the second instruction: <PRE>if equalp count :word 1 [stop] </PRE> <P>Ann must hire several other elves to help her: an <CODE>if</CODE> elf, a <CODE>count</CODE> elf, and a <CODE>thing</CODE> elf. I won't go through all the steps in computing the inputs to <CODE>if</CODE>; since the <CODE>count</CODE> of the word <CODE>hello</CODE> is not 1, the first input to <CODE>if</CODE> turns out to be the word <CODE>false</CODE>. The second input to <CODE>if</CODE> is, of course, the list <CODE>[stop]</CODE>. (Notice that Ann does <EM>not</EM> hire a <CODE>stop</CODE> specialist. A list inside square brackets evaluates to itself, just like a quoted word, without invoking any procedures. If the first input to <CODE>if</CODE> had turned out to be <CODE>true</CODE>, it would have been the <CODE>if</CODE> elf who would have hired a <CODE>stop</CODE> elf to carry out the instruction inside the list.) Since its first input is <CODE>false</CODE>, the <CODE>if</CODE> elf ends up doing nothing. <P>Ann's third instruction is <PRE>downup butlast :word </PRE> <P>Here's where things start to get interesting. Ann must hire <EM>another</EM> <CODE>downup</CODE> specialist, named Bill. (Ann can't carry out this new <CODE>downup</CODE> instruction herself because she's already in the middle of a job of her own.) Ann must give Bill an input to put in his pocket; to compute this input, she hires a <CODE> butlast</CODE> elf and a <CODE>thing</CODE> elf. They eventually come up with the word <CODE>hell</CODE> (the <CODE>butlast</CODE> of <CODE>hello</CODE>), and that's what Ann puts in Bill's pocket. <P>We now have two active <CODE>downup</CODE> elves, Ann and Bill. Each has a pocket. Both pockets are named <CODE>word</CODE>, but they have different contents: Ann's <CODE>word</CODE> pocket contains <CODE>hello</CODE>, while Bill's <CODE>word</CODE> pocket contains <CODE>hell</CODE>. <P> <CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch9/elf2.gif" ALT="figure: elf2"></CENTER> <P>Here is what this metaphor represents, in more technical language: Although there is only one <EM>procedure</EM> named <CODE> downup</CODE>, there can be more than one <EM>invocation</EM> of that procedure in progress at a particular moment. (An invocation of a procedure is also sometimes called an <EM>instantiation</EM> of the procedure.) Each invocation has its own local variables; at this moment there are <EM>two</EM> variables named <CODE>word</CODE>. It is perfectly possible for two variables to have the same name as long as they are associated with (local to) different procedure invocations. <P>If you had trouble figuring out how <CODE>downup</CODE> works in Chapter 7, it's almost certainly because of a misunderstanding about this business of local variables. That's what makes the elf metaphor so helpful. For example, if you're accustomed to programming in BASIC, then you're familiar with <EM>global</EM> variables as the only possibility in the language. If all variables were global in Logo, then there could only be one variable in the entire computer named <CODE>word</CODE>. Instead of representing variables as pockets in the elves' clothes, we'd have to represent them as safe deposit boxes kept in some central bank and shared by all the elves. <P>But even if you're familiar with Logo's use of local variables, you may have been thinking of the variables as being local to a <EM> procedure,</EM> instead of understanding that they are local to an <EM> invocation</EM> of a procedure. In that case you may have felt perfectly comfortable with the procedures named <CODE>downup1</CODE>, <CODE> downup2</CODE>, and so on, each of them using a separate variable named <CODE> word</CODE>. But you may still have gotten confused when the <EM>same</EM> variable <CODE>word</CODE>, the one belonging to the single procedure <CODE> downup</CODE>, seemed to have several values at once. <P>If you were confused in that way, here's how to use the elf metaphor to help yourself get unconfused: Suppose the procedure definitions are written on scrolls, which are kept in a library. There is only one copy of each scroll. (That is, there is only one definition for a given procedure.) All the elves who specialize in a particular procedure, like <CODE>downup</CODE>, have to share the same scroll. Well, if variables were local to a procedure, they'd be pockets in the <EM> scroll,</EM> rather than pockets in the <EM>elves' jackets.</EM> By directing your attention to the elves (the invocations) instead of the scrolls (the procedure definitions), you can see that there can be two variables with the same name (<CODE>word</CODE>), associated with the same procedure (<CODE>downup</CODE>), but belonging to different invocations (represented by the elves Ann and Bill). <P>We still have several more elves to meet, so I'm going to pass over some of the details more quickly now. We've just reached the point where Bill is ready to set to work. For his first instruction he hires a <CODE>print</CODE> elf, who prints the word <CODE>hell</CODE> on your screen. Why <CODE>hell</CODE> and not <CODE>hello</CODE>? The answer is that when Bill hires a <CODE>thing</CODE> expert to evaluate the expression <CODE> :word</CODE>, the <CODE>thing</CODE> rules say that that expert must look <EM> first</EM> in Bill's pockets, <EM>then</EM> (if Bill didn't have a pocket named <CODE>word</CODE>) in Ann's pockets. <P>Bill then carries out the <CODE>if</CODE> instruction, which again has no effect. Then Bill is ready for the <CODE>downup</CODE> instruction. He hires a third <CODE>downup</CODE> elf, named Cathy. Bill puts the word <CODE> hel</CODE> in Cathy's pocket. There are now three elves, all with pockets named <CODE>word</CODE>, each with a different word. <P>Cathy is now ready to get to work. Don't forget, though, that Ann and Bill haven't finished their jobs. Bill is still working on his third instruction, waiting for Cathy to report the completion of her task. Similarly, Ann is waiting for Bill to finish. <P>Cathy evaluates her first instruction, printing <CODE>hel</CODE> on the screen. She evaluates the <CODE>if</CODE> instruction, with no effect. Then she's ready for the <CODE>downup</CODE> instruction, the third one in the procedure definition. To carry out this instruction, she hires David, a fourth <CODE>downup</CODE> expert. She puts the word <CODE>he</CODE> in his pocket. <P>David's career is like that of the other <CODE>downup</CODE> elves we've met so far. He starts by printing his input, the word <CODE>he</CODE>. He evaluates the <CODE>if</CODE> instruction, with no effect. (The <CODE>count</CODE> of the word <CODE>he</CODE> is still not equal to 1.) He then gets to the recursive invocation of <CODE>downup</CODE>, for which he hires a fifth expert, named Ellen. He puts the word <CODE>h</CODE> in Ellen's pocket. <P>Ellen's career is <EM>not</EM> quite like that of the other elves. It starts similarly: she prints her input, the word <CODE>h</CODE>, on your screen. Then she prepares to evaluate the <CODE>if</CODE> instruction. This time, though, the first input to <CODE>if</CODE> turns out to be the word <CODE>true</CODE>, since the <CODE>count</CODE> of <CODE>h</CODE> is, indeed, 1. Therefore, the <CODE>if</CODE> elf evaluates the instruction contained in its second input, the list <CODE>[stop]</CODE>. It hires a <CODE>stop</CODE> elf, whose job is to tell Ellen to stop working. (Why Ellen? Why not one of the other active elves? There are <EM>seven</EM> elves active at the moment: Ann, Bill, Cathy, David, Ellen, the <CODE>if</CODE> elf, and the <CODE> stop</CODE> elf. The rule is that a <CODE>stop</CODE> elf stops the <EM> lowest-level invocation of a user-defined procedure.</EM> <CODE>If</CODE> and <CODE>stop</CODE> are primitives, so they don't satisfy the <CODE>stop</CODE> elf. The remaining five elves are experts in <CODE>downup</CODE>, a user-defined procedure; of the five, Ellen is the lowest-level invocation.) <P>(By the way, the insistence of <CODE>stop</CODE> on a user-defined procedure to stop is one of the few ways in which Logo treats such procedures differently from primitive procedures. If you think about it, you'll see that it would be useless for <CODE>stop</CODE> to stop just the invocation of <CODE>if</CODE>. That would mean that the <CODE>if</CODE> instruction would never do anything of interest and there would be no way to stop a procedure of your own conditionally. But you can imagine other situations in which it would be nice to be able to <CODE>stop</CODE> a primitive. Here's one: <PRE>repeat 100 [print "hello if equalp random 5 0 [stop]] </PRE> <P>If it worked, this instruction would print the word <CODE> hello</CODE> some number of times, up to 100, but with a 20 percent chance of stopping after each time. In fact, though, you can't use <CODE> stop</CODE> to stop a <CODE>repeat</CODE> invocation.) <P>Let's review what's been printed so far: <PRE>hello printed by Ann hell printed by Bill hel printed by Cathy he printed by David h printed by Ellen </PRE> <P>Ellen has just stopped. She reports back to David, the elf who hired her. He's been waiting for her; now he can continue with his own work. David is up to the fourth and final instruction in the definition of <CODE>downup</CODE>: <PRE>print :word </PRE> <P>What word will David print? For David, <CODE>:word</CODE> refers to the contents of <EM>his own</EM> pocket named <CODE>word</CODE>. That is, when David hires a <CODE>thing</CODE> expert, that expert looks first in David's pockets, before trying Cathy's, Bill's, and Ann's. The word in David's <CODE>word</CODE> pocket is <CODE>he</CODE>. So that's what David prints. <P>Okay, now David has reached the end of his instructions. He reports back to his employer, Cathy. She's been waiting for him, so that she can continue her own work. She, too, has one more <CODE>print</CODE> instruction to evaluate. She has the word <CODE>hel</CODE> in her <CODE>word</CODE> pocket, so that's what she prints. <P>Cathy now reports back to Bill. He prints his own word, <CODE>hell</CODE>. He reports back to Ann. She prints her word, <CODE>hello</CODE>. <P>When Ann finishes, she reports back to the Chief Elf, who prints a question mark on the screen and waits for you to type another instruction. <P>Here is the complete effect of this <CODE>downup</CODE> instruction: <PRE>hello printed by Ann hell printed by Bill hel printed by Cathy he printed by David h printed by Ellen he printed by David hel printed by Cathy hell printed by Bill hello printed by Ann </PRE> <P>»You might want to see if the little person metaphor can help you understand the working of the <CODE>inout</CODE> procedure from Chapter 7. Remember that each elf carrying out the recursive procedure needs two pockets, one for each input. <P><H2>Tracing</H2> <P>Many people find the idea of multiple, simultaneous invocations of a single procedure confusing. To keep track of what's going on, you have to think about several "levels" of evaluation at once. "Where is <CODE>downup</CODE> up to right now?" -- "Well, it depends what you mean. The lowest-level <CODE>downup</CODE> invocation has just evaluated its first <CODE>print</CODE> instruction. But there are three other invocations of <CODE>downup</CODE> that are in the middle of evaluating their recursive <CODE>downup</CODE> instructions." This can be especially confusing if you've always been taught that the computer can only do one thing at a time. People often emphasize the <EM>sequential</EM> nature of the computer; what we've been saying about recursion seems to violate that nature. <P>If this kind of confusion is a problem for you, it may help to think about a procedure like <CODE>downup</CODE> by <EM>tracing</EM> its progress. That is, we can tell the procedure to print out extra information each time it's invoked, to help you see the sequence of events. <P>Just for reference, here's <CODE>downup</CODE> again: <P><PRE>to downup :word print :word if equalp count :word 1 [stop] downup butlast :word print :word end </PRE> <P>The trace command takes a procedure name (or a list of procedure names, to trace more than one) as its input. It tells Logo to notify you whenever that procedure is invoked: <P><PRE>? <U>trace "downup</U> ? <U>downup "logo</U> <SMALL><CODE>( downup "logo ) </CODE></SMALL>logo <SMALL><CODE> ( downup "log ) </CODE></SMALL>log <SMALL><CODE> ( downup "lo ) </CODE></SMALL>lo <SMALL><CODE> ( downup "l ) </CODE></SMALL>l <SMALL><CODE> downup stops </CODE></SMALL>lo <SMALL><CODE> downup stops </CODE></SMALL>log <SMALL><CODE> downup stops </CODE></SMALL>logo <SMALL><CODE>downup stops </CODE></SMALL></PRE> <P>To make this result a little easier to read, I've printed the lines that are generated by the tracing in smaller letters than the lines generated by <CODE>downup</CODE> itself. Of course the actual computer output all looks the same. <P>Each line of tracing information is indented by a number of spaces equal to the number of traced procedure invocations already active--the <EM> level</EM> of procedure invocation. By looking only at the lines between one <CODE>downup</CODE> invocation and the equally-indented stopping line, you can see how much is accomplished by each recursive call. For example, the innermost invocation (at level 4) prints only the letter <CODE>l</CODE>. <P><H2>Level and Sequence</H2> <P> The result of tracing <CODE>downup</CODE> is most helpful if you think about it two-dimensionally. If you read it <EM>vertically,</EM> it represents the <EM>sequence</EM> of instructions that fits the traditional model of computer programming. That is, the order of the printed lines represents the order of events in time. First the computer enters <CODE>downup</CODE> at level 1. Then it prints the word <CODE>logo</CODE>. Then it enters <CODE>downup</CODE> at level 2. Then it prints <CODE>log</CODE>. And so on. Each printed line, including the "official" lines as well as the tracing lines, represents a particular instruction, carried out at a particular moment. Reading the trace vertically will help you fit <CODE>downup</CODE>'s recursive method into your sequential habits of thought. <P> On the other hand, if you read the trace <EM>horizontally,</EM> it shows you the hierarchy of <EM>levels</EM> of <CODE>downup</CODE>'s invocations. To see this, think of the trace as divided into two overlapping columns. The left column consists of the official pattern of words printed by the original <CODE>downup</CODE>. In the right column, the pattern of entering and exiting from each level is shown. The lines corresponding to a particular level are indented by a number of spaces that corresponds to the level number. For example, find the line <PRE><SMALL><CODE> ( downup "log ) </CODE></SMALL></PRE> <P>and the matching <PRE><SMALL><CODE> downup stops </CODE></SMALL></PRE> <P>Between these two lines you'll see this: <PRE>log <SMALL><CODE> ( downup "lo ) </CODE></SMALL>lo <SMALL><CODE> ( downup "l ) </CODE></SMALL>l <SMALL><CODE> downup stops </CODE></SMALL>lo <SMALL><CODE> downup stops </CODE></SMALL>log </PRE> <P>What this shows is that levels 3 and 4 are <EM>part of</EM> level 2. You can see that the traced invocation and stopping lines for levels 3 and 4 begin further to the right than the ones for level 2. Similarly, the lines for level 4 are further indented than the ones for level 3. This variation in indentation is a graphic display of the superprocedure/subprocedure relationships among the various invocations. <P>There are two ways of thinking about the lines that aren't indented. One way is to look at all such lines within, say, level 2: <PRE>log lo l lo log </PRE> <P>This tells you that those five lines are printed somehow within the activity of level 2. (In terms of the little people metaphor, those lines are printed by Bill, either directly or through some subordinate elf.) Another way to look at it is this: <PRE><SMALL><CODE> ( downup "log ) </CODE></SMALL>log <SMALL><CODE> ( downup "lo ) </CODE></SMALL> ... <SMALL><CODE> downup stops </CODE></SMALL>log <SMALL><CODE> downup stops </CODE></SMALL></PRE> <P>What this picture is trying to convey is that only the two <CODE>log</CODE> lines are <EM>directly</EM> within the control of level 2. The three shorter lines (<CODE>lo</CODE>, <CODE>l</CODE>, <CODE>lo</CODE>) are delegated to level 3. <P>We've seen three different points of view from which to read the trace, one vertical and two horizontal. The vertical point of view shows the sequence of events in time. The horizontal point of view can show either the <EM>total</EM> responsibility of a given level or the <EM>direct</EM> responsibility of the level. To develop a full understanding of recursion, the trick is to be able to see all of these aspects of the program at the same time. <P>»Try invoking the traced <CODE>downup</CODE> with a single-letter input. Make a point of reading the resulting trace from all of these viewpoints. Then try a two-letter input. <P> <H2>Instruction Stepping</H2> <P>Perhaps you are comfortable with the idea of levels of invocation, but confused about the particular order of instructions within <CODE> downup</CODE>. Why should the <CODE>if</CODE> instruction be where it is, instead of before the first <CODE>print</CODE>, for example? Logo's <CODE>step</CODE> command will allow you to examine each instruction line within <CODE>downup</CODE> as it is carried out: <P><PRE>? <U>step "downup</U> ? <U>downup "ant</U> <SMALL><CODE>[print :word] >>> </CODE></SMALL>ant <SMALL><CODE>[if equalp count :word 1 [stop]] >>> [downup butlast :word] >>> [print :word] >>> </CODE></SMALL>an <SMALL><CODE>[if equalp count :word 1 [stop]] >>> [downup butlast :word] >>> [print :word] >>> </CODE></SMALL>a <SMALL><CODE>[if equalp count :word 1 [stop]] >>> [print :word] >>> </CODE></SMALL>an <SMALL><CODE>[print :word] >>> </CODE></SMALL>ant </PRE> <P>After each of the lines ending with <CODE>>>></CODE>, Logo waits for you to press the RETURN or ENTER key. <P>You can combine <CODE>trace</CODE> and <CODE>step</CODE>: <P><PRE>? <U>step "downup</U> ? <U>trace "downup</U> ? <U>downup "ant</U> <SMALL><CODE>( downup "ant ) [print :word] >>> </CODE></SMALL>ant <SMALL><CODE>[if equalp count :word 1 [stop]] >>> [downup butlast :word] >>> ( downup "an ) [print :word] >>> </CODE></SMALL>an <SMALL><CODE> [if equalp count :word 1 [stop]] >>> [downup butlast :word] >>> ( downup "a ) [print :word] >>> </CODE></SMALL>a <SMALL><CODE> [if equalp count :word 1 [stop]] >>> downup stops [print :word] >>> </CODE></SMALL>an <SMALL><CODE> downup stops [print :word] >>> </CODE></SMALL>ant <SMALL><CODE>downup stops </CODE></SMALL></PRE> <P>In this case, the <CODE>step</CODE> lines are indented to match the <CODE>trace</CODE> lines. <P>Once a procedure is <CODE>trace</CODE>d or <CODE>step</CODE>ped, it remains so until you use the <CODE>untrace</CODE> or <CODE>unstep</CODE> command to counteract the tracing or stepping. <P>»Try drawing a vertical line extending between the line <PRE> ( downup "an ) </PRE> <P>and the equally indented <PRE> downup stops </PRE> <P>Draw the line just to the left of the printing, after the indentation. The line you drew should also touch exactly four instruction lines. These four lines make up the entire definition of the <CODE>downup</CODE> procedure. If we restrict our attention to one particular invocation of <CODE>downup</CODE>, like the one you've marked, you can see that each of <CODE>downup</CODE>'s instructions is, indeed, evaluated in the proper sequence. Below each of these instruction lines, you can see the effect of the corresponding instruction. The two <CODE>print</CODE> instructions each print one line in the left (unindented) column. (In this case, they both print the word <CODE>an</CODE>.) The <CODE>if</CODE> instruction has no visible effect. But the recursive invocation of <CODE>downup</CODE> has quite a large effect; it brings into play the further invocation of <CODE>downup</CODE> with the word <CODE>a</CODE> as input. <P>One way to use the stepping information is to "play computer." Pretend you are the Logo interpreter, carrying out a <CODE>downup</CODE> instruction. Exactly what would you do, step by step? As you work through the instructions making up the procedure definition, you can check yourself by comparing your activities to what's shown on the screen. <P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> <P><A HREF="../v1ch8/v1ch8.html"><STRONG>BACK</STRONG></A> chapter thread <A HREF="../v1ch10/v1ch10.html"><STRONG>NEXT</STRONG></A> <P> <ADDRESS> <A HREF="../index.html">Brian Harvey</A>, <CODE>bh@cs.berkeley.edu</CODE> </ADDRESS> </BODY> </HTML>