Lab 6: Understanding Recursion

After completing their latest mission on defeating the evil Exemplar Bot, the Guardians of the Galaxy just received a new distress call from… Ryan?? Their mission: to venture and understand recursion!

But first, Groot has something to say:

I am Groot!
am Groot!
Groot!

Wow! Language, Groot. Don't curse, recurse.

In lecture, we have started to write recursive functions, where a function body calls the same function, just on a smaller part of the data. This lab gives you practice with understanding how this works and writing recursive functions of your own.

In the first part of lab, you'll draw function diagrams on paper and work with the blocks-based tool that Kathi showed quickly at the end of lecture. You can refer to this sample of both diagrams and blocks to understand what's expected and how the tool and paper diagrams align. Additionally, this Snap guide explains the Snap terminology (local context, bindings, etc).

Using the Function-Tracing Tool

Download this lab6-starter.xml setup file to your computer. You can do this by visiting the page, clicking "File" -> "Save Page As" (or pressing Ctrl+S on Windows or Cmd+S on Mac) and giving the file the title "lab6-starter.xml".

Access the tracing tool via this link. (The tool is actually a programming tool called SNAP, but we've adapted SNAP for tracing programs). When it comes up, you'll see lots of different kinds of blocks and areas. Near the top-left of the window is a white document icon. Click that, and you'll see a menu of options including "Import". Import the setup file (which you saved to the lab computer). You can also drag the setup file onto the blocks area in the middle.

Once you've done that, you should see the following:

Note that we are only using Snap for visualization! We are not running programs or doing anything else in Snap other than drawing blocks.

The rightmost segment (with the white rectangle) might be much wider. Drag on the two vertical bars to the left of the white triangle to narrow that column. You won't need it.

The first set of lab exercises will ask you to replace the pink "FILL IN" boxes with proper contents. These will correspond to parts of the diagram that you draw on paper.

When you are ready to replace a pink box, click on it and drag it out to the open space in the bottom-left area of the window. That will leave behind a text box where you can enter answers.

Part 1: Creating Call-Record Chains

Exercise 1: Binning Numbers by their Signs

In data analysis, we often take a column of data and convert it into a small number of fixed "bins": this lets us cluster data for analysis. For example, we refer to December, January, and February as "winter", while March, April, and May are referred to as "spring". The following function bins numbers based on their signs (positive, negative, and zero):

fun signs(numlist :: List<Number>) -> List<String>:
  cases (List) numlist:
    | empty => empty
    | link(fst, rst) =>
      sign = 
        if fst > 0: "pos"
        else if fst == 0: "zero"
        else: "neg"
        end
      # eval point A
      link(sign, signs(rst))
  end
where:
  signs([list: 3, -1, 6, 0]) is [list: "pos", "neg", "pos", "zero"]
end

Task: On paper, draw a nested-box diagram (just like in the presentation) showing the unfinished function calls that exist at the point when signs is called with the empty list.

Take a picture of your diagram – we'll ask you to upload it after the next problem.

Task: Go to the tool and look at how the parts of the diagram that you drew aligns with the contents of the "Problem 1" boxes. Replace the pink "FILL IN" boxes from problem 1 with details from your drawing.

Note: the [] notation in the blocks stands for a function-call box from the diagram (alternatively phrased, the "hole" that the return value will fill). It is not the empty list, which we write as either [list:] or empty.

Task: Once you have the blocks filled in drawn down to the empty, plug values into the local context holes (the [] spots) through each call record (from bottom to top) to compute the value of the function (this would be the same as replacing each box with its value in the diagram). Do that, and make sure you see how the final answer gets generated.

Task: When people first see recursion, they often believe that the function will return the answer for the empty case (since in the code, the function returns a simple value in that case). What aspect of the chain diagram illustrates why this doesn't happen?

---

CHECKPOINT: Call over a TA once you reach this point.

---

Exercise 2: Creating Palindromes

A palindrome is a word whose characters are in the same order whether read from left to right or right to left. "abba" and "tacocat" are both palindromes.

The following code makes a list of letters into a palindrome:

fun make-palindrome(letters :: List<String>) -> String:
  cases (List) letters:
    | empty => ""
    | link(fst, rst) =>
      # here, + is being used to append strings
      fst + make-palindrome(rst) + fst
  end
where:
  make-palindrome([list: "a", "b", "c"]) is "abccba"
end

Task: Draw the function-call diagram up to the call of make-palindrome on the empty list. Based on your diagram, complete the "FILL IN" boxes in the "Problem 2" blocks in the tool.

Task: Upload the picture of your diagram from the signs problem and a picture of the diagram from this problem to this Google Form. We're not collecting names – we just want to see what sorts of pictures you are drawing.

Exercise 3: Counting Fruits

An intergalactic food importer wants to count how many fruits are named in a list of items that a customer has ordered. The importer has created a function is-fruit that checks whether an item is the name of a fruit that they can supply. The count-fruit function uses is-fruit to tally up the number of known fruits in a list of items.

fun is-fruit(word :: String) -> Boolean:
  (word == "yumberry") or 
  (word == "albaloo") or 
  (word == "apple") or 
  (word == "thatinungu")
end

fun count-fruit(items :: List<String>) -> Number:
  cases (List) items:
    | empty => 0
    | link(fst, rst) =>
      if is-fruit(fst):
        1 + count-fruit(rst) 
      else:
        count-fruit(rst)
      end
  end
end

Consider the following example:

count-fruit([list: "yumberry", "kale", "apple"])

Task: "Problem 3, Task 1" in the starter file gives the structure of calls that exist at the point when is-fruit is called with the first element in the list, yumberry. Update the "FILL IN" boxes in this task. You can draw the paper diagram first, or not, based on whether you'd find it helpful.

Task: Separately, draw the diagram of unfinished calls that exist at the point when is-fruit is called with the second element in the list, kale. You may work on paper or work in the tool, whichever you prefer.

Task: Where is the is-fruit block with input yumberry in this new diagram? Explain why it is where it is. (write down your answer)

Task: Update the "FILL IN" in "Problem 3 Task 2" to show the unfinished call records that exist at the point when count-fruit is called with the empty list.

Task: Compare the sequence of "local context" terms in this chain to the "local context" terms for the signs problem. What do you notice is the same and different between about the two set of terms? Write down your answer.

Task: Now, think about whether each of the functions you worked on involved mapping or filtering. What hypothesis can you make about the sequence of "local context" terms for map-like functions versus filter-like functions? Write down your answer.

---

CHECKPOINT: Call over a TA once you reach this point.

---

Part 2: Recursive Programming Practice

If you have been comfortable writing recursive programs in class, you can skip ahead to part 3

Imagine that you are playing a game that asks you to generate a collection of words from a specified set of letters. The following functions check various conditions against those words in order to score the game.

Task: Develop a function all-have-t :: List<String> -> Boolean that takes a list of words and determines whether every word in the list contains the letter "t".

Task: Develop a function compute-score1 :: List<String> -> Number that takes a list of words and produces a score which is the sum of the lengths of all the words.

Task: Develop another scoring function compute-score2 :: List<String> -> Number in which the score for a single word is 1 if it has four or fewer characters. For words longer than four characters, its score is the length of the word.

Task: Look at the two functions you've just written. Is there a common pattern to writing "scoring"-style functions? At what point do they differ?

Task: If you aren't sure how these functions are working, draw out call record chains (either with the tool or with the same components on paper) to trace out how the computation is evolving.

Part 3: Richer Recursion Practice

Task: Write a function make-circles(rad-list :: List<Number>) -> Image that takes in a list of numbers representing radii and produces an image consisting of adjacent green circles. Each circle should have the radius of its corresponding list index. In other words, the first circle should have the same radius as the first element of rad-list, and so on. The final circle in the image should always be a black circle of radius 10, which is not represented in the list.

For example, make-circles([list: 40,60,10]) should produce an image that looks like the following:

Task: Now, we want a function that lets us change the colors of the circles as well. The function make-better-circles(rad-list :: List<Number>, color-list :: List<String>) -> Image should take in:

• A list of Numbers representing radii
• A list of Strings representing valid Pyret colors

As before, the function should output an image of adjacent circles. This time, each circle should have both the color and radius of its corresponding list index. The first circle should be the same color as the first element of color-list and the size of the first element of rad-list, and so on. The final circle in the image should still be a black circle of radius 10, not in either list.

For example, make-better-circles([list: 30,40,50], [list: "orange", "olive", "blue"]) should produce an image that looks like the following:

Task: Write out a sequence of related examples (like we did in Monday's lecture) to show how the two lists interact within and across the examples.

Task: Write the code for this problem. (Note: Part of the point of this problem is to have you think through which of the two input lists is "driving" generation of the circles. That should be the list you break down in the cases expression.)

Task: Modify your make-better-circles function to raise an error if there aren't enough colors in the color list for all of the radii

---

CHECKPOINT: Call over a TA once you reach this point.

---

More Challenging Task: Write a new version of make-better-circles called make-circles-recycle in which the list of colors can be shorter than the list of radii. The circles should cycle through the list of colors in order, repeating until all circles have been generated. For example, given a list of four radii and the two colors [list: "red", "brown"], the circles would appear in colors red, brown, red, brown.

Warning: it is easy to make this unnecessarily complicated, especially if you have programmed before. This is an exercise in elegance. If you find yourself thinking about this by counting and modulo, for example, try again!

---