Lab 6: Recursion Again and Again

14 October 2022

In class, we’ve been writing recursive functions, where a function body calls the same function, just on a smaller part of the data. This lab gives you practice reading, understanding, and writing functions involving lists and recursion.


This lab can be completed in pairs!

If you choose to work in a pair, you’ll make a single code file which you’ll upload to Gradescope with both your names.


Consider the following recursive function:

fun product(lst :: List<Number>) -> Number:
  doc: "Return the product of the numbers in list lst"
  cases (List) lst:
    | empty => 1
    | link(f, r) => f * product(r)
  end
where:
  product([list: 5, 2, 3]) is 30
  product([list:    2, 3]) is ...
  product([list:       3]) is ...
  product([list:        ]) is ...
end

In class, you’ve seen this function or ones that are very similar, e.g., my-sum.

Task: Trace the execution of the example

product([list: 5, 2, 3])

showing the values of f and r and the return value each time the function is called.

Write your solutions as comments in your file in this format:

#|
product([list: 5, 2, 3]):
  f is 5
  r is [list: 2, 3]
  return value is 30

  it calls product(...)
    f is ...
    r is ...
    return value is ...

    it calls product(...)
      f is ...
      r is ...
      return value is ...

      it calls product(empty)
        return value is ...
|#

Consider this template for a function:

fun sum-of-cubes(lst :: List<Number>) -> Number:
  doc: "Return the sum of the cube of each number in the list"
  cases (List) lst:
    | empty => ...
    | link(f, r) => ...
  end
where:
  sum-of-cubes([list: 1, 2, 3]) is 36 because ...
  sum-of-cubes([list:    2, 3]) is 35 because ...
  sum-of-cubes([list:       3]) is 27 because ...
  sum-of-cubes([list:        ]) is  0
end

The examples give the right answers but don’t show why we get that answer. That’s what because lets us fill in. For example, for product in Exercise 1, we could have written:

  product([list: 5, 2, 3]) is 30 because 5 * product([list: 2, 3])

An example like this shows how the solution is defined using the solution to a smaller problem. This makes writing the body of the function easy!

Task: Copy the template for sum-of-cubes and fill in the ... in each example with an appropriate expression showing how we get the right answer.

Now you’re ready to fill in the body of the function:

Task: Replace ... with the appropriate code for both the base case and the recursive case.

Task: Fill in the missing parts below to write a function max-pos-num that takes in a list of positive numbers and returns the largest number on the list.

fun max-pos-num(lst :: List<Number>) -> Number:
  doc: "Return the maximum element of a list of positive numbers; if the list is empty, return -1. Assume that the input list does not have any negative numbers"
  ...
where:
  max-pos-num([list: ]) is -1
  max-pos-num([list: 3, 5, 1, 4]) is 5
end

If the list is empty, max-pos-num should return -1. (Note that every positive number is greater than -1!)

Your function should call num-max to find the maximum of two numbers.

Task: Fill in the missing parts below to write a function that takes in a list of (non-negative) numbers and draws a bar chart using the given heights.

fun bar-chart(lst :: List<Number>) -> Image:
  doc: "Return an image of bars of the given heights next to each other"
  ...
end

You don’t need to write test cases for this function, but you should call it to make sure it works as intended. For example,

bar-chart([list: 100, 200, 50, 75, 100, 10])

might look like this:

But you can feel free to adjust the appearance.

Hint: You may want to refer to the Pyret image documentation – and note the existence of empty-image!

Task: Fill in the missing parts below to write a function long-strings that takes in a list of strings lst and a Number len and returns a list that includes all of the strings from lst whose length is greater than len.

fun long-strings(lst :: List<String>, len :: Number) -> List<String>:
  doc: "Return a list consisting of those elements of lst that are longer than len"
  cases (List) lst:
    | empty => ...
    | link(f, r) =>
      if string-length(f) > len:
        ...
      else:
        ...
      end
  end
where:
  long-strings([list: ], 0) is empty
  long-strings([list: "the", "quick", "brown", "fox"], 5)
    is empty
  long-strings([list: "the", "quick", "brown", "fox"], 4)
    is [list: "quick", "brown"]
  long-strings([list: "the", "quick", "brown", "fox"], 2)
    is [list: "the", "quick", "brown", "fox"]
end

Optional: After you have completed the code for long-strings, show how to use filter to accomplish the same thing that long-strings does but with less code.

  • When you’ve completed the exercises, show your code to your instructor or one of the coaches.

  • Then upload your lab06.arr file to the Lab 6 assignment on Gradescope.