Lab 13, Part 1: Fruitful recursion warm-up

Create a new file in your lab13 folder called part1.py and complete the following tasks.

Task 1. sumUpTo

Write a fruitful recursive function called sumUpTo that will take an integer and return the sum of all numbers up to and including that integer.

(You saw this function in lecture, but attempt it without refering to your notes.)

Click here for a sketch of the function call diagrams

For example:

sumUpTo(0) # returns 0
sumUpTo(3) # returns 6 (because 3 + 2 + 1 = 6)
sumUpTo(10) # returns 55
sumUpTo(88) # returns 3916
sumUpTo(500) # returns 125250
sumUpTo(1000) # --> ERROR maximum recursion depth exceeded

Make sure that your function actually returns a value (as opposed to merely printing it).

Here's a way to test it— add the following line to your file and run it...

print(sumUpTo(10))

...it should produce the number 55. If it produces None, then your function prints rather than returns the value and it needs to be fixed.

Task 2. sumBetween(start, end)

Write a fruitful recursive function called sumBetween that will take a start and end integer and return the sum of all numbers between start and end, inclusive. Assume that start and end are always non-negative integers.

For example:

sumBetween(0,0) # returns 0
sumBetween(0,3) # returns 6 (because 1 + 2 + 3 = 6)
sumBetween(3,3) # returns 3 
sumBetween(3,7) # returns 25 (3 + 4 + 5 + 6 + 7 = 25)
sumBetween(10, 14) # returns 60 (10 + 11 + 12 + 13 + 14 = 60)
sumBetween(87, 94) # returns 724
sumBetween(117, 213) # returns 16005
sumBetween(12345, 13524) # --> ERROR maximum recursion depth exceeded

Task 3. mapO

Write a fruitful recursive function called mapO that takes a list of strings, and returns a list of strings with the letter o added to the end of each string.

Examples:

print(mapO(['hell', 'cheeri', 'JL', 'ore']))
print(mapO([]))
print(mapO(['No', 'Yes', 'Maybe']))
print(mapO(['Robert', 'Carl', 'Leonard', 'Rome', 'Valentin']))

...produces:

['hello', 'cheerio', 'JLo', 'oreo']
[]
['Noo', 'Yeso', 'Maybeo']
['Roberto', 'Carlo', 'Leonardo', 'Romeo', 'Valentino']

Remember that you can use concatenation (+) not only with strings, but also with list elements.

For example, ['Mary Kate'] + ['Ashley'] ==> ['Mary Kate','Ashley']

OPTIONAL Task 4. Dropping R words

Write a fruitful recursive function called dropRs that accepts a list of strings and returns a list containing only the strings that did not start with the letter r.

Examples:

print(dropRs([]))
print(dropRs(['snow', 'rain', 'sleet', 'turtles']))
print(dropRs(['Swim', 'Bike', 'Run']))
print(dropRs(['cs111', 'is', 'so', 'much', 'fun']))
print(dropRs(['lather', 'rinse', 'repeat']))
print(dropRs(['read', 'write', 'rithmetic']))
print(dropRs(['red', 'room', 'really']))

...produces:

[]
['snow', 'sleet', 'turtles']
['Swim', 'Bike']
['cs111', 'is', 'so', 'much', 'fun']
['lather']
['write']
[]

OPTIONAL Task 5. Dropping R words and counting how many are dropped

Write a fruitful recursive function called countAndDropRs that accepts a list of strings and returns a tuple containing two items: 1) a list contain only the strings that did not start with the letter r and 2) the number of strings that were dropped from the original list.

Return a tuple? Really? Yup, really. Be careful, because this means that your function must return a tuple in both the base case and the recursive case. This also means that each recursive call will return a tuple.

There are hints in Helpful Hints and Diagrams (see Table of Contents below), in particular, this countAndDropRs diagram may be useful.

Examples:

print(countAndDropRs(['snow', 'rain', 'sleet', 'turtles']))
print(countAndDropRs(['Swim', 'Bike', 'Run']))
print(countAndDropRs(['cs111', 'is', 'so', 'much', 'fun']))
print(countAndDropRs(['lather', 'rinse', 'repeat']))
print(countAndDropRs(['read', 'write', 'rithmetic']))
print(countAndDropRs(['red', 'room', 'really']))

...produces these tuples:

(['snow', 'sleet', 'turtles'], 1)
(['Swim', 'Bike'], 1)
(['cs111', 'is', 'so', 'much', 'fun'], 0)
(['lather'], 2)
(['write'], 2)
([], 3)

Table of Contents