Lab: Basic Recursion
Preparation
a. Create a folder called lab-10-29
in your StuWork
directory.
b. Open a Terminal
and navigate to your lab-10-29
directory.
c. Create a file named data_processing.py
and put all of the code from it today in there.
Exercise 1
Consider the following implementation of the largest
procedure that returns the largest element of a list.
def largest(numbers):
if len(numbers) == 1:
return numbers[0]
else:
first = numbers[0]
the_rest = numbers[1:]
return max(first, largest(the_rest))
a. Copy and paste the above code into your lab file, open up a REPL, and import the largest
function into the REPL.
b. Test the largest
function by executing it on a variety of inputs.
c. What do you think happens if you run largest
on a singleton list? Verify this in the REPL.
d. What do you think happens if you run largest
on the empty list? Verify this in the REPL.
e. What do you think happens if you run largest
on lists with non-numeric elements? Verify this in the REPL.
f. Add the following line of code immediately before the return
statement:
print(" ==> max({}, largest({}))".format(first, the_rest))
g. Close and reopen the REPL to refresh its definition of the largest
function. Now execute largest
on a variety of inputs to trace the recursion through to the base case.
Exercise 2
Consider the following function select_strings
that extracts the strings out of a list.
def select_strings(lst):
if len(lst) == 0:
return []
elif type(lst[0]) == str:
# If the first element is a string, add it to the list of
# the rest of the strings in the list
return [lst[0]] + select_strings(lst[1:])
else:
# Otherwise return just the strings in the rest of the list
return select_strings(lst[1:])
a. Copy and paste the above code into the lab file and import it into the REPL.
b. Discuss the code with your partner and make sure you understand each of the components.
c. Execute the code on a variety of inputs and ensure that it is extracting out the strings as expected.
Exercise 3
Consider the following function is_palindrome
that checks if a string is the same if read both forwards and backwards. An example of a palindrome is “civic”.
def is_palindrome(s):
if len(s) <= 1:
return True
else:
# Checks if the first character is equal to the last
# and checks if the substring excluding the first and
# last characters is also a palindrome
return (s[0] == s[-1]) and is_palindrome(s[1:-1])
a. Copy and paste the above code into the lab file and import it into the REPL.
b. Discuss the code with your partner and make sure you understand each of the components.
c. Execute the code on a variety of inputs and ensure that it is working as expected.
d. Add the following line of code immediately before the if
statement (just after the declaration of the function):
print('is_palindrome("' + s + '")')
e. Execute is_palindrome
on a variety of strings and watch how it recurses.
Exercise 4
Suppose that the len
function was not written for lists. How might we implement it? We could remove one element from the list, make a recursive call, and then add one.
a. Using this idea, write a recursive function list_len
that takes in a list as a parameter and returns the length of the list. You may not use len
for this.
b. Check your answer on a variety of inputs. (Be sure to check the empty list, too)
Exercise 5
Suppose that we want to count the number of occurrences of a certain value val
in a list lst
. Using a similar idea from exercise 2, write a recursive function called count(lst, val)
that returns the number of times val
appears in lst
.
Check your answer on a variety of inputs including the empty list.
Exercise 6
Now let’s try implementing a function similar to range
. Recall that range(n)
returns a sequence of numbers starting at 0
and ending at n-1
. Recursion could be helpful in implementing this procedure.
Write a recursive function called list_range(n)
that takes in a number n
and returns a list that contains all the integers between 0
and n-1
.
Exercise 7
Using a technique similar to exercise 3, write a recursive function called reverse(s)
that takes in a string as a parameter and returns a new string that has the characters in the reverse order. Thus, reverse("abc")
returns the string "cba"
.