Lab 6: Recursion

Learning goals

By the end of this lab, you will be able to:

• Write recursive functions to solve problems on recursive structures (like nested lists)
• Implement the List ADT using a recursive approach

Task 0: Setup

Download nested.py and recursive_list.py into your labs/lab6 folder.

Some helpful advice:

1. As with the last lab, draw lots of pictures and use the drawings to guide your code.
2. Once you get the hang of recursion, most of the functions and methods in this lab take no more than a few lines of code! Remember the recursive structure of nested lists, and structure your code in the same way.

Task 1: Practice with nested lists

Open the file nested.py that contains a few nested list functions for you to implement. To help you, the doctest examples illustrate (a) a base case, where no recursive calls are needed, and (b) a general case where you combine recursive calls to return the desired result.

For each of the functions, read the docstring and implement it using recursion. Follow these four design steps:

1. Identify the recursive structure and write down the code template for nested lists:

   def f(obj: Union[int, List]) -> ...:
       if isinstance(obj, int):
           ...
       else:
           for sublist in obj:
               ... f(sublist) ...

2. Implement the base case(s) directly.

3. Write down a concrete example with a somewhat complex argument, and then write down the relevant recursive calls and what they should return.

4. Think about how to combine the recursive calls to compute the correct output.

Task 2: Recursive implementation of the List ADT

Now, you will use your growing comfort with recursion to implement the List ADT recursively. This will be the third implementation of the List ADT that we have covered in this course. Remember that implementations can have the same public interface, even though they implement their methods quite differently! This guarantees that if client code switches to using the new implementation, it will work exactly as it did before.

Open the file recursive_list.py that contains a partial implementation of a recursive list class RecursiveList. In this task you will implement the rest of its methods.

There are two important things to note before you begin:

• A recursive list has two attributes, the first item in the list, and the rest of the list.
• An empty list is represented by having its _first and _rest attributes be None. This is expanded upon in a representation invariant in the class documentation.

When you are ready, follow these steps to learn and work with this new recursive structure.

1. Review the given documentation for the RecursiveList class. Carefully read the descriptions of each attribute, and the representation invariants.

2. Read the docstring and code for the __init__, is_empty, and __str__ methods and understand how each of these three methods works on these instances.

3. Read the docstring for __len__ and implement the method. Your implementation should handle the base case, where the list is empty, and the recursive case, where the list definitely has one item, and possibly more items. Remember that even if a RecursiveList has just one item, its _rest attribute still refers to a RecursiveList object!

4. Read the docstring and implementation for __contains__. Again, __contains__ has two base cases. Then read the docstring for count, which is similar to __contains__, and implement the method.

5. Read the docstring for __getitem__. __getitem__ should have two base cases: a) the list is empty, or b) the index is 0, referring to the first item in the list. Then, implement the method.

6. Read the docstring for __setitem__, which is similar to __getitem__, and implement the method.

7. Read the docstring for the methods insert and pop, that mutate a list at a specified index. For each method, write down the base case(s), and then implement it using recursion.

   You may find implementing the methods _pop_first and _insert_first helpful.

Additional exercises

If you finish the tasks above, here are some additional exercises that you may try.

Map

In Python, functions are first-class objects, which means, among other things, that they can be passed as arguments to other functions. For example, the following function takes in two arguments, a function and an object, and tries to call the function on that object and see whether the result is True or not.

def try_function(f: Callable[[Any], bool], arg: Any) -> None:
    if f(arg):
        print('Success!')
    else:
        print('Failure...')

If we define the following function,

def positive(n: int) -> bool:
    return n > 0

we can use try_function like this:

>>> try_function(positive, 10)
'Success!'
>>> try_function(positive, -4)
'Failure...'

Building on this example, implement the method map in the RecursiveList class, which returns a new recursive list created by applying a function to each item in the original list. Note that map does not mutate the original list.