Recursion Revisited

In this lab you will sort your contact list alphabetically by name.

On this page you will review the technique of recursion.

Recursive Graphics

  1. In Unit 2 you wrote a recursive program to draw this picture:
    Sierpinski gasket
    Open your project U2L4-FractalArt and save it as U3L2-Recursion. Then look inside the nested triangle block. Your solution may not be exactly this, but it's probably close:
    nested triangle, size: (size) : if (size > 2) [repeat 3 [set pen color to (color); move (size) steps; nested triangle, size: (size / 2) color: (color + 10); turn 120 degrees]]
    2. Get to know this code well:


    A top-level script is one that's in the scripting area, not inside the definition of a block.

    An invocation is a use of a block. For example, (7+8)+1 makes two invocations of +. The verb form is invoke.

    Talk with Your Partner
  2. When you invoke nested triangle from a top-level script, how many times does that invocation (not counting invocations within invocations) run the purple block that invokes nested triangle?
    3. Talk with Your Partner
  3. Which instruction inside the top-level invocation of nested triangle draws the three lines shown in black in the picture below?
    gasket with smaller copies in color
    4. Talk with Your Partner
  4. If the sprite starts out pointing to the right, which smaller fractal (red, green, or blue) is drawn first?
    5. Talk with Your Partner
  5. What is the purpose of the if block in this code? (If you're not sure, you might try editing nested triangle to remove it, and see what happens.)

A recursive problem (the thing you're trying to do, not the code to do it) is one in which the desired result includes a smaller version of itself, such as the green (or red or blue) fractal inside the bigger fractal. A recursive procedure (the actual code) is one that calls itself inside its definition. Do you see why a recursive procedure is likely to be a good solution to a recursive problem?

If a recursive procedure calls itself, and that call also calls itself, and that call also calls itself... the result will be an infinite loop, which means that the program will keep running forever (or until it runs out of memory). To avoid that bug, every recursive procedure must have a base case, a simple input for which the procedure can do its job without calling itself. (The base case of nested triangle happens when size ≤ 2; in that case the procedure doesn't have to do anything.)

Save Your Work

Recursive Reporters

The general pattern for a recursive command is

if (base case?) then [do something simple] else [[do something] [recursive call] [do something]]

Compare this with the nested triangle block above. (In that one, the base case is particularly simple: it does nothing at all.) Most recursive commands follow this pattern, except that in certain cases there's more than one recursive call.

It's therefore tempting to try to write a recursive reporter this way:

if (base case?) then [report something simple] else [[report something] [report recursive call] [report something]]

But in fact you can't stack report blocks; once your block reports a value, it's finished. (This is why there's no connection tab at the bottom of the report block.) Instead, you have to use a combiner function to put the pieces together into a single thing to report:

if (base case?) then [report something simple] else [report (combiner (stuff) (recursive call) (stuff)]

The combiner can be any function with the correct range (the kind of value it can return). So if your custom reporter is supposed to return a sentence, the combiner might be join or join words; if it's supposed to return a number, you might use + or ×.

  1. Write a reporter whose input is a list of numbers, reporting the sum of the numbers. Follow this template (without the comments): if (empty slot for test) [report (empty slot for value)] else [report (empty slot for value)]
    If you'd like to write the sum of block with no additional help, do it now. Otherwise, fill in the three blanks in the definition this way:
    1. What should the base case test be? What's the smallest possible list of numbers? Fill in the hexagonal input slot in the if block.
    2. What should your procedure report in that case? Super big hint if you can't get it to work.
      The block is supposed to report a number.
    3. What should your procedure report in the recursive case? You have to find a smaller, similar subproblem just as you did for the triangle fractal. Generally, when writing recursive blocks with lists as input, the most common idea is to split the list into its first item (item () of 'list input slot') and all the other items (all but first of 'list input slot').
      item () of 'list input slot' and all but first of 'list input slot' are the main selectors for lists.
      1. What are you going to do with all but first of the list? You really don't need this hint.
        What makes this a recursive procedure?
      2. How are you going to combine the first item with the result of part (i) to get the overall result?
Combining the items of a list is such a common thing to do that there's a higher-order function for it.
    Import Tools
  1. Make friends with the combine with ( ) items of ( ) block. Try these examples:
    Unlike map and keep, combine requires a function with two empty input slots.
    combine with (+) items of (list 7 8 1)
    combine with (*) items of (list 7 8 1)
    combine with (min) items of (list 7 8 1)
    2. Unlike its friends map and keep, combine is mostly used with one of only these six functions in its first input slot:
    + ×
    and or
    join join words
    Among blocks you might write yourself, there are only two likely candidates:
    max min
    Why so few?
    The function has to be associative, meaning that it doesn't matter what order you group the items in; (7 + 8) + 1 is the same as 7 + (8 + 1) (work it out yourself), but (7 − 8) − 1 is different from 7 − (8 − 1). So combine with (-) items of (list 7 8 1) would be ambiguous.
  2. Rewrite sum of using combine.
    3. So why'd you make us do it the hard way?
    Well, for one thing, some people find recursion more natural than higher-order functions. But also, the kinds of list reporter patterns that happen often enough in programs so that people have abstracted them into higher-order functions tend to be the ones that are easiest to write recursively. On the next page you'll write a recursive operation for which there is no higher-order function, but we wanted you to start with easier examples while getting to know how to write recursive reporters.
  3. Build this block:
    initials (words): report (map (letter 1 of ( )) over (words))
    What does it do?
  4. Now rewrite it using recursion instead of map.
    Selectors are all you needed for problem 6 because the reported result wasn't a list. If you want to write a recursive block that reports a list, you also need the constructor () in front of 'list input slot', which makes a new list with one new item in front of an existing list.
    Remember the steps: What's the base case? What should you report in that case? What should you do with the first list item? What will you do with the rest of the input list? And what combiner do you need to put those together?
    5. Save your work
  1. An acronym is a "word" made up of the first letters of every capitalized word in a phrase. For example, the acronym for United States of America is USA, and SUNY is an acronym for State University of New York. Create a reporter block that takes a phrase as input and reports an acronym made of the first letters of only from the capitalized words. It should work like this:
    Beauty and Joy of Computing: BJC New York City: NYC
    The steps below suggest one way:
      Import Tools
    1. The input phrase is a string of characters. Break it up into a list of words.
      2. There are many ways to turn a string like "Beauty and Joy of Computing" into a list of words. One way is to use this green block: sentence to list (pronounced "sentence to list"). It lets you break a string at every space and convert the string to a list of words. It's in the Tools library.
    2. You have choices about the next step:
        The unicode of block will be helpful here.
      • You could use map to generate a new list containing only the first letters of the words in your input list, and then keep only those that are capital letters.
      • Or you could keep only the words that begin with capitals and then use map to create a list containing only the first letters of those words.
    3. Save Your WorkLast, you need to convert that list back into a string.