CS21 Lab 10: Recursion

  • Part 1 is due on Monday, December 4 at the start of class. You may submit Part 1 on paper or you can email your professor a PDF or photograph of the the solution before the start of class. Please be sure that your paper/PDF/photograph is legible!

  • Part 2 is due on Saturday, December 2, by 11:59pm and will be turned in the "normal" way using handin21.

Goals

The goals for this lab assignment are:

  • Practice tracing recursive functions

  • Designing recursive functions

  • Identifying base and recursive cases

1. Tracing: Stack Diagrams

The first part of this lab asks you to read four recursive functions. First, identify the base case and recursive case. Second, trace the programs, showing all program output and drawing the stack diagrams without erasing any of the stack frames after the functions end.

Example Question

Given the Python program shown below:

def fact(n):
    if n <= 1:
       return 1
    elif
       f = n * fact(n - 1)
       return f

def main():
   v = fact(4)
   print(v)

main()

Example Solution

  • Base case: when n <= 1

  • Recursive case(s): when n > 1

  • The final output of this program is:

    Output:
24

  • The stack diagram would look like this if we didn’t erase stack frames and ran the program to completion:

    example stack

Program 1

Provide the base case, recursive case, final output, and draw the stack diagram for the program shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def show(lst):
    if len(lst) == 0:
        print("done")
    else:
        print(lst[0])
        show(lst[1:])

def main():
    nums = [1, 5, 2, 8]
    show(nums)

main()

Program 1a

Before you go on, check your understanding! What would happen if we swapped lines 5 and 6 in the program above so that it looked like the program shown below? You only need to provide the output, not the stack diagram.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def show(lst):
    if len(lst) == 0:
        print("done")
    else:
        show(lst[1:]) # these two lines were swapped
        print(lst[0]) # from Program 1 shown above

def main():
    nums = [1, 5, 2, 8]
    show(nums)

main()

Program 2

Provide the base case, recursive case, final output, and draw the stack diagram for the program shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def mystery(a, b):
    if b == 0:
        return 0
    else:
        p = mystery(a, b - 1)
        q = a + p
        return q

def main():
    v = mystery(2, 4)
    print(v)

main()

Program 3

Provide the base case, recursive case, final output, and draw the stack diagram for the program shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def dub(s):
    if s == "":
        return s
    else:
        return s[0] + s[0] + dub(s[1:])

def main():
    r = dub("swat")
    print(r)

main()

2. Designing Recursive Functions

When designing recursive programs, the first step is to identify the base case(s) first: the simplest case where there is not a recursive call. Then move on to the recursive case(s).

2.1. Sum squares

Write a recursive function called sum_squares(lst) that takes a list of integers as its only parameter and returns the sum of all squares of all the numbers in the the list. You can assume that the list contains only integers. Put your solution in squares.py in the labs/10 directory. Be sure that your solution includes a main function that tests your sum_squares function with a few different parameter values.

Your solution must be recursive.

def sum_squares(lst):
    """
    This function sums the squares of numbers in a list of integers

    Args:
        lst (list): a list of integers

    Returns:
        int: the sum of the squares of the values in the list
    """

For example:

sum_squares([]) ==> 0

sum_squares([1, 3, 4, 2]) ==> 30 (since 1*1 + 3*3 + 4*4 + 2*2 = 30)

sum_squares([0, 2, -4, 6]) ==> 56 (since 0*0 + 2*2 + -4*-4 + 6*6 = 56)

sum_squares([5]) ==> 25

2.2. Hiding numbers

Imagine you are writing a function that hides numbers like phone numbers, social security numbers, house numbers, etc. You will write a recursive function called hide that replaces any digits in a string with #. Put your solution in hide.py in the labs/10 directory. Be sure that your solution includes a main function that tests your hide function with a few different parameter values.

Your solution must be recursive.

For practice, you can try to write this function iteratively (using a for loop). If you’d like to try this, call your function hide_loop(string) in the hide.py file. 
def hide(string):
    """
    Returns a new string equal to the old string except that all of the
    numbers have been replaced with the symbol #.

    Args:
        string (str): a string that you want to hide the numbers in

    Returns:
        str: the string with all numbers replaced by the symbol #
   """

For example:

hide('') ==> ''

hide('SCI 256') ==> 'SCI ###'

hide('apples') ==> 'apples'

hide('555-55-5555') ==> '###-##-####'

2.3. Checking to see if all the numbers are positive

Write a function called positive(lst) that takes a list of numbers as its only parameter and returns True if every number in the list is positive; otherwise, the function returns False. You can assume that the list contains only integers and/or floats. Put your solution in positive.py in the labs/10 directory. Be sure that your solution includes a main function that tests your positive function with a few different parameter values.

def positive(lst):
    """
    This function returns True only if every number in the list is positive.

    Args:
        lst (list): a list of integers and/or floats

    Returns:
        True if every element in the list is positive; otherwise, False
    """

For example:

positive([]) ==> True

positive([1, 3.14, 4, 2]) ==> True

positive([1, 3.14, -4, 2]) ==> False

positive([-2, -8, -9, 15]) ==> False