## Quiz 6 Study Guide

You are responsible for all material covered through the end of Week 13 (Classes and Objects).

In addition to all concepts from Quiz 5, you should understand the following:

### Python concepts

• Recursion

• base case

• recursive call

• recursion on numbers, strings, and lists

• recursion vs iteration

• Writing Classes

• the `self` parameter

• defining and calling methods

• initializing and using member variables

• constructors (`__init__()`)

• to-string (`__str__()`)

### You should be able to

• trace the execution of a recursive function

• write a recursive function that takes a number, string or list as a parameter

• write new methods to add functionality to a class

### Practice problems

1. What would the output of the following code be?

``````def mystery(n):
if n == 1:
# Draw stack here
return 0
else:
return 1 + mystery(n//2)

def main():
result = mystery(11)
print("Result: %d" % (result))

main()``````

Draw a stack diagram to show the contents of the stack just before returning from the base case.

2. Given the code below:

``````def unknown(lst, idx):
if (idx >= (len(lst) - 1)):
return True
elif lst[idx] > lst[idx + 1]:
return False
else:
return unknown(lst, idx + 1)

def main():
result = unknown([3, 5, 7, 1], 0)
print("Result:", result)

main()``````
• What is the return type of the recursive function?

• What is the base case(s)?

• What is the recursive step(s)?

• What is the output of the program show above?

• Provide another list (instead of `[3, 5, 7, 1]`) with the same length that gives a different output.

• What does the `unknown` function do, and what would be a better name for this function?

3. Write two versions of each of the following functions…​one version using iteration and one using recursion:

• sum all values in a given list of integers

• return True if a list is sorted/in order, False if not

• count/return how many times a given value (v) is found in a list (L)

• find the largest number in a list

4. Draw a stack diagram for the following program. Show what the stack would look like at it’s largest point (i.e. just before the `return` statement in the base case). Then write down the complete output of the program (i.e. when `main` is done running).

``````def main():
n = 5
ans = factorial(n)
print(ans)

def factorial(x):
if x == 0:
return 1
else:
return x * factorial(x-1)

main()``````
5. Write a recursive function, `insert_many`, that takes a string, a character, and a number and returns a new string with the character inserted between every letter of the original string and repeated the given number of times. For example:

``````insert_many('swat','x', 3) => 'sxxxwxxxaxxxt'
insert_many('hello','!', 0) => 'hello'
insert_many('cs21', '!', 2) => 'c!!s!!2!!1'``````
6. Consider the `StudentRecord` class we used for in-class exercises (code below); for each of the following features, modify both the class and the main program as instructed.

• Academic concern: write a method that returns `True` if a student’s GPA is below 2.0, then write a function that applies this method to each student in a list, printing out their name if the method returns true.

• Graduating year: add a member variable to the class to store the year a student will graduate (e.g. 2022); modify the constructor to take an additional argument, then write getter and setter methods for this new field. Next, write a method called `years_left()` that takes in the current year as a parameter, and returns the number of years remaining before a student graduates (e.g. if the student should graduate in 2024 and the method is passed 2022, it should return 2). Write some code to test out this new functionality.

``````
class StudentRecord(object):
"""
Remember, the body of an object must all be indented to the same level, just
like the body of any other block of Python code
"""

def __init__(self, name, age, major, gpa):
"""
Constructor; parameters are initial values for:
name (string), age (int), major (string), gpa (float)
"""
# initialize several member variables with parameter values
self.name = name
self.age = age
self.major = major
self.gpa = gpa
# initialize an empty list to store student's grades

##########################
"""
Getter methods; each returns the value of the appropriate member variable
"""

def get_name(self):
""" Getter method for name
- no parameters beyond 'self'
- returns value of "name" field
"""
return self.name

def get_age(self):
""" Getter method for age
- no parameters beyond 'self'
- returns value of "age" field
"""
return self.age

def get_major(self):
""" Getter method for major
- no parameters beyond 'self'
- returns value of "major" field
"""
return self.major

def get_gpa(self):
""" Getter method for gpa
- no parameters beyond 'self'
- returns value of "gpa" field
"""
return self.gpa

""" Getter method for grades
- no parameters beyond 'self'
- returns value of "grades" field
"""

##########################
"""
Setter methods; each modifies the value of the appropriate member variable
"""

def set_name(self, newName):
""" Setter method for name
- takes a new value for the 'name' field
- no return value
"""
self.name = newName

def set_major(self, newMajor):
""" Setter method for major; must be in list of options
- takes a new value for the 'major' field
- no return value
"""
validMajors = ["CS", "Math", "English", "Philosophy"]
if (newMajor in validMajors):
self.major = newMajor
else:
print("Warning; trying to set invalid major: \"%s\"" % (newMajor))

def set_age(self, newAge):
""" Setter method for age
- takes a new value for the 'age' field
- no return value
"""
if (age >= 0):
self.age = newAge
else:
print("Warning; age must not be negative")

##########################
"""
Modifier methods change values of members, but don't directly assign
new values to them
"""

""" modifier method for list of grades
- takes a new grade to add to list
- no return value
"""

def birthday(self):
"""
Method to run if it's a student's birthday; print a message and
increment the student's age.
No parameters or return value.
"""
print("Happy birthday, %s!", (self.name))
self.age = self.age + 1

def update_gpa(self):
"""
Method to re-calculate GPA based on list of grades
No parameters or return value.
"""
total = 0
for i in range(len(self.grades)):
total = total + self.grades[i]

self.gpa = total / len(self.grades)

##########################

def __str__(self):
"""
to-string method, returns a string containing info about the student
No parameters
returns string
"""
return "%-12s (age: %d,   major: %s, \tgpa: %.2f)" % \
(self.name, self.age, self.major, self.gpa)

##########################
# End of class definition
##########################

def main():
"""
main function for testing the class
"""

print("Running tests for StudentRecord class...")

print("Testing constructor...")
beth = StudentRecord("Beth", 19, "Math", 3.8)
cal = StudentRecord("Cal", 20, "English", 3.4)

slst = [ada, beth, cal]
print("Testing to-string...")
for s in slst:
print(s)

print("Testing getter methods...")

print("testing grade list methods...")