# Lab 6: Recursion Again and Again

15 October 2021

The purpose of this lab is to give you practice reading, understanding, and writing functions involving lists and recursion.

# Setup

Create the file lab06.arr and copy/paste the following into it: import lists as L

As usual, ask your instructor or a coach if you're stuck. Remember to save your work every so often.

# Exercise 1: Tracing

Look at the following recursive function. In class, you've seen this function or ones that are very similar (e.g., my-sum).

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

Trace the execution of the my-product([list: 5, 2, 3]), showing the values of lst, f, and r and the return value each time the function is called. If lst is empty, there are no values for f and r, so you can leave those lines out. You should fill in the return values (in reverse order) after you've shown the values of lst, f, and r for each call.

#|
my-product([list: 5, 2, 3]):
lst is [list: 5, 2, 3]
f is ...
r is ...
return value is ...
it calls
my-product(...)
f is ...
r is ...
return value is ...
it calls

...

it calls
my-product(empty)
return value is ...

|#

# Exercise 2: sum-of-cubes

Fill in the missing parts to write a function that takes in a list of Numbers and returns the sum of the cubes of the numbers:

fun sum-of-cubes(lst :: List<Number>) -> Number:
doc: "computes the sum of the cubes of the numbers in lst"
cases (List) lst:
| empty      => ...
end
where:
sum-of-cubes(empty) is 0
sum-of-cubes([list: 1, 2, 3]) is 36
end

# Exercise 3: list-to-string

Fill in the missing parts to write a function that takes in a list of Strings and returns a single string with all the strings “glued” together. For example list-to-string([list: "ab", "cd"]) should return the string "abcd". Your function should call string-append to glue two strings together.

fun list-to-string(lst :: List<String>) -> String:
doc: returns a single string
consisting of all of the strings in list
lst 'glued' together

...

where:
list-to-string(empty) is ""
list-to-string([list: "hello"]) is "hello"
list-to-string([list: "hello ", "world"]) is "hello world"
list-to-string([list: "one", "two", "three"]) is "onetwothree"
end

# Exercise 4: max-pos-num

Fill in the missing parts to write a function max-pos-num that takes in a list of positive numbers and returns the largest number on the list. 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.

fun max-pos-num(lst :: List<Number>) -> Number:
doc: returns the maximum
element of a list of positive numbers;
if the list is empty, returns -1.
Assume that the input list does not have
any negative numbers
...

where:
max-pos-num(empty) is -1
max-pos-num([list: 3, 5, 1, 4]) is 5
end

# Exercise 5: long-strings

Fill in the missing parts 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: returns a list consisting
of those elements of lst
that are longer than len
cases (List) lst:
| empty => ...
if string-length(f) > len:
...
else:
...
end
end
where:
long-strings(empty, 0) is empty
long-strings([list: "the", "quick", "brown", "fox"], 4) is [list: "quick", "brown"]
long-strings([list: "the", "quick", "brown", "fox"], 5) is empty
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 L.filter to accomplish the same thing that long-strings does (with much less code).

• When you've complete the exercises, show your code to me or one of our coaches.

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