Lab 6: Recursion Again and Again
14 October 2022
Learning objective
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.
Exercise 1: Tracing recursion
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 ...
|#
Exercise 2: sum-of-cubes
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.
Exercise 3: max-pos-num
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.
Exercise 4: bar-chart
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
!
Exercise 5: long-strings
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.
Submitting the lab
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.