Recursion &

Tree Recursion

annietang@berkeley.edu�anniewtang.github.io/cs61a

links.cs61a.org/annie-disc

Announcements

• links.cs61a.org/annie-disc
• sign up for CSM! @Piazza for details
• homework 3 is due next week

​

Agenda

1. Recursion
2. Tree Recursion

Recursion

The Setup & The Solution(s)

Iterative Solution

• ask a friend to go to the front of the line
• while they haven’t reached me yet, ask them to count the number of people (one by one)
• when they get to me, tell me the number of people!

Situation

• you’re waiting in line to shake dan’s hand
• you can’t see the front of the line (bc it’s so long), but you want to know what your place in line is
• you can’t leave the line to count yourself, bc you’d lose your spot
• now what :,(

The Setup & The Solution(s)

Situation

• you’re waiting in line to shake dan’s hand
• you can’t see the front of the line (bc it’s so long), but you want to know what your place in line is
• you can’t leave the line to count yourself, bc you’d lose your spot
• now what :,(

Recursive Solution

• if you’re at the front, you know you’re number one!
• otherwise, if not, just ask the person in front of you: “hey fam what number in line r u”
• then all we gotta do is add one to the number given to us by that person

how can we implement this in code?

write a function: factorial(n)

Functional Abstraction

• the idea where you don’t need to care about how a function is implemented, just what it does!
• abstract away the details — only care about the end result/behavior of the function!
• this is the basis behind the “recursive leap of faith”
• know what the function takes in
• know what the function outputs
• and decide how you want to use this output to achieve your goal

understanding the domain & range of a function

The Three Steps to Recursion

1. Write down your base case
2. Break down your problem into a smaller case, �using recursion!
3. Use this recursive call to solve the main problem!

(classic)

step 1:

the base case

How does one choose a base case?

• the simplest or smallest argument/input that could be initially passed into your function
• the immediate “success” or “failure” cases
• inputs that would cause your function to stop when first passed in
• usually related to the first bullet point
• just another way of thinking about it!
• if it’s unclear what your base case should return try starting from the recursive call to figure out base case
• more on next slide

consider the following scenarios!

Starting from the recursive call

• i.e. count_partitions
• what happens if m = 0? n = 0?
• not super intuitive if we use the “from the start” perspective
• one thing to notice (after getting the overall recursive call/structure) is that we’re decrementing m and n each time we make a recursive call
• if the variables we’re changing are m and n, then we need to let our function know at what point do we want to stop changing m and n?
• use the logic we applied to get the recursive call to determine what the “stopping” points & results are for m & n in this function
• this becomes some of our base cases!

for non-intuitive base cases

step 2:

use recursion to solve the smaller problem

tackling that “smaller” problem

• think about “one step/section away”
• i.e. you executed one choice or one part of your strategy — what’s left of the problem?

• if you tried to “write out” your steps, do u see a pattern?
• any repeated steps/strategies => use recursion to take care of it

• when making a recursive call on the “smaller” problem, think about what that call should be returning
• don’t think about how it will give you the result
• think about what the expected result is

step 3:

solve the main problem

using your recursive step

• using the “what should my recursive call be giving me” mindset, how can you use that expected return value to solve the problem at hand?
• don’t get caught up in the details for the recursive call
• ex: when solving factorial(5), don’t think about how your function will give you factorial(4)
• this will lead you to think how you would solve factorial(3) and factorial(2) and .... you get stuck in a rabbit hole
• instead, think about how you would how you can use the result of factorial(4) to get factorial(5)

factorial(5)�= 5 * 4 * 3 * 2 * 1�= 5 * factorial(4)

Tree Recursion

Tree Recursion (overview)

Tree recursion ⇒ Recursion by cases.

Let’s say you’re trying to solve a problem using recursion, and while doing so you realize:

• there are multiple situations/paths/cases to consider
• you need to combine the results of these multiple situations to get the final result
• multiple recursive calls → tree recursion

NOTE:

Later when we learn about “Trees” (an abstract data type), you’ll see us applying recursion on trees.

​

Our recursive strategy on trees oftentimes uses tree recursion

Overall, recursion takes a lot of practice to get used to!

so don’t worry if you find it difficult in the beginning :)