CS21 Lab 10: Recursion

Part 1 is due on Monday, April 21st at the start of class, and will be turned in on paper.
Part 2 is due on Sunday, April 20 by 11:59pm and will be turned in the "normal" way using handin21.

Goals

The goals for this lab assignment are:

Learn how to think recursively
Identify base and recursive cases in functions
Practice tracing recursive functions
Design and implement recursive functions

1. Tracing: Stack Diagrams

The first part of this lab asks you to read several recursive functions, and answer some questions.

First, identify the base case and recursive case.
Second, draw the stack diagram for each of the programs.
Third, show all program output when the full program is run.

Example Question

Given the Python program shown below:

def fact(n):
    if n <= 1:
       return 1
    else:
       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:

For each of the programs below:

First, identify the base case and recursive case.
Second, draw the stack diagram for each of the programs, showing all the stack frames, if we didn’t erase the stack frames and ran them to completion (like the example above).
Third, show all program output when the full program is run.

Program 1

Provide the base case, recursive case(s), 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 main():
    result = bling("swat")
    print(result)

def bling(text):
    if len(text) == 0:
        return ""
    else:
        s = text[0] + "*" + bling(text[1:])
        return s

main()

Program 2

Provide the base case, recursive case(s), 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
14
15
16
17 def main():
    values = [7, 10, 5, 2]
    answer = mystery(values)
    print(answer)
    
def mystery(ls):
    if len(ls) == 0:
        result = 0
        return result
    partial = mystery(ls[1:])
    if ls[0]%5 == 0:
        result = 1 + partial
    else:
        result = partial
    return result

main()

2. Designing Recursive Functions

For this part of the lab, you will design and implement recursive functions.

When designing recursive programs, 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. Count Vowels

Write a recursive function called count_vowels(text) that counts the number of vowels (a, e, i, o, and u) in a given string of text. Write your solution in the file count_vowels.py

Your solution must be recursive.

def count_vowels(text):
    """
    This function counts the number of vowels in the give text.
    The vowels include a, e, i, o, and u. It should count the vowels
    regardless of their case.

    Parameters:
        text (str): a string of text

    Returns:
        int: the number of vowels in the text
    """

Here are some sample calls to count_vowels and their results:

count_vowels("ACME") ==> 2

count_vowels("acme") ==> 2

count_vowels("bcd")  ==> 0

count_vowels("Swat") ==> 1

Be sure that your solution includes a main function that tests your function with several different text values.

2.2. Print Wedge

Write a function called print_wedge(n, ch) that prints a wedge with n rows, using the character ch. Write your solution in the file print_wedge.py.

Your solution must be recursive.

def print_wedge(n, ch):
    """
    Prints a wedge using the symbol ch with height of n.
    You can assume n is greater than or equal to zero.

    Parameters:
        n (int): an integer n>=0 representing the number of rows to print
        ch (str): a single character string to use for the tower

    Returns:
        None

    Side effects:
        Prints a wedge of n rows using the character ch.
   """

For example:

print_wedge(5, "*")
*****
****
***
**
*


print_wedge(3, "$")
$$$
$$
$


print_wedge(1, "+")
+

print_wedge(0, "!")
             <- NOTE: there is no output when n is 0

Be sure to write a main function that includes several tests of your function.

2.3. Get Multiples

Write a function called get_multiples(base, n) that returns a list of length n containing the first n multiples of the base number. Write your solution in the file get_multiples.py.

Your solution must be recursive.

def get_multiples(base, n):
    """
    This function creates a list of length n containing the first n
    multiples of the base number.

    Parameters:
       base (int): a number to create multiples from
       n (int): the desired number of multiples

    Returns:
       (list): a list of the first n multiples of the base number
    """

For example:

get_multiples(3, 4) ==> [3, 6, 9, 12]

get_multiples(2, 6) ==> [2, 4, 6, 8, 10, 12]

get_multiples(5, 1) ==> [5]

get_multiples(7, 0) ==> []

Be sure to write a main function that tests your function multiple times.

3. Requirements

The code you submit for labs is expected to follow good style practices, and to meet one of the course standards, you’ll need to demonstrate good style on six or more of the lab assignments across the semester. To meet the good style expectations, you should:

Write a comment that describes the program as a whole using a comment at the top of the file.
All programs should have a main() function.
Use descriptive variable names.
Write code with readable line length, avoiding writing any lines of code that exceed 80 columns.
Add comments to explain complex code segments (as applicable).
Write a comment for each function (except main) that describes its purpose, parameters and return value.

In addition, you’ll need to demonstrate good top-down design practices on two or more lab assignments across the semester. To meet the top-down design expectations, you should:

Have a main() function that serves as an outline for your program.
Your main() function should call other functions that implement subtasks.
The functions that are called by main() should be well-named and have good comments explaining their purpose, parameters (including their types), and return value (including its type).

For EACH QUESTION in the stack-diagram portion of the lab, you should meet the following requirements:

Draw the correct stack diagram.
Show the base case and recursive case.
Show the final output of the program.

For EACH PROGRAM in the function-writing portion of the lab, you should meet the following requirements:

Your function should contain a non-recursive base case.
Your function should make one or more recursive calls on a smaller version of the problem.
Your function should correctly solve the problem.
To test your solution, your main function should make at least three calls to the recursive function.

Answer the Questionnaire

After each lab, please complete the short Google Forms questionnaire. Please select the right lab number (Lab 10) from the dropdown menu on the first question.

Once you’re done with that, you should run handin21 again.

Submitting lab assignments

Remember to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.

Logging out

When you’re done working in the lab, you should log out of the computer you’re using.

First quit any applications you are running, including your vscode editor, the browser and the terminal. Then click on the logout icon ( or other logout icon ) and choose "log out".

If you plan to leave the lab for just a few minutes, you do not need to log out. It is, however, a good idea to lock your machine while you are gone. You can lock your screen by clicking on the lock xlock icon. PLEASE do not leave a session locked for a long period of time. Power may go out, someone might reboot the machine, etc. You don’t want to lose any work!