CS21 Lab 10: Recursion

Due Monday, November 28.

Part 1 will be turned in at the start of class, on paper
Part 2 using handin21

Goals

The goals for this lab assignment are:

Trace recursive functions
Design recursive functions
Identify 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 the program output and drawing the stack diagrams.

Example Solution

Use the following template:

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

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

main()

Base case:
n <= 1


Recursive case:
n > 1


Stack Diagram:
+----------------+
|                |
| fact      n -----> 1
|                |
+----------------+
|                |
| fact      n -----> 2
|                |
|           f -----> 2
|                |
+----------------+
|                |
| fact      n -----> 3
|                |
|           f -----> 6
|                |
+----------------+
|                |
| fact      n -----> 4
|                |
|           f -----> 24
|                |   ^
+----------------+   |
|                |   |
| main      v---------
|                |
+----------------+


Output:
24

Program 1

def f(lst):
   if len(lst) > 0:
       print(lst[0])
       f(lst[1:])

def main():
  evens = [0, 2, 4, 6]
  f(evens)

Program 2

def b(x):
   if x <= 1:
      print(x)
   else:
      b(x // 2)
      print(x % 2)

def main():
    b(11)
main()

Program 3

def m(a, b):
   if b == 0:
       return 0
   else:
       v = m(a, b - 1)
       return a + v

def main():
    v = m(3, 5)
    print(v)

main()

Program 4

def n(a, b):
    if b == 0:
        return 0
    elif (b % 2) == 0:
        v = n(a + a, b // 2)
        return v
    else:
        v = n(a + a, b // 2)
        return v + a

def main():
    v = n(3, 5)
    print(v)

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. Vowels

Write a recursive function vowels that replaces all the vowels of the string with *. Put your solution in vowels.py in the labs/10 directory.

def vowels(s):
   ''' return a version of s, where all vowels are replaced with '*' '''

$ python3 -i vowels.py
>>> vowels("")
""
>>> vowels("a")
"*"
>>> vowels("cat")
"c*t"
>>> vowels("vowels")
"v*w*ls"

2.2. Linear Search

Rewrite search to use recursion instead of a for loop. Put your solution in search.py in the labs/10 directory.


def search(key, lst):
   ''' return True if v exists in the list provided, False otherwise '''
    for v in lst:
        if key == v:
       	    return True
    return False

$ python3 -i search.py
>>> search("cat", [])
False
>>> search("cat", ["cat"])
True
>>> search("cat", ["cat", "dog", "fish"])
True
>>> search("zebra", ["cat", "dog", "fish"])
False