Berkeley Time!

+ 10 minutes

1

give me song recz: links.larynqi.com/recz

Discussion 03:

Recursion

​

February 10, 2022

Laryn Qi – larynqi@berkeley.edu – Lab 115L, 134L – Disc 134, 125

Announcements

• MT1 grades released! Check Gradescope
• MT1 regrade requests due Wednesday 2/16 @ 11:59 PM
• Join a CSM section for extra weekly practice - see Piazza
• Advising appointments
• Good way to talk about how the exam went for you and roadmap a study strategy for the rest of the semester with staff
• Lost and found at Soda Front Desk (Weekdays 8-noon, 1-4 PM)
• MT2 on March 17th has been rescheduled to 8-10 PM (instead of 7-9 PM)
• Hog due tonight @ 11:59 PM

​

• Website/slides can be found on TA page or links.cs61a.org/laryn

Laryn Qi

Let’s talk about the midterm...

Point breakdown for CS 61A (from syllabus)

• Midterm 1, worth 40 points.
• Midterm 2, worth 50 points.
• The final exam, worth 75 points.
• Four projects, worth 99 points.
• Homework, worth 16 points.
• Lab, worth 10 points.
• Participation, worth 10 points (5 lab, 5 discussion).

Read: 135 points in this class come from assignments/participation, 165 come from exams

If you get full credit on all non-exam stuff, you’d need:

• Average ~24% on exams to get a C- (pass the class if taking PNP)
• Average ~70% on exams to get a B+ (3.3 GPA)

​

Reassurances

• Most of the points in this class are still to come—how you did on MT 1 does not set your fate for the entire class
• Also, how well you do in 61A does not alone make-or-break whether you can be a CS major
• Folks tend to do approx 1 grade bin better in 61B than in 61A!
• And even more critically, your grade on the exam is not a judgement on your worth or skill as a programmer or computer scientist
• If you did great, awesome! But if you didn’t you are still perfectly capable of succeeding in industry
• Also if you enrolled in a CSM section awesome and if you didn’t I highly encourage it!!
• We’ve found that typically folks who enroll in CSM sections after MT 1 tend to do better on MT 2 and the final
• If you felt like this midterm was “easy” that does not necessarily mean that we’re going to make the other exams “harder” just to compensate
• Tutoring: https://upe.berkeley.edu/, https://hkn.eecs.berkeley.edu/

Agenda

• Recursion
• Tree Recursion
• Lists

Laryn Qi

Recursion

Laryn Qi

Recursion

• A recursive function is a function that calls itself
• Way of solving big but repetitive problems
• Analogy from lecture: how far am I from the front of the line

Laryn Qi

Recursion

• Base Case: the simplest possible case(s) where we can determine the answer immediately
1. The first person in line knows that they are the first one in line
• No/improper base case → Traceback (most recent call last): ...

RecursionError: maximum recursion depth exceeded

Laryn Qi

Recursion

• Recursive call: make a call to itself with simpler arguments that trend toward base case(s)
• Ask the person in front of you
• Trust that they tell the truth (recursive leap of faith)!!

​

• Recombination: combine the result of the recursive call to get your final answer
• Add 1 to the answer the person gave you

Laryn Qi

Putting it all together

def factorial(n):

if n == 0 or n == 1:

return 1 # base case

else:

return n * factorial(n - 1)

Arms-length recursion

def factorial(n):

if n == 0 or n == 1:

return 1 # base case

else:

return n * (n - 1) * factorial(n - 2) # AHHHHHHHHH

Question 2:

Recursion ED

Laryn Qi

Question 1:

multiply

Laryn Qi

Q1 Multiply

Things to think about

• What does each input (m, n) represent?
• What is the simplest case that I know the answer to?
• How do I make the problem one step simpler/one step closer to my base case(s)?

Laryn Qi

Question 3:

Find the Bug

Laryn Qi

Question 4:

hailstone

Laryn Qi

Question 5:

merge

Laryn Qi

Helper Functions

• Functions that are defined inside usually a recursive function to help the outer function run
• Reasons why we use helpers in recursion:
• If the problem needs to keep track of extra info → define new parameters
• With helpers, all the outer function needs to do is call the helper with the proper initial values

Laryn Qi

Question 6:

is_prime

Laryn Qi

Tree Recursion

Laryn Qi

Tree Recursion

• A recursive function that makes more than one recursive call
• In essence, it’s still recursion → trying to break one complex problem into smaller subproblems
• Trend toward a base case
• Recursion follows a linear path toward the base case(s)
• Tree Recursion considers and explores multiple paths at each step (multiple subproblems)

Laryn Qi

Example: Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• The kth element of the fib sequence is defined as the sum of the k-1th element with the k-2nd element
• Recursive definition:
• fib(k) = fib(k - 1) + fib(k - 2)
1. Assumes that fib(k - 1) and fib(k - 2) return the correct values, then just adds them
• Base case:
• fib(0) = 0, fib(1) = 1

Laryn Qi

Example: Count Partitions

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• The kth element of the fib sequence is defined as the sum of the k-1th element with the k-2nd element
• Recursive definition:
• fib(k) = fib(k - 1) + fib(k - 2)
• Assumes that fib(k - 1) and fib(k - 2) return the correct values, then just adds them
• Base case:
• fib(0) = 0, fib(1) = 1

Laryn Qi

Tree Recursion Tips

1. Try simple inputs/doctests to formulate base cases
2. Visualize your function’s intended behavior
1. Draw out a test case
2. How can I break my problem into subproblems?
3. What possible paths/options do I have to consider at each step?
4. Recursive leap of faith
3. Is there anything I need to keep track of throughout all recursive calls (helper)?
4. Remain consistent among all return types
• For path counting problems, usually return 1/0
5. Check your work with edge cases

Laryn Qi

Question 2.1:

count_stair_ways

Laryn Qi

Question 2.2:

count_k

Laryn Qi

Lists

Laryn Qi

Lists

• An ordered collection of any data type
• The following are all valid lists:
• [1, 2, 3]
• [‘hi’, ‘nice’, ‘to’, ‘meet’, ‘you’]
• [True, False, False]
• [[1, 2], [3]]
• [1, ‘hi’, True, [1, 2]]

Laryn Qi

List Examples

Basics

Slicing

lst[start:stop:step]

Laryn Qi

>>> lst = [1, 2, 3]

>>> lst[0]

1

>>> lst[2]

3

>>> lst[-1]

3

>>> lst[3]

ERROR

>>> len(lst)

3

>>> lst = [2, 0, 6, -1, 7]

>>> lst[1:4]

[0, 6, -1]

>>> lst[0:3:2]

[2, 6]

>>> lst[3:]

[-1, 7]

>>> lst[:]

[2, 0, 6, -1, 7]

>>> lst[10:]

[]

​

​

For Loops

• Very similar to while loops
• Great for iterating through the elements of a sequence or when given fixed sized inputs

Laryn Qi

def while_print_lst(lst):

index = 0

while index < len(lst):

print(lst[index])

index += 1

def for_print_lst(lst):

for elem in lst:

print(elem)

List Comprehensions

• Compact way to create a list whose elements are the results of applying a fixed expression to elements in another sequence

Laryn Qi

List Comprehensions

• Compact way to create a list

Laryn Qi

result = []

for elem in lst:

if elem > 3:

result = result + [elem + 1]

result = [elem + 1 for elem in lst if elem > 3]

Question 3.2:

even_weighted

Laryn Qi

Thanks for coming!

​

Attendance: links.larynqi.com/attendance

Secret Phrase: asha

35

Laryn Qi

Resources

​

​

Laryn Qi