## 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:

### 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
12def 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
12def 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
13def 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
11def 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.

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

 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```