CS21 Lab 10: Recursion

Part 1 is due on Monday, December 2 at the start of class. You may submit Part 1 on paper or you can upload a PDF solution directly to gradescope. Please be sure that your paper/PDF is legible!
Part 2 is due on Monday, 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, and answer some questions.

First, identify the base case and recursive case.
Second, draw the stack diagram for each of the programs, showing all the stack frames prior to the first time the program reaches a return statement.
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
    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:

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 prior to the first time the program reaches a return statement.
Third, show all program output when the full program is run.

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
13
14 def show(phrase):
    if len(phrase) == 0:
        print("!")
        return
    else:
        print(phrase[0])
        show(phrase[1:])
        return

def main():
    text = "Snow"
    show(text)

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
14 def mystery(a, b):
    if b == 0:
        return a
    else:
        r = 1
        p = mystery(a, b - 1)
        r = r + p
        return r

def main():
    v = mystery(2, 3)
    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
12
13
14
15
16
17 def helper(lst):
    if lst == []:
        return 0

    r = helper(lst[1:])

    if lst[0] < 0:
        r = r + 1
    
    return r
        

def main():
    ans = helper([1, -2, 3, -4])
    print(ans)

main()

2. Designing Recursive Functions

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

As you write programs, use good programming practices:

Use a comment at the top of the file to describe the purpose of the program (see example).
All programs should have a main() function (see example).
Use variable names that describe the contents of the variables.
Write your programs incrementally and test them as you go. This is really crucial to success: don’t write lots of code and then test it all at once! Write a little code, make sure it works, then add some more and test it again.
Don’t assume that if your program passes the sample tests we provide that it is completely correct. Come up with your own test cases and verify that the program is producing the right output on them.
Avoid writing any lines of code that exceed 80 columns.
- Always work in a terminal window that is 80 characters wide (resize it to be this wide)
- In vscode, at the bottom right in the window, there is an indication of both the line and the column of the cursor.

Function Comments

All functions should have a top-level comment! Please see our function example page if you are confused about writing function comments.

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. Sum odds

Write a recursive function called sum_odds(n) that computes the sum of the odd numbers from 1 to n, inclusive. You can assume that n is a non-negative integer. Write your solution in sum_odds.py Be sure that your solution includes a main function that tests your sum_odds function with a few different parameter values.

Your solution must be recursive.

def sum_odds(n):
    """
    This function sums the odd numbers from 1 to n, inclusive.

    Args:
        n (int): a non-negative integer

    Returns:
        int: the sum of the odd numbers from 1 to n, inclusive
    """

Here are some sample calls to sum_odds and their results:

sum_odds(0) ==> 0

sum_odds(1) ==> 1

sum_odds(5) ==> 9 (since 1 + 3 +  5 = 9)

sum_odds(6) ==> 9 (since 1 + 3 +  5 = 9 and 6 is even)

You should write a main function that makes at least two calls to sum_odds to test your solution. Be sure to print out the results of your calls to sum_odds.

For example:

def main():
    # test the base case
    n = 0
    result = sum_odds(n)
    print("sum_odds(%d) = %d" % (n, result))

    # test a recursive case
    n = 6
    result = sum_odds(n)
    print("sum_odds(%d) = %d" % (n, result))

    # test some other cases to be sure they work

main()

2.2. print_tower

Write a function called print_tower(n, ch) that prints a tower with n rows, using the character ch.

Your solution must be recursive.

For example:

print_tower(5, "*")
*
**
***
****
*****


print_tower(4, "~")
~
~~
~~~
~~~~


print_tower(1, "+")
+

print_tower(0, "$")
             <- NOTE: there is no output when n is 0

def print_tower(n, ch):
    """
    Prints a tower of the symbol ch with the base size of n.
    **You can assume n is greater than or equal to zero.**

    Args:
        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:
        Nothing, but prints a tower of n rows using the character ch
   """

Be sure to write a main function similar to what you did for your sum_odds function. Note that the print_tower function does not return a value.

2.3. Count letters

Write a function called count_letters(text) that a string text and returns the number of letters in the text. You may use the isalpha() method to determine if a character is a letter.

Your solution must be recursive.

def count_letters(txt):
    """
    This function returns a count of how many characters in txt are letters.

    Args:
       txt (str): a string of txt

    Returns:
         the number of letters in txt (int)
    """

For example:

count_letters("hello") ==> 5

count_letters("123") ==> 0

count_letters("test: hello 123") ==> 9

Be sure to write a main function similar to what you did for your sum_odds function.

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 to a a smaller version of the problem
Your function should correctly solve the problem
Your main function should make at least two calls to the recursive function in your main function to test your solution.

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!