Lab 6: Recurring, Again and Again

Learning Objective

The goal of this lab is to understand when and how to use recursion while writing functions.

Recursion can be a very effective strategy while writing functions, especially when dealing with list inputs. But writing recursive functions requires first gaining some intuition for when it can be useful. Each of the problems below is set up well for a recursive function solution, and in each of these cases (especially the later ones), we recommend thinking about why recursion can be used to write cleaner solutions than through other strategies.

If you don’t feel more comfortable with recursion after working on this lab, come to TA hours!

Hints & Guidelines

This week, we’ll be practicing solving problems that require list recursion. For some solutions, you’ll be allowed to use List library functions. For others, you’ll need to write recursive functions (using cases) as discussed in class.

Remember to follow the Design Recipe steps:

Design Recipe

1. Write the name, inputs (with types), and output type for your program.

2. Write some examples of what your program should do. Cover the various cases of the input, including the empty case for lists. For a list problem, writing 2-3 examples that handle a list and its suffixes can be helpful in seeing the pattern that defines the link case.

3. Write a task plan–-a list of the computations you'll need to build up your program. Annotate each item with a built-in operation or helper function you could write to handle that task.

4. For each recursive function you need to write, if the function operates over lists, copy the template code, replacing the function name, inputs, and types with ones that are relevant to your program.

   ​​​​fun my-fun(lst :: ?) -> ?
   ​​​​  cases (List) lst:
   ​​​​    | empty => 
   ​​​​    | link(fst, rst) => my-fun(rst)
   ​​​​  end
   ​​​​end
   

   Note: fst and rst can be named anything–-they are just names that we give the first and rest of the List lst.

5. Fill in the template with the code that is specific to the function you are trying to write.

Setup

Paste the following code into the definitions window (coord will come up in a later problem):

include image
import lists as L

data Coord:
  | coord(x :: Number, y :: Number)
end

Part 1: List Operations & Recursion

1. Use L.map to write the following functions:

   • doubles-words(word-list :: List<String>) -> List<String>, which takes in a list of strings and doubles each element. For example, doubles-words([list: "hello", "friend"]) should return [list: "hellohello", "friendfriend"]

   • create-stars(star-colors :: List<String>) -> List<Image>, which takes in a list of strings representing valid colors and produces a list of stars (take a look at the Pyret image documentation if you can't remember how to make a star). Each star should have a side length of 10 units.

2. Rewrite the functions from above, but this time without using L.map. Instead, use the template described in Hints & Guidelines. The function headings should be:

   • double-words-no-map(word-list :: List<String>) -> List<String>

   • create-stars-no-map(star-colors :: List<String>) -> List<Image>

---

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

---

Part 2: More recursion

1. Write a function build-sentence(word-list :: List<String>, punct :: String) -> String that takes in:

   • A list of Strings representings words in a sentence
   • A String representing a punctuation mark to place at the end of the sentence

   and returns a single String containing each word in order, with a space between each item of word-list and ending with punct.

    >>> build-sentence([list: "I", "like", "recursion"], "!")
    "I like recursion !"
    >>> build-sentence([list: ], "?")
    "?"

2. Write a function generate-pattern(coord-list :: List<Coord>, img :: Image) -> Image that takes in:

   • A List of Coord's representing coordinates
   • A background image

   The function should output a new image with blue circles placed on the background at each coordinate in the coord-list. Each circle should be colored "blue" and have a radius of size 10.

   For example, generate-pattern([list: coord(0,0), coord(100, 30), coord(190, 190)], square(200, "solid", "salmon")) should produce an image that looks like the following:
   

   Note: Use place-image from the Pyret image documentation to put a circle onto an image at a specific coordinate (the "Scene" output type is just an image).

   HINT: A brief review of Coords:
   Coords take the form coord(x, y) where x represents the x-component and y represents the y-component. To make one, just replace x and y with the numbers you want. For example, if you write the following code in the definitions window:

   ​​​​coord1 = coord(5, 6)
   ​​​​coord2 = coord(7, 8)
   

   You can do the following in the interactions window:

   ​​​​>>> coord1.x
   ​​​​5
   ​​​​>>> coord2.y
   ​​​​8
   

   Note that both the x- and y- components of a Coord are actually of type Number, so you can treat them like numbers. For example, you could define a new Coord in the definitions window like this:

   ​​​​coord3 = coord(coord1.x + 5, coord.y + 10)
   

   And wind up with the following in the interactions window:

   ​​​​>>> coord3.x
   ​​​​10
   ​​​​>>> coord3.y
   ​​​​16
   

3. 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 a radius equal to the first element of rad-list, the second circle should have a radius equal to the second 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:
   

   NOTE: For this problem, use explicit recursion rather than built-in list operators.

4. Now, we want a function that lets us change the colors of the circles as well. Write a function make-better-circles(rad-list :: List<Number>, color-list :: List<String>) -> Image that takes 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:
   

   HINT: You can access the first element of a list by doing my-list.first and the rest of the list by doing my-list.rest.

5. Write a function spell-check-alot(word-list :: List<String>) -> List<String> which takes in a list of strings and replaces each instance of “alot” (1 list element) with “a” followed by “lot” (2 list elements)

   HINT: If you're having trouble approaching this problem, start by writing a function that replaces all instances of "alot" with "a lot" (both a single list element). Then, think about how to modify your function to create two list elements.

---

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

---

Part 3: Lists of Lists

Lists can contain more complicated data than just numbers, string, or images. For example, lists can contain other lists! As an example, imagine that we need to store weather readings across several days. Each day could be captured as a list of temperature readings, as follows:

temp-data = 
  [list: 
    [list: 56, 58, 60, 64, 64, 58],
    [list: 62, 65, 65, 65, 65, 63, 60],
    [list: 45, 48, 50, 52, 53],
    [list: 53, 53, 51, 48, 45, 42]
  ]

Note that the inner lists can be of different lengths (the weather data is missing some readings).

We want to write a recursive function days-in-range that counts how many days had all of their temperatures within a given range. For example:

fun days-in-range(temps :: List, low :: Number, high :: Number) -> Number:
  ...
where:
  days-in-range(temp-data, 45, 60) is 1 # the 2nd to last row
  days-in-range(temp-data, 65, 80) is 0 # no row has all temps above 65
end

1. Write a task list for days-in-range. For each task, state the name and input/output types of a function you will write to perform the task. After your list is done, contrast it to ours.

2. Write a function that takes one of the inner lists and the low/high range values and determines whether all of the temperatures are within that range (including the low/high values). Write an explicitly-named function (rather than a lam function) to check whether a temperature is between the low and high range values (having a named function helps set up for a later question).

3. Write a function that takes in a list like temp-data, as well as the low and high range values, and counts how many days consist only of temps within that range.

Understanding Recursion

Now, let's step back and make sure you understand how this program evaluates. Here is a smaller data example:

temp-data-short = 
  [list: 
    [list: 56, 58, 60],
    [list: 45],
    [list: 53, 53]
  ]

Assume you were going to evaluate the expression

days-in-range(temp-data-short, 50, 60)

1. What is the sequence of function calls that get made as this program evaluates? Write out the list with just enough detail that you and your partner agree on what the inputs will be at each call.

2. Go to http://cpo.herokuapp.com/editor, which is the experimental Pyret version that shows you how programs evaluate. Copy and paste your data and code for just this temps problem into the editor. Press the Trace and Run button. At the prompt, run the days-in-range expression that you just explored by hand.

   Press Trace Last. You should get a tree-shaped summary diagram of which function calls were made. If you don't see a diagram with lots of calls, make sure the drop down on the upper left corner says "All" (the other two options let you expand the tree manually by clicking on the blue circles–-each click will expand the tree; "depth first" lets you see the calls that get made in order). If you hover your mouse over a function call, the tool will show you the input(s) to that call and the result of that call.

   You read the diagram by following the calls in the leftmost branch until they end, then the next-leftmost branch, and so on (going "deep" when you can, moving left to right otherwise). Did you predict the same sequence of calls?

3. As this program runs, your parameters (the temps, low range, and high range) take on many different values. Is this a potential source of error in your code? How might Pyret keep track of which values you have at each point in the diagram?

4. What questions do you have about recursion after working on this lab? Enter them in the following form, so we can go over them.

---

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

---

Another lab in the books!

Great work on conquering a recurrence assignment!

Heading to 18? A More Advanced Option

This is the additional problem that we didn't get to cover in the CS18-facing lecture on Monday. It isn't a required part of lab, but those of you heading to 18 may want to take a look whenever you have a chance.

Consider the following function for scoring a word-based game. Notice that the function has three calls to filter, each of which runs over the list words.

import lists as L

fun total-score(words :: List<String>) -> Number:
  doc: "computes scores for a word game"
  long = L.filter(lam(wd): string-length(wd) > 6 end, words)
  short = L.filter(lam(wd): string-length(wd) < 5 end, words)
  fun has-z(wd): string-contains(wd, "z") end
  zs = L.filter(has-z, words)
  if L.length(short) > 0:
    (L.length(zs) + L.length(long)) / L.length(short)
  else:
    L.length(zs) + L.length(long)
  end
where:
  total-score(empty) is 0
  total-score([list: "hi", "bye"]) is 0
  total-score([list: "pizza", "pie", "zzs"]) is (2 + 0) / 2 
  total-score([list: "pizzazz", "pie", "zebras"]) is (2 + 1) / 1
end

Running three separate filters over the same list might feel excessive. Can't we do this computation with just one filter over the list?

Task: Discuss with your lab partner – do you think you can modify this code to collapse the three uses of filter into one shared use of filter? Why or why not?

Even if the calls to filter can't be combined, we can always write a straight-up recursive function to walk down the list once, performing the computations of the separate filters in one pass.

Task: Write a recursive function that performs the same computation, but only works with each element in the list once. If you get stuck, write down what you are stuck on (as part of practicing describing code challenges precisely).

Hint: Can you use parameters to help?

Still stuck?

Hint: Do parameters always have to capture inputs to the computation? Can you use them creatively?

Task: Which of the two solutions (our original or yours) do you prefer? Why?

Task: Write down what you have learned from working on this problem.

---

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

---