CS21 Lab 10: Recursion

  • Part 1 is due on Monday, 22 April at the start of class. You must submit Part 1 on paper. Be sure that your paper is legible!

  • Part 2 is due on Saturday, 20 April, 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 three recursive functions. For each function, complete the following steps on paper.

  1. Identify the base case and recursive case.

  2. Trace the programs, and drawing the stack diagrams right up until the you reach the first return statement. Do not erase stack frames as you go along.

  3. Write down the final output of the program.

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

  1. Base case: when n <= 1

  2. Recursive case(s): when n > 1

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

    example stack

  4. The final output of this program is:

    Output:
24

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 main():
    show("hello", 2)

def show(msg, n):
    if n == 0:
        print("done")
        #draw stack here
        return
    else:
        print("%d: %s" % (n, msg))
        show(msg,n-1)
        print("%d: %s" % (n, msg))

main()

Program 2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def main():
    v = mystery(4, 3)
    print(v)

def mystery(a, b):
    if b == 0:
        ans = a
        #draw stack here
        return ans
    elif b > 0:
        ans = mystery(a-1, b-1)
    else:
        ans = mystery(a+1, b+1)
    return ans

main()

Program 3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def main():

	w = "cs21"
	result = puzzle(w, 0)
	print(result)

def puzzle(s, i):

	if i == len(s):
		val = "*"
        #draw stack here
		return val

	part = puzzle(s, i+1)
	ans = "*" + s[i] + part
	print(ans)
	return ans

main()

2. Designing Recursive Functions

Getting and Working on Lab10 Code

Make sure you are working in the correct directory when you edit and run lab 10 files.

Run update21 to get the starting point code of the next lab assignment. This will create a new ~/cs21/labs/10 directory for your lab work. Edit and run Lab 10 programs from within your cs21/labs/10 directory.

Make sure all programs are saved to your cs21/labs/10 directory! Files outside that directory will not be graded.

$ update21
$ cd ~/cs21/labs/10
$ pwd
/home/username/cs21/labs/10
$ ls
(should see your program files here)

Then edit and run program files in your ~/cs21/labs/10 directory:

$ code filename.py
$ python3 filename.py

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. Add evens

In the file add_evens.py, write a recursive function called add_evens(n) that takes a non-negative integer n as its only parameter and returns the sum of all the even numbers from 2 to n, inclusive.

Be sure that your solution includes a main function that tests your add_evens function with a few different parameter values.

Your solution must be recursive.

def add_evens(n):
    """
    Compute the sum of all even numbers from 2 to n

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

    Returns:
        int: the sum of the _even_ numbers up to and including n
    """

For example:

print(add_evens(0)) #0
print(add_evens(1)) #0
print(add_evens(2)) #2
print(add_evens(10)) #2+4+6+8+10 = 30

Hint: You can use the modulo operator % to determine if a number is even. For example, n % 2 == 0 is True if n is even.

2.2. Contains

In the file contains.py write a recursive function called contains(lst, val, pos) that takes a list lst of integers, an integer value val, and an integer position pos as its parameters and returns True if lst contains the value val at or beyond index pos. Return False otherwise. Your solution must be recursive and cannot use loops, the .index() method, or the in operator.

print(contains([1,9,0,8,1], 1, 0)) #True
print(contains([1,9,0,8,1], 2, 0)) #False
print(contains([1,9,0,8,1], 9, 2)) #False
print(contains([1,9,0,8,1], 9, 1)) #True
print(contains([1,9,0,8,1], 0, 0)) #True
def contains(lst, val, pos):
    """
    This function recursively checks if a lst contains a
     val at or beyond a given position

    Params:
        lst(list): a list of ints
        val(int): an integer value to search for
        pos(int): an integer indicating the starting position in lst

    Returns:
        bool: True if lst contains val at or beyond pos, False otherwise
    """

2.3. Ascii ruler

A typical ruler/tape measure has a series of marks of various lengths at regular intervals. For example, a ruler might have a long mark at every inch and a shorter mark at every half inch, and an even shorter mark every quarter inch. In the file ruler.py add a recursive function called ruler(n) that takes a non-negative integer n as its only parameter and prints an ASCII ruler according to the following rules:

  1. A ruler for n=0 has no marks.

  2. A ruler of n=1 has a single mark. You can print a single hyphen - to represent the mark.

  3. For a ruler of length n, it contains in sequential order the following elements:

    1. A smaller size n-1 ruler

    2. A mark of length n dashes

    3. A a second smaller size n-1 ruler

For example, a ruler for n=2 would look like this:

-
--
-

A ruler for n=3 would look like this:

-
--
-
---
-
--
-

Can you identify the two n=2 ruler patterns in the n=3 ruler example? Your recursive function should not return anything. It should print the ruler directly to the screen.

def ruler(n):
    """
    This function recursively prints an ASCII ruler of size n

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


    Returns:
        None
    """

A ruler for n=5 would look like this:

-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
-----
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-

2.4. Removing upper case letters

In the file remove_upper.py write a function called remove_upper(s, n) that takes a string s as its first parameter and an integer n as its second parameter. The function should return a new string that starts at position n in s and with any uppercase letters in position n or later removed. The function must be recursive.

For example:

print(remove_upper("Hello", 0)) # ello
print(remove_upper("Hello", 2)) # llo
print(remove_upper("", 0)) # empty string
print(remove_upper("WOW", 0)) # empty string
print(remove_upper("SweeT!", 0)) #wee!

Hints:

  • You can use the ch.isupper() method to determine if a character ch is uppercase.

  • Both the recursive and base cases must return a string. You can construct a new string ans by concatenating strings together. For example, ans = s1 + s2 creates a new string ans that is the concatenation of strings s1 and s2.

def remove_upper(s, n):
    """
    Create a new string that removes
      all uppercase letters from the string s starting at position n

    If n is >= the length of s or <0, return an empty string

    Params:
        s(str): a string
        n(int): an integer indicating the starting position in s

    Returns:

        (str) a new string with no uppercase letters.
    """

3. 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 (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!