15110 SUMMER SESSION TWO 2014

Lab 6 - Monday, July 14

Goals

The purpose of this lab is to get you to write recursive functions. When you are done, you should be able to

Identify the base case and recursive case of a given function
Trace the execution of a given recursive function
Implement simple recursive functions over integers, one-dimensional lists, and nested lists

Deliverables

multiply.py
stars.py
first_odd.py

Place these files in a lab6 folder. Before leaving lab, zip up the lab6 folder and hand in the zip file.

TA Demonstration (as necessary)

Function blast_off(n) in blast_off.py, which prints the integers from n down to 0, each on a separate line, and then prints Blast off! and return None.
```
def blast_off(n):
    print(n)
    if n == 0:
        print("Blast off!")
        return None
     blast_off(n-1)
```
Drawing the recursion tree for blast_off
Review how to create a list with all but the first element of a given list.
Review nested lists such as [2,[4,[6,7,8],10]]. What is the length of this list? How can we access the number 7? How can we test if an element of the list is itself a list?

Activities

In multiply.py write a RECURSIVE Python function multiply(a,b) that computes the value of a * b based on the following RECURSIVE formula. Assume that the function is always called with a non-negative integer for b. \[ a \times b = \begin{cases} a & \text{if } b = 1 \\ a + {a} \times (b - 1) & \text{if } b > 1 \end{cases} \]
(Does this formula look somewhat familiar?)
```
>>> multiply(5,1)
5
>>> multiply(5,10)
50
```
In stars.py write a RECURSIVE function called num_to_bar(numlist) that prints a bar graph of the numbers given in numlist using stars. Your solution must use recursion and should NOT have a loop in it. You can assume that numlist contains non-negative numbers only. Number 0 in the list causes the program output to contain a blank line in the corresponding position. You can use the function print_stars(n) below as a helper function, which prints a sequence of n stars recursively.
```
def print_stars(n):
    if n == 0:
        print("")
    else:
        print("*", end = "")
        print_stars(n-1) 
```
```
>>> num_to_bar([5,2,6,4])
*****
**
******
****
>>> num_to_bar([5,2,0,4])
*****
**

****
```
One place where recursion is especially useful is in searching nested lists (lists of lists). Consider the function first_odd(x) that returns the first component of x that is an odd number or None if no elements are odd. Think why this function would be harder to write using a while loop. Write the recursive function first_odd(x) in a file called first_odd.py
```
>>> first_odd([2,[4,[6,7,8],10]])
7
>>> first_odd([2,[4,[6,8],3]])
3
>>> first_odd(5)
5
```
(Think of some other interesting test cases and share them with your classmates for testing.)