diff options
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v1ch7')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch7/recur1.html | 931 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch7/v1ch7.html | 931 |
2 files changed, 1862 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v1ch7/recur1.html b/js/games/nluqo.github.io/~bh/v1ch7/recur1.html new file mode 100644 index 0000000..e8a9147 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch7/recur1.html @@ -0,0 +1,931 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 7: Introduction to Recursion</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Introduction to Recursion</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/v1ch07.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="../v1ch6/v1ch6.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch8/v1ch8.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> +My goal in this chapter is to write a procedure named <CODE>downup</CODE> +that behaves like this: + +<PRE> +? <U>downup "hello</U> +hello +hell +hel +he +h +he +hel +hell +hello +? <U>downup "goodbye</U> +goodbye +goodby +goodb +good +goo +go +g +go +goo +good +goodb +goodby +goodbye +</PRE> + +<P> +The programming techniques we've used so far in this book +don't allow an elegant solution to this problem. We'll use a +new technique called <EM>recursion:</EM> writing a procedure that uses +<EM>itself</EM> as a subprocedure. + +<P> +We're going to solve this problem using recursion. It turns out that the +idea of recursion is both very powerful--we can solve a <EM>lot</EM> of +problems using it--and rather tricky to understand. That's why I'm going +to explain recursion several different ways in the coming chapters. Even +after you understand one of them, you'll probably find that thinking about +recursion from another point of view enriches your ability to use this idea. +The explanation in this chapter is based on the <EM>combining method.</EM> + +<H2>Starting Small</H2> + +<P> +My own favorite way to understand recursion is based on the general +problem-solving strategy of solving a complicated problem by starting +with a simpler version. To solve the <CODE>downup</CODE> problem, I'll start +by solving this simpler version: write a <CODE>downup</CODE> procedure that +works only for a single-character input word. (You can't get much +simpler than that!) Here's my solution: + +<PRE> +to downup1 :word +print :word +end + +? <U>downup1 "j</U> +j +</PRE> + +<P> +See how well it works? + +<H2>Building Up</H2> + +<P> +Of course, <CODE>downup1</CODE> won't work at all if you give it an input +longer than one character. You may not think this was such a big +step. But bear with me. Next I'll write a procedure that acts like +<CODE>downup</CODE> when you give it a two-letter input word: + +<PRE> +to downup2 :word +print :word +print butlast :word +print :word +end + +? <U>downup2 "it</U> +it +i +it +</PRE> + +<P> +We could keep this up for longer and longer input words, but each procedure +gets more and more complicated. Here's <CODE>downup3</CODE>: + +<PRE> +to downup3 :word +print :word +print butlast :word +print butlast butlast :word +print butlast :word +print :word +end +</PRE> + +<P> +» How many <CODE>print</CODE> instructions would I need to write <CODE>downup4</CODE> +this way? How many would I need for <CODE>downup20</CODE>? + +<P> +Luckily there's an easier way. Look at the result of invoking <CODE>downup3</CODE>: + +<PRE> +? <U>downup3 "dot</U> +dot +<TABLE border="5" rules="none" frame="box" noshade><TR><TD>do +<TR><TD>d +<TR><TD>do</TABLE>dot +</PRE> + +<P> +The trick is to recognize that the boxed lines are what we'd get by invoking +<CODE>downup2</CODE> with the word <CODE>do</CODE> as input. So we can find +the instructions in <CODE>downup3</CODE> that print those three lines and +replace them with one instruction that calls <CODE>downup2</CODE>: + +<PRE> +to downup3 :word +print :word +<U>downup2 butlast :word</U> +print :word +end +</PRE> + +<P> +You might have to think a moment to work out where the +<CODE>butlast</CODE> came from, but consider +that we're given the word <CODE>dot</CODE> and we +want the word <CODE>do</CODE>. + +<P> +Once we've had this idea, it's easy to extend it to longer words: + +<PRE> +to downup4 :word +print :word +downup3 butlast :word +print :word +end + +to downup5 :word +print :word +downup4 butlast :word +print :word +end +</PRE> + +<P> +» Can you rewrite <CODE>downup2</CODE> so that it looks like these others? + +<P> +» Before going on, make sure you really understand these procedures by +answering these questions: What happens if you use one of these numbered +versions of <CODE>downup</CODE> with an input that is too long? What if the input +is too short? + +<H2>Generalizing the Pattern</H2> + +<P> +We're now in good shape as long as we want to <CODE>downup</CODE> short +words. We can pick the right version of <CODE>downup</CODE> for the length +of the word we have in mind: + +<PRE> +? <U>downup5 "hello</U> +hello +hell +hel +he +h +he +hel +hell +hello +? <U>downup7 "goodbye</U> +goodbye +goodby +goodb +good +goo +go +g +go +goo +good +goodb +goodby +goodbye +</PRE> + +<P> +Having to count the number of characters in the word is a +little unaesthetic, but we could even have the computer do that for us: + +<PRE> +to downup :word +if equalp count :word 1 [downup1 :word] +if equalp count :word 2 [downup2 :word] +if equalp count :word 3 [downup3 :word] +if equalp count :word 4 [downup4 :word] +if equalp count :word 5 [downup5 :word] +if equalp count :word 6 [downup6 :word] +if equalp count :word 7 [downup7 :word] +end +</PRE> + +<P> +There's only one problem. What if we want to be able to say + +<PRE> +downup "antidisestablishmentarianism +</PRE> + +<P> +You wouldn't want to have to type in separate versions of +<CODE>downup</CODE> all the way up to <CODE>downup28</CODE>! + +<P> +What I hope you're tempted to do is to take advantage of the +similarity of all the numbered <CODE>downup</CODE> procedures by combining +them into a single procedure that looks like this: + +<PRE> +to downup :word +print :word +downup butlast :word +print :word +end +</PRE> + +<P> +(Remember that Logo's <CODE>to</CODE> command won't let you +redefine <CODE>downup</CODE> if you've already typed in my earlier version +with all the <CODE>if</CODE> instruction lines. Before you can type in the +new version, you have to <CODE>erase</CODE> the old one.) + +<P> +Compare this version of <CODE>downup</CODE> with one of the numbered +procedures like <CODE>downup5</CODE>. Do you see that this combined version +should work just as well, if all the numbered +<CODE>downup</CODE> procedures are identical except for the numbers in the +procedure names? +Convince yourself that that makes sense. + +<P> +» Okay, now try it. + +<H2>What Went Wrong?</H2> + +<P> +You probably saw something like this: + +<PRE> +? <U>downup "hello</U> +hello +hell +hel +he +h + +butlast doesn't like as input in downup +</PRE> + +<P> +There's nothing wrong with the reasoning I used in the last section. +If all the numbered <CODE>downup</CODE> procedures are identical except for +the numbers, it should work to replace them all with a single +procedure following the same pattern. + +<P> +The trouble is that the numbered <CODE>downup</CODE> procedures +<EM>aren't</EM> quite +all identical. The exception is <CODE>downup1</CODE>. If it +were like the others, it would look like this: + +<PRE> +to downup1 :word +print :word +<U>downup0 butlast :word</U> +<U>print :word</U> +end +</PRE> + +<P> +Review the way the numbered <CODE>downup</CODE>s work to make sure +you understand why <CODE>downup1</CODE> is different. Here's what happens +when you invoke one of the numbered versions: + + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch7/downup.gif" ALT="<P>figure: downup"></CENTER> + +<P> +In this chart, instructions within a particular procedure +are indented the same amount. For example, the lines +<CODE>print "hello</CODE> and +<CODE>downup4 "hell</CODE> are part of <CODE>downup5</CODE>, as is +the line <CODE>print "hello</CODE> at the very end of the chart. The lines +in between are indented more because they're part of <CODE>downup4</CODE> +and its subprocedures. + +<P> +(By the way, the lines in the chart don't show actual instructions in +the procedure definitions. Otherwise all the <CODE>print</CODE> lines would +say <CODE>print :word</CODE> instead of showing actual words. In the chart +I've already evaluated the inputs to the commands.) + +<P> +The point of the chart is that <CODE>downup1</CODE> has to be special because +it marks the end of the "down" part of the problem and the +beginning of the "up" part. <CODE>downup1</CODE> doesn't invoke a +lower-numbered <CODE>downup</CODE> subprocedure because there's no smaller +piece of the word to print. + +<P> +» Okay, Logo knows when to stop the "down" part of the program +because <CODE>downup1</CODE> is different from the other procedures. +Question: How does Logo know when to stop the "up" part of the +program? Why doesn't <CODE>downup5</CODE>, in this example, have to be +written differently from the others? + +<H2>The Stop Rule</H2> + +<P> +Our attempt to write a completely general <CODE>downup</CODE> procedure has +run into trouble because we have to distinguish two cases: the special +case in which the input word contains only one character and the +general case for longer input words. We can use <CODE>ifelse</CODE> to +distinguish the two cases: + +<PRE> +to downup :word +ifelse equalp count :word 1 [downup.one :word] [downup.many :word] +end + +to downup.one :word +print :word +end + +to downup.many :word +print :word +downup butlast :word +print :word +end +</PRE> + +<P> +You'll find that this version of the <CODE>downup</CODE> program actually +works correctly. +Subprocedure <CODE>downup.one</CODE> is exactly like the +old <CODE>downup1</CODE>, while <CODE>downup.many</CODE> is like the version +of <CODE>downup</CODE> that didn't work. + +<P> +It's possible to use the same general idea, however--distinguishing +the special case of a one-letter word--without having +to set up this three-procedure structure. Instead we can take +advantage of the fact that <CODE>downup.one</CODE>'s single instruction is +the same as the first instruction of <CODE>downup.many</CODE>; we can use a +single procedure that <CODE>stop</CODE>s early if appropriate. + +<PRE> +to downup :word +print :word +if equalp count :word 1 [stop] +downup butlast :word +print :word +end +</PRE> + +<P> +The <CODE>if</CODE> instruction in this final version of +<CODE>downup</CODE> is called a <EM>stop rule.</EM> + +<P> +<CODE>Downup</CODE> illustrates the usual pattern of a recursive procedure. +There are three kinds of instructions within its definition: (1) There +are the ordinary instructions that carry out the work of the +procedure for a particular value of the input, in this case the +<CODE>print</CODE> instructions. (2) There is at least one +<EM>recursive call,</EM> +an instruction that invokes the same procedure with a smaller input. +(3) There is a stop rule, which prevents the recursive invocation when +the input is too small. + +<P> +It's important to understand that the stop rule always comes +<EM>before</EM> the recursive call or calls. One of the common mistakes +made by programmers who are just learning about recursion is to think +this way: "The stop rule <EM>ends</EM> the program, so it belongs at the +<EM>end</EM> of the procedure." The right way to think about it is +that the purpose of the stop rule is to stop the innermost invocation +of the procedure <EM>before</EM> it has a chance to invoke itself +recursively, so the stop rule must come <EM>before</EM> the recursive call. + +<H2>Local Variables</H2> + +<P> +When you're thinking about a recursive procedure, it's especially +important to remember that each invocation of a procedure has its own +local variables. It's possible to get confused about this +because, of course, if a procedure invokes itself as a subprocedure, +each invocation uses the same <EM>names</EM> for local variables. For +example, each invocation of <CODE>downup</CODE> has a local variable (its +input) named <CODE>word</CODE>. But each invocation has a +<EM>separate</EM> input variable. + +<P> +It's hard to talk about different invocations in the abstract. So +let's look back at the version of the program in which each invocation +had a different procedure +name: <CODE>downup1</CODE>, <CODE>downup2</CODE>, and so on. + +<P> +If you type the instruction + +<PRE> +downup5 "hello +</PRE> + +<P> +the procedure <CODE>downup5</CODE> is invoked, with the word +<CODE>hello</CODE> as +its input. <CODE>Downup5</CODE> has a local variable named +<CODE>word</CODE>, which +contains <CODE>hello</CODE> as its value. The first instruction +in <CODE>downup5</CODE> is + +<PRE> +print :word +</PRE> + +<P> +Since <CODE>:word</CODE> is <CODE>hello</CODE>, this instruction prints +<CODE>hello</CODE>. The next instruction is + +<PRE> +downup4 butlast :word +</PRE> + +<P> +This instruction invokes procedure <CODE>downup4</CODE> with the +word <CODE>hell</CODE> +(the <CODE>butlast</CODE> of <CODE>hello</CODE>) as input. +<CODE>Downup4</CODE> has a local +variable that is also named <CODE>word</CODE>. The +value of <EM>that</EM> variable is the word <CODE>hell</CODE>. + +<P> +At this point there are two separate variables, both named +<CODE>word</CODE>. <CODE>Downup5</CODE>'s <CODE>word</CODE> contains +<CODE>hello</CODE>; <CODE>downup4</CODE>'s <CODE>word</CODE> contains +<CODE>hell</CODE>. I won't go through all the details of how +<CODE>downup4</CODE> invokes <CODE>downup3</CODE> and so on. But eventually +<CODE>downup4</CODE> finishes its task, and <CODE>downup5</CODE> continues +with its final instruction, which is + +<PRE> +print :word +</PRE> + +<P> +Even though different values have been assigned to variables named +<CODE>word</CODE> in the interim, <EM>this</EM> variable named +<CODE>word</CODE> (the one that is local to <CODE>downup5</CODE>) still has +its original value, <CODE>hello</CODE>. So that's what's printed. + +<P> +In the recursive version of the program exactly the same thing +happens about local variables. It's a little harder to describe, +because all the procedure invocations are invocations of the same +procedure, <CODE>downup</CODE>. So I can't say things like "the variable +<CODE>word</CODE> that belongs to <CODE>downup4</CODE>"; instead, you have to +think about "the variable named <CODE>word</CODE> that belongs to the +second invocation of <CODE>downup</CODE>." But even though there is only +one <EM>procedure</EM> involved, there are still five procedure +<EM>invocations,</EM> each with its own local variable named <CODE>word</CODE>. + +<H2>More Examples</H2> + +<P> +» Before I go on to show you another example of a recursive procedure, +you might try to write <CODE>down</CODE> and <CODE>up</CODE>, which should work like +this: + +<PRE> +? <U>down "hello</U> +hello +hell +hel +he +h +? <U>up "hello</U> +h +he +hel +hell +hello +</PRE> + +<P> +As a start, notice that there are two <CODE>print</CODE> +instructions in <CODE>downup</CODE> and that one of them does the "down" +half and the other does the "up" half. But you'll find that just +eliminating one of the <CODE>print</CODE>s for <CODE>down</CODE> and the other for +<CODE>up</CODE> doesn't <EM>quite</EM> work. + +<P> +After you've finished <CODE>down</CODE> and <CODE>up</CODE>, come back here for a +discussion of a similar project, which I call <CODE>inout</CODE>: + +<PRE> +? <U>inout "hello</U> +hello + ello + llo + lo + o + lo + llo + ello +hello +</PRE> + +<P> +At first glance <CODE>inout</CODE> looks just like <CODE>downup</CODE>, +except that it uses the <CODE>butfirst</CODE> of its input instead of the +<CODE>butlast</CODE>. <CODE>Inout</CODE> is somewhat more complicated than +<CODE>downup</CODE>, however, because it has to print spaces before some of the words +in order to line up the rightmost letters. <CODE>Downup</CODE> lined up the +leftmost letters, which is easy. + +<P> +Suppose we start, as we did for <CODE>downup</CODE>, with a version that only +works for single-letter words: + +<PRE> +to inout1 :word +print :word +end +</PRE> + +<P> +But we can't quite use <CODE>inout1</CODE> as a subprocedure of +<CODE>inout2</CODE>, as we did in the <CODE>downup</CODE> problem. Instead we need +a different version of <CODE>inout1</CODE>, which types a space before its +input: + +<PRE> +to inout2 :word +print :word +inout2.1 butfirst :word +print :word +end + +to inout2.1 :word +type "| | ; a word containing a space +print :word +end +</PRE> + +<P> +<CODE>Type</CODE> is a command, which requires one input. The +input can be any datum. <CODE>Type</CODE> prints its input, like +<CODE>print</CODE>, but does not move the cursor to a new line afterward. The +cursor remains right after the printed datum, so the next <CODE>print</CODE> +or <CODE>type</CODE> command will continue on the same line. + +<P> +We need another specific case or two before a general pattern will +become apparent. Here is the version for three-letter words: + +<PRE> +to inout3 :word +print :word +inout3.2 butfirst :word +print :word +end + +to inout3.2 :word +type "| | +print :word +inout3.1 butfirst :word +type "| | +print :word +end + +to inout3.1 :word +repeat 2 [type "| |] +print :word +end +</PRE> + +<P> +Convince yourself that each of these procedures types the +right number of spaces before its input word. + +<P> +Here is one final example, the version for four-letter words: + +<PRE> +to inout4 :word +print :word +inout4.3 butfirst :word +print :word +end + +to inout4.3 :word +type "| | +print :word +inout4.2 butfirst :word +type "| | +print :word +end + +to inout4.2 :word +repeat 2 [type "| |] +print :word +inout4.1 butfirst :word +repeat 2 [type "| |] +print :word +end + +to inout4.1 :word +repeat 3 [type "| |] +print :word +end +</PRE> + +<P> +» Try this out and try writing <CODE>inout5</CODE> along the same lines. + +<P> +How can we find a common pattern that will combine the elements of +all these procedures? It will have to look something like this: + +<PRE> +to inout :word +repeat <U>something</U> [type "| |] +print :word +if <U>something</U> [stop] +inout butfirst :word +repeat <U>something</U> [type "| |] +print :word +end +</PRE> + +<P> +This is not a finished procedure because we haven't figured +out how to fill the blanks. First I should remark that the stop rule +is where it is, after the first <CODE>print</CODE>, because that's how far the +innermost procedures (<CODE>inout2.1</CODE>, <CODE>inout3.1</CODE>, and +<CODE>inout4.1</CODE>) get. They type some spaces, print the input word, and +that's all. + +<P> +Another thing to remark is that the first input to the <CODE>repeat</CODE> +commands in this general procedure will sometimes be zero, because the +outermost procedures (<CODE>inout2</CODE>, <CODE>inout3</CODE>, and +<CODE>inout4</CODE>) don't type any spaces at all. Each subprocedure types +one more space than its superprocedure. For example, <CODE>inout4</CODE> +types no spaces. Its subprocedure <CODE>inout4.3</CODE> types one space. +<CODE>inout4.3</CODE>'s subprocedure <CODE>inout4.2</CODE> types two +spaces. Finally, <CODE>inout4.2</CODE>'s subprocedure <CODE>inout4.1</CODE> +types three spaces. + +<P> +In order to vary the number of spaces in this way, the solution is to +use another input that will have this number as its value. We can +call it <CODE>spaces</CODE>. The procedure will then look like this: + +<PRE> +to inout :word :spaces +repeat :spaces [type "| |] +print :word +if equalp count :word 1 [stop] +inout (butfirst :word) (:spaces+1) +repeat :spaces [type "| |] +print :word +end + +? <U>inout "hello 0</U> +hello + ello + llo + lo + o + lo + llo + ello +hello +</PRE> + +<P> +Notice that, when we use <CODE>inout</CODE>, we have to give it a +zero as its second input. We could eliminate this annoyance by +writing a new <CODE>inout</CODE> that invokes this one as a subprocedure: + +<PRE> +to inout :word +inout.sub :word 0 +end + +to inout.sub :word :spaces +repeat :spaces [type "| |] +print :word +if equalp count :word 1 [stop] +inout.sub (butfirst :word) (:spaces+1) +repeat :spaces [type "| |] +print :word +end +</PRE> + +<P> +(The easiest way to make this change is to edit <CODE>inout</CODE> +with the Logo editor and change its title line and its recursive call +so that its name is <CODE>inout.sub</CODE>. Then, still in the editor, +type in the new superprocedure <CODE>inout</CODE>. When you leave the +editor, both procedures will get their new definitions.) + +<P> +This program structure, with a short superprocedure and a recursive +subprocedure, is very common. The superprocedure's only job is to provide +the initial values for some of the subprocedure's inputs, so it's sometimes +called an <EM>initialization procedure.</EM> In this program +<CODE>inout</CODE> is an initialization procedure for <CODE>inout.sub</CODE>. + +<P> +By the way, the parentheses in the recursive call aren't really +needed; I just used them to make it more obvious which input is which. + +<H2>Other Stop Rules</H2> + +<P> +The examples I've shown so far use this stop rule: + +<PRE> +if equalp count :word 1 [stop] +</PRE> + +<P> +Perhaps you wrote your <CODE>down</CODE> procedure the same way: + +<PRE> +to down :word +print :word +if equalp count :word 1 [stop] +down butlast :word +end +</PRE> + +<P> +Here is another way to write <CODE>down</CODE>, which has the same +effect. But this is a more commonly used style: + +<PRE> +to down :word +if emptyp :word [stop] +print :word +down butlast :word +end +</PRE> + +<P> +This version of <CODE>down</CODE> has the stop rule as its first +instruction. After that comes the instructions that carry out the +specific work of the procedure, in this case the <CODE>print</CODE> +instruction. The recursive call comes as the last instruction. + +<P> +A procedure in which the recursive call is the last instruction is +called <EM>tail recursive.</EM> We'll have more to say later about the +meaning of tail recursion. (Actually, to be precise, I should have +said that a <EM>command</EM> in which the recursive call is the last +instruction is tail recursive. What constitutes a tail recursive +operation is a little tricker, and so far we haven't talked about +recursive operations at all.) + +<P> +Here's another example: + +<PRE> +to countdown :number +if equalp :number 0 [print "Blastoff! stop] +print :number +countdown :number-1 +end + +? <U>countdown 10</U> +10 +9 +8 +7 +6 +5 +4 +3 +2 +1 +Blastoff! +</PRE> + +<P> +In this case, instead of a word that gets smaller by +<CODE>butfirst</CODE>ing or <CODE>butlast</CODE>ing it, the input is a +number from which 1 is subtracted for each recursive invocation. This +example also shows how some special action (the <CODE>print +"Blastoff!</CODE> instruction) can be taken in the innermost invocation of +the procedure. + +<P> +» Here are some ideas for recursive programs you can write. In each +case I'll show an example or two of what the program should do. +Start with <CODE>one.per.line</CODE>, a command with one input. If the input +is a word, the procedure should print each letter of the word on a +separate line. If the input is a list, the procedure should print +each member of the list on a separate line: + +<PRE> +? <U>one.per.line "hello</U> +h +e +l +l +o +? <U>one.per.line [the rain in spain]</U> +the +rain +in +spain +</PRE> + +<P> +(You already know how to do this without recursion, using +<CODE>foreach</CODE> instead. Many, although not all, recursive problems +can also be solved using higher order functions. You might enjoy this +non-obvious example: + +<PRE> +to down :word +ignore cascade (count :word) [print ? butlast ?] :word +end +</PRE> + +<P> +While you're learning about recursion, though, don't use higher +order functions. Once you're comfortable with both techniques you can +choose which to use in a particular situation.) + +<P> +» As an example in which an initialization procedure will be helpful, +try <CODE>triangle</CODE>, a command that takes a word as its single input. +It prints the word repeatedly on the same line, as many times as its +length. Then it prints a second line with one fewer repetition, and +so on until it prints the word just once: + +<PRE> +? <U>triangle "frog</U> +frog frog frog frog +frog frog frog +frog frog +frog +</PRE> + +<P> +» A more ambitious project is <CODE>diamond</CODE>, which takes as its input a +word with an odd number of letters. It displays the word in a diamond +pattern, like this: + +<PRE> +? <U>diamond "program</U> + g + ogr + rogra +program + rogra + ogr + g +</PRE> + +<P> +(Hint: Write two procedures <CODE>diamond.top</CODE> and +<CODE>diamond.bottom</CODE> for the growing and shrinking halves of the display. +As in <CODE>inout</CODE>, you'll need an input to count the number of spaces +by which to indent each line.) Can you write <CODE>diamond</CODE> so that it +does something sensible for an input word with an even number of +letters? + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch6/v1ch6.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch8/v1ch8.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> diff --git a/js/games/nluqo.github.io/~bh/v1ch7/v1ch7.html b/js/games/nluqo.github.io/~bh/v1ch7/v1ch7.html new file mode 100644 index 0000000..e8a9147 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch7/v1ch7.html @@ -0,0 +1,931 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 7: Introduction to Recursion</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Introduction to Recursion</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/v1ch07.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="../v1ch6/v1ch6.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch8/v1ch8.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> +My goal in this chapter is to write a procedure named <CODE>downup</CODE> +that behaves like this: + +<PRE> +? <U>downup "hello</U> +hello +hell +hel +he +h +he +hel +hell +hello +? <U>downup "goodbye</U> +goodbye +goodby +goodb +good +goo +go +g +go +goo +good +goodb +goodby +goodbye +</PRE> + +<P> +The programming techniques we've used so far in this book +don't allow an elegant solution to this problem. We'll use a +new technique called <EM>recursion:</EM> writing a procedure that uses +<EM>itself</EM> as a subprocedure. + +<P> +We're going to solve this problem using recursion. It turns out that the +idea of recursion is both very powerful--we can solve a <EM>lot</EM> of +problems using it--and rather tricky to understand. That's why I'm going +to explain recursion several different ways in the coming chapters. Even +after you understand one of them, you'll probably find that thinking about +recursion from another point of view enriches your ability to use this idea. +The explanation in this chapter is based on the <EM>combining method.</EM> + +<H2>Starting Small</H2> + +<P> +My own favorite way to understand recursion is based on the general +problem-solving strategy of solving a complicated problem by starting +with a simpler version. To solve the <CODE>downup</CODE> problem, I'll start +by solving this simpler version: write a <CODE>downup</CODE> procedure that +works only for a single-character input word. (You can't get much +simpler than that!) Here's my solution: + +<PRE> +to downup1 :word +print :word +end + +? <U>downup1 "j</U> +j +</PRE> + +<P> +See how well it works? + +<H2>Building Up</H2> + +<P> +Of course, <CODE>downup1</CODE> won't work at all if you give it an input +longer than one character. You may not think this was such a big +step. But bear with me. Next I'll write a procedure that acts like +<CODE>downup</CODE> when you give it a two-letter input word: + +<PRE> +to downup2 :word +print :word +print butlast :word +print :word +end + +? <U>downup2 "it</U> +it +i +it +</PRE> + +<P> +We could keep this up for longer and longer input words, but each procedure +gets more and more complicated. Here's <CODE>downup3</CODE>: + +<PRE> +to downup3 :word +print :word +print butlast :word +print butlast butlast :word +print butlast :word +print :word +end +</PRE> + +<P> +» How many <CODE>print</CODE> instructions would I need to write <CODE>downup4</CODE> +this way? How many would I need for <CODE>downup20</CODE>? + +<P> +Luckily there's an easier way. Look at the result of invoking <CODE>downup3</CODE>: + +<PRE> +? <U>downup3 "dot</U> +dot +<TABLE border="5" rules="none" frame="box" noshade><TR><TD>do +<TR><TD>d +<TR><TD>do</TABLE>dot +</PRE> + +<P> +The trick is to recognize that the boxed lines are what we'd get by invoking +<CODE>downup2</CODE> with the word <CODE>do</CODE> as input. So we can find +the instructions in <CODE>downup3</CODE> that print those three lines and +replace them with one instruction that calls <CODE>downup2</CODE>: + +<PRE> +to downup3 :word +print :word +<U>downup2 butlast :word</U> +print :word +end +</PRE> + +<P> +You might have to think a moment to work out where the +<CODE>butlast</CODE> came from, but consider +that we're given the word <CODE>dot</CODE> and we +want the word <CODE>do</CODE>. + +<P> +Once we've had this idea, it's easy to extend it to longer words: + +<PRE> +to downup4 :word +print :word +downup3 butlast :word +print :word +end + +to downup5 :word +print :word +downup4 butlast :word +print :word +end +</PRE> + +<P> +» Can you rewrite <CODE>downup2</CODE> so that it looks like these others? + +<P> +» Before going on, make sure you really understand these procedures by +answering these questions: What happens if you use one of these numbered +versions of <CODE>downup</CODE> with an input that is too long? What if the input +is too short? + +<H2>Generalizing the Pattern</H2> + +<P> +We're now in good shape as long as we want to <CODE>downup</CODE> short +words. We can pick the right version of <CODE>downup</CODE> for the length +of the word we have in mind: + +<PRE> +? <U>downup5 "hello</U> +hello +hell +hel +he +h +he +hel +hell +hello +? <U>downup7 "goodbye</U> +goodbye +goodby +goodb +good +goo +go +g +go +goo +good +goodb +goodby +goodbye +</PRE> + +<P> +Having to count the number of characters in the word is a +little unaesthetic, but we could even have the computer do that for us: + +<PRE> +to downup :word +if equalp count :word 1 [downup1 :word] +if equalp count :word 2 [downup2 :word] +if equalp count :word 3 [downup3 :word] +if equalp count :word 4 [downup4 :word] +if equalp count :word 5 [downup5 :word] +if equalp count :word 6 [downup6 :word] +if equalp count :word 7 [downup7 :word] +end +</PRE> + +<P> +There's only one problem. What if we want to be able to say + +<PRE> +downup "antidisestablishmentarianism +</PRE> + +<P> +You wouldn't want to have to type in separate versions of +<CODE>downup</CODE> all the way up to <CODE>downup28</CODE>! + +<P> +What I hope you're tempted to do is to take advantage of the +similarity of all the numbered <CODE>downup</CODE> procedures by combining +them into a single procedure that looks like this: + +<PRE> +to downup :word +print :word +downup butlast :word +print :word +end +</PRE> + +<P> +(Remember that Logo's <CODE>to</CODE> command won't let you +redefine <CODE>downup</CODE> if you've already typed in my earlier version +with all the <CODE>if</CODE> instruction lines. Before you can type in the +new version, you have to <CODE>erase</CODE> the old one.) + +<P> +Compare this version of <CODE>downup</CODE> with one of the numbered +procedures like <CODE>downup5</CODE>. Do you see that this combined version +should work just as well, if all the numbered +<CODE>downup</CODE> procedures are identical except for the numbers in the +procedure names? +Convince yourself that that makes sense. + +<P> +» Okay, now try it. + +<H2>What Went Wrong?</H2> + +<P> +You probably saw something like this: + +<PRE> +? <U>downup "hello</U> +hello +hell +hel +he +h + +butlast doesn't like as input in downup +</PRE> + +<P> +There's nothing wrong with the reasoning I used in the last section. +If all the numbered <CODE>downup</CODE> procedures are identical except for +the numbers, it should work to replace them all with a single +procedure following the same pattern. + +<P> +The trouble is that the numbered <CODE>downup</CODE> procedures +<EM>aren't</EM> quite +all identical. The exception is <CODE>downup1</CODE>. If it +were like the others, it would look like this: + +<PRE> +to downup1 :word +print :word +<U>downup0 butlast :word</U> +<U>print :word</U> +end +</PRE> + +<P> +Review the way the numbered <CODE>downup</CODE>s work to make sure +you understand why <CODE>downup1</CODE> is different. Here's what happens +when you invoke one of the numbered versions: + + +<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch7/downup.gif" ALT="<P>figure: downup"></CENTER> + +<P> +In this chart, instructions within a particular procedure +are indented the same amount. For example, the lines +<CODE>print "hello</CODE> and +<CODE>downup4 "hell</CODE> are part of <CODE>downup5</CODE>, as is +the line <CODE>print "hello</CODE> at the very end of the chart. The lines +in between are indented more because they're part of <CODE>downup4</CODE> +and its subprocedures. + +<P> +(By the way, the lines in the chart don't show actual instructions in +the procedure definitions. Otherwise all the <CODE>print</CODE> lines would +say <CODE>print :word</CODE> instead of showing actual words. In the chart +I've already evaluated the inputs to the commands.) + +<P> +The point of the chart is that <CODE>downup1</CODE> has to be special because +it marks the end of the "down" part of the problem and the +beginning of the "up" part. <CODE>downup1</CODE> doesn't invoke a +lower-numbered <CODE>downup</CODE> subprocedure because there's no smaller +piece of the word to print. + +<P> +» Okay, Logo knows when to stop the "down" part of the program +because <CODE>downup1</CODE> is different from the other procedures. +Question: How does Logo know when to stop the "up" part of the +program? Why doesn't <CODE>downup5</CODE>, in this example, have to be +written differently from the others? + +<H2>The Stop Rule</H2> + +<P> +Our attempt to write a completely general <CODE>downup</CODE> procedure has +run into trouble because we have to distinguish two cases: the special +case in which the input word contains only one character and the +general case for longer input words. We can use <CODE>ifelse</CODE> to +distinguish the two cases: + +<PRE> +to downup :word +ifelse equalp count :word 1 [downup.one :word] [downup.many :word] +end + +to downup.one :word +print :word +end + +to downup.many :word +print :word +downup butlast :word +print :word +end +</PRE> + +<P> +You'll find that this version of the <CODE>downup</CODE> program actually +works correctly. +Subprocedure <CODE>downup.one</CODE> is exactly like the +old <CODE>downup1</CODE>, while <CODE>downup.many</CODE> is like the version +of <CODE>downup</CODE> that didn't work. + +<P> +It's possible to use the same general idea, however--distinguishing +the special case of a one-letter word--without having +to set up this three-procedure structure. Instead we can take +advantage of the fact that <CODE>downup.one</CODE>'s single instruction is +the same as the first instruction of <CODE>downup.many</CODE>; we can use a +single procedure that <CODE>stop</CODE>s early if appropriate. + +<PRE> +to downup :word +print :word +if equalp count :word 1 [stop] +downup butlast :word +print :word +end +</PRE> + +<P> +The <CODE>if</CODE> instruction in this final version of +<CODE>downup</CODE> is called a <EM>stop rule.</EM> + +<P> +<CODE>Downup</CODE> illustrates the usual pattern of a recursive procedure. +There are three kinds of instructions within its definition: (1) There +are the ordinary instructions that carry out the work of the +procedure for a particular value of the input, in this case the +<CODE>print</CODE> instructions. (2) There is at least one +<EM>recursive call,</EM> +an instruction that invokes the same procedure with a smaller input. +(3) There is a stop rule, which prevents the recursive invocation when +the input is too small. + +<P> +It's important to understand that the stop rule always comes +<EM>before</EM> the recursive call or calls. One of the common mistakes +made by programmers who are just learning about recursion is to think +this way: "The stop rule <EM>ends</EM> the program, so it belongs at the +<EM>end</EM> of the procedure." The right way to think about it is +that the purpose of the stop rule is to stop the innermost invocation +of the procedure <EM>before</EM> it has a chance to invoke itself +recursively, so the stop rule must come <EM>before</EM> the recursive call. + +<H2>Local Variables</H2> + +<P> +When you're thinking about a recursive procedure, it's especially +important to remember that each invocation of a procedure has its own +local variables. It's possible to get confused about this +because, of course, if a procedure invokes itself as a subprocedure, +each invocation uses the same <EM>names</EM> for local variables. For +example, each invocation of <CODE>downup</CODE> has a local variable (its +input) named <CODE>word</CODE>. But each invocation has a +<EM>separate</EM> input variable. + +<P> +It's hard to talk about different invocations in the abstract. So +let's look back at the version of the program in which each invocation +had a different procedure +name: <CODE>downup1</CODE>, <CODE>downup2</CODE>, and so on. + +<P> +If you type the instruction + +<PRE> +downup5 "hello +</PRE> + +<P> +the procedure <CODE>downup5</CODE> is invoked, with the word +<CODE>hello</CODE> as +its input. <CODE>Downup5</CODE> has a local variable named +<CODE>word</CODE>, which +contains <CODE>hello</CODE> as its value. The first instruction +in <CODE>downup5</CODE> is + +<PRE> +print :word +</PRE> + +<P> +Since <CODE>:word</CODE> is <CODE>hello</CODE>, this instruction prints +<CODE>hello</CODE>. The next instruction is + +<PRE> +downup4 butlast :word +</PRE> + +<P> +This instruction invokes procedure <CODE>downup4</CODE> with the +word <CODE>hell</CODE> +(the <CODE>butlast</CODE> of <CODE>hello</CODE>) as input. +<CODE>Downup4</CODE> has a local +variable that is also named <CODE>word</CODE>. The +value of <EM>that</EM> variable is the word <CODE>hell</CODE>. + +<P> +At this point there are two separate variables, both named +<CODE>word</CODE>. <CODE>Downup5</CODE>'s <CODE>word</CODE> contains +<CODE>hello</CODE>; <CODE>downup4</CODE>'s <CODE>word</CODE> contains +<CODE>hell</CODE>. I won't go through all the details of how +<CODE>downup4</CODE> invokes <CODE>downup3</CODE> and so on. But eventually +<CODE>downup4</CODE> finishes its task, and <CODE>downup5</CODE> continues +with its final instruction, which is + +<PRE> +print :word +</PRE> + +<P> +Even though different values have been assigned to variables named +<CODE>word</CODE> in the interim, <EM>this</EM> variable named +<CODE>word</CODE> (the one that is local to <CODE>downup5</CODE>) still has +its original value, <CODE>hello</CODE>. So that's what's printed. + +<P> +In the recursive version of the program exactly the same thing +happens about local variables. It's a little harder to describe, +because all the procedure invocations are invocations of the same +procedure, <CODE>downup</CODE>. So I can't say things like "the variable +<CODE>word</CODE> that belongs to <CODE>downup4</CODE>"; instead, you have to +think about "the variable named <CODE>word</CODE> that belongs to the +second invocation of <CODE>downup</CODE>." But even though there is only +one <EM>procedure</EM> involved, there are still five procedure +<EM>invocations,</EM> each with its own local variable named <CODE>word</CODE>. + +<H2>More Examples</H2> + +<P> +» Before I go on to show you another example of a recursive procedure, +you might try to write <CODE>down</CODE> and <CODE>up</CODE>, which should work like +this: + +<PRE> +? <U>down "hello</U> +hello +hell +hel +he +h +? <U>up "hello</U> +h +he +hel +hell +hello +</PRE> + +<P> +As a start, notice that there are two <CODE>print</CODE> +instructions in <CODE>downup</CODE> and that one of them does the "down" +half and the other does the "up" half. But you'll find that just +eliminating one of the <CODE>print</CODE>s for <CODE>down</CODE> and the other for +<CODE>up</CODE> doesn't <EM>quite</EM> work. + +<P> +After you've finished <CODE>down</CODE> and <CODE>up</CODE>, come back here for a +discussion of a similar project, which I call <CODE>inout</CODE>: + +<PRE> +? <U>inout "hello</U> +hello + ello + llo + lo + o + lo + llo + ello +hello +</PRE> + +<P> +At first glance <CODE>inout</CODE> looks just like <CODE>downup</CODE>, +except that it uses the <CODE>butfirst</CODE> of its input instead of the +<CODE>butlast</CODE>. <CODE>Inout</CODE> is somewhat more complicated than +<CODE>downup</CODE>, however, because it has to print spaces before some of the words +in order to line up the rightmost letters. <CODE>Downup</CODE> lined up the +leftmost letters, which is easy. + +<P> +Suppose we start, as we did for <CODE>downup</CODE>, with a version that only +works for single-letter words: + +<PRE> +to inout1 :word +print :word +end +</PRE> + +<P> +But we can't quite use <CODE>inout1</CODE> as a subprocedure of +<CODE>inout2</CODE>, as we did in the <CODE>downup</CODE> problem. Instead we need +a different version of <CODE>inout1</CODE>, which types a space before its +input: + +<PRE> +to inout2 :word +print :word +inout2.1 butfirst :word +print :word +end + +to inout2.1 :word +type "| | ; a word containing a space +print :word +end +</PRE> + +<P> +<CODE>Type</CODE> is a command, which requires one input. The +input can be any datum. <CODE>Type</CODE> prints its input, like +<CODE>print</CODE>, but does not move the cursor to a new line afterward. The +cursor remains right after the printed datum, so the next <CODE>print</CODE> +or <CODE>type</CODE> command will continue on the same line. + +<P> +We need another specific case or two before a general pattern will +become apparent. Here is the version for three-letter words: + +<PRE> +to inout3 :word +print :word +inout3.2 butfirst :word +print :word +end + +to inout3.2 :word +type "| | +print :word +inout3.1 butfirst :word +type "| | +print :word +end + +to inout3.1 :word +repeat 2 [type "| |] +print :word +end +</PRE> + +<P> +Convince yourself that each of these procedures types the +right number of spaces before its input word. + +<P> +Here is one final example, the version for four-letter words: + +<PRE> +to inout4 :word +print :word +inout4.3 butfirst :word +print :word +end + +to inout4.3 :word +type "| | +print :word +inout4.2 butfirst :word +type "| | +print :word +end + +to inout4.2 :word +repeat 2 [type "| |] +print :word +inout4.1 butfirst :word +repeat 2 [type "| |] +print :word +end + +to inout4.1 :word +repeat 3 [type "| |] +print :word +end +</PRE> + +<P> +» Try this out and try writing <CODE>inout5</CODE> along the same lines. + +<P> +How can we find a common pattern that will combine the elements of +all these procedures? It will have to look something like this: + +<PRE> +to inout :word +repeat <U>something</U> [type "| |] +print :word +if <U>something</U> [stop] +inout butfirst :word +repeat <U>something</U> [type "| |] +print :word +end +</PRE> + +<P> +This is not a finished procedure because we haven't figured +out how to fill the blanks. First I should remark that the stop rule +is where it is, after the first <CODE>print</CODE>, because that's how far the +innermost procedures (<CODE>inout2.1</CODE>, <CODE>inout3.1</CODE>, and +<CODE>inout4.1</CODE>) get. They type some spaces, print the input word, and +that's all. + +<P> +Another thing to remark is that the first input to the <CODE>repeat</CODE> +commands in this general procedure will sometimes be zero, because the +outermost procedures (<CODE>inout2</CODE>, <CODE>inout3</CODE>, and +<CODE>inout4</CODE>) don't type any spaces at all. Each subprocedure types +one more space than its superprocedure. For example, <CODE>inout4</CODE> +types no spaces. Its subprocedure <CODE>inout4.3</CODE> types one space. +<CODE>inout4.3</CODE>'s subprocedure <CODE>inout4.2</CODE> types two +spaces. Finally, <CODE>inout4.2</CODE>'s subprocedure <CODE>inout4.1</CODE> +types three spaces. + +<P> +In order to vary the number of spaces in this way, the solution is to +use another input that will have this number as its value. We can +call it <CODE>spaces</CODE>. The procedure will then look like this: + +<PRE> +to inout :word :spaces +repeat :spaces [type "| |] +print :word +if equalp count :word 1 [stop] +inout (butfirst :word) (:spaces+1) +repeat :spaces [type "| |] +print :word +end + +? <U>inout "hello 0</U> +hello + ello + llo + lo + o + lo + llo + ello +hello +</PRE> + +<P> +Notice that, when we use <CODE>inout</CODE>, we have to give it a +zero as its second input. We could eliminate this annoyance by +writing a new <CODE>inout</CODE> that invokes this one as a subprocedure: + +<PRE> +to inout :word +inout.sub :word 0 +end + +to inout.sub :word :spaces +repeat :spaces [type "| |] +print :word +if equalp count :word 1 [stop] +inout.sub (butfirst :word) (:spaces+1) +repeat :spaces [type "| |] +print :word +end +</PRE> + +<P> +(The easiest way to make this change is to edit <CODE>inout</CODE> +with the Logo editor and change its title line and its recursive call +so that its name is <CODE>inout.sub</CODE>. Then, still in the editor, +type in the new superprocedure <CODE>inout</CODE>. When you leave the +editor, both procedures will get their new definitions.) + +<P> +This program structure, with a short superprocedure and a recursive +subprocedure, is very common. The superprocedure's only job is to provide +the initial values for some of the subprocedure's inputs, so it's sometimes +called an <EM>initialization procedure.</EM> In this program +<CODE>inout</CODE> is an initialization procedure for <CODE>inout.sub</CODE>. + +<P> +By the way, the parentheses in the recursive call aren't really +needed; I just used them to make it more obvious which input is which. + +<H2>Other Stop Rules</H2> + +<P> +The examples I've shown so far use this stop rule: + +<PRE> +if equalp count :word 1 [stop] +</PRE> + +<P> +Perhaps you wrote your <CODE>down</CODE> procedure the same way: + +<PRE> +to down :word +print :word +if equalp count :word 1 [stop] +down butlast :word +end +</PRE> + +<P> +Here is another way to write <CODE>down</CODE>, which has the same +effect. But this is a more commonly used style: + +<PRE> +to down :word +if emptyp :word [stop] +print :word +down butlast :word +end +</PRE> + +<P> +This version of <CODE>down</CODE> has the stop rule as its first +instruction. After that comes the instructions that carry out the +specific work of the procedure, in this case the <CODE>print</CODE> +instruction. The recursive call comes as the last instruction. + +<P> +A procedure in which the recursive call is the last instruction is +called <EM>tail recursive.</EM> We'll have more to say later about the +meaning of tail recursion. (Actually, to be precise, I should have +said that a <EM>command</EM> in which the recursive call is the last +instruction is tail recursive. What constitutes a tail recursive +operation is a little tricker, and so far we haven't talked about +recursive operations at all.) + +<P> +Here's another example: + +<PRE> +to countdown :number +if equalp :number 0 [print "Blastoff! stop] +print :number +countdown :number-1 +end + +? <U>countdown 10</U> +10 +9 +8 +7 +6 +5 +4 +3 +2 +1 +Blastoff! +</PRE> + +<P> +In this case, instead of a word that gets smaller by +<CODE>butfirst</CODE>ing or <CODE>butlast</CODE>ing it, the input is a +number from which 1 is subtracted for each recursive invocation. This +example also shows how some special action (the <CODE>print +"Blastoff!</CODE> instruction) can be taken in the innermost invocation of +the procedure. + +<P> +» Here are some ideas for recursive programs you can write. In each +case I'll show an example or two of what the program should do. +Start with <CODE>one.per.line</CODE>, a command with one input. If the input +is a word, the procedure should print each letter of the word on a +separate line. If the input is a list, the procedure should print +each member of the list on a separate line: + +<PRE> +? <U>one.per.line "hello</U> +h +e +l +l +o +? <U>one.per.line [the rain in spain]</U> +the +rain +in +spain +</PRE> + +<P> +(You already know how to do this without recursion, using +<CODE>foreach</CODE> instead. Many, although not all, recursive problems +can also be solved using higher order functions. You might enjoy this +non-obvious example: + +<PRE> +to down :word +ignore cascade (count :word) [print ? butlast ?] :word +end +</PRE> + +<P> +While you're learning about recursion, though, don't use higher +order functions. Once you're comfortable with both techniques you can +choose which to use in a particular situation.) + +<P> +» As an example in which an initialization procedure will be helpful, +try <CODE>triangle</CODE>, a command that takes a word as its single input. +It prints the word repeatedly on the same line, as many times as its +length. Then it prints a second line with one fewer repetition, and +so on until it prints the word just once: + +<PRE> +? <U>triangle "frog</U> +frog frog frog frog +frog frog frog +frog frog +frog +</PRE> + +<P> +» A more ambitious project is <CODE>diamond</CODE>, which takes as its input a +word with an odd number of letters. It displays the word in a diamond +pattern, like this: + +<PRE> +? <U>diamond "program</U> + g + ogr + rogra +program + rogra + ogr + g +</PRE> + +<P> +(Hint: Write two procedures <CODE>diamond.top</CODE> and +<CODE>diamond.bottom</CODE> for the growing and shrinking halves of the display. +As in <CODE>inout</CODE>, you'll need an input to count the number of spaces +by which to indent each line.) Can you write <CODE>diamond</CODE> so that it +does something sensible for an input word with an even number of +letters? + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch6/v1ch6.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch8/v1ch8.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |