Discussion 3

Recursion and Tree Recursion

Antonio Kam
anto [at] berkeley [dot] edu

Announcements

  • Lab 2 due today (2022/06/30)
  • HW 1 due today (2022/06/30)
  • Hog Checkpoint due tomorrow (2022/07/01)
    • Finish all of Phase 1 (all autograder tests passing) by then to get checkpoint credit
  • My office hours are 1-2 PM Tuesdays and 3-5 PM Wednesdays
  • I won't be in Berkeley from July 6th to July 11th (there will still be section at this time; you'll just have someone covering for me!)
    • Attendance will still work even if you don't use the same form
Slides by Antonio Kam (anto@)

Temperature Check 🌡️

  • Recursion
  • Tree Recursion
Slides by Antonio Kam (anto@)

Results from last section

Slides by Antonio Kam (anto@)

Questions and Comments from last section

  • Mini-lectures in the middle of labs are good!
    • Will continue to do this for future labs 😎
  • I think the consensus is that a hybrid of whiteboarding and using slides is a pretty good option
    • I'll do a mix with more focus on whiteboarding from here on
Slides by Antonio Kam (anto@)

All slides can be found on
teaching.rouxl.es

Slides by Antonio Kam (anto@)

What is recursion?

  • A recursive function is one where a function is defined in terms of itself.
  • Similar to higher-order functions except it returns a call to a function rather than the function itself
  • Will be hearing me talk about this a lot: recursive leap of faith
Slides by Antonio Kam (anto@)

3 Steps of Recursion

  1. Base Case
    • What is the smallest version of the problem we know the answer to?
    • I tend to think of this as the simplest input
  2. Recursive Case (recursive call on a smaller version of the problem)
    • What can I do to reduce my input to something simpler?
    • Similar to while loops
  3. Connecting it all together
    • Assuming your recursive call is correct (recursive leap of faith!), how do you solve the real problem
Slides by Antonio Kam (anto@)

Example

def factorial(n):
    if n == 0 or n == 1: # Base Case
        return 1
    else: # Recursive Case
        return n * factorial(n - 1)
Slides by Antonio Kam (anto@)

Example

  • To calculate a factorial of an integer, what you do is multiply the integer itself with the factorial of one less than itself
    • factorial(5) = 5 * factorial(4)
  • Notice the recursive pattern - factorial(4) will call factorial(3), and so on and so forth, until our base case is reached.
  • We know the result of factorial(1), so calling factorial(1) will just return 1 (base case)
Slides by Antonio Kam (anto@)

Example (Another Perspective)

  • What's the smallest input? What's the simplest problem I know the answer to?
    • 0 is the smallest input - factorial(0) also returns 1.
  • How can I reduce my problem?
    • If you have factorial(n), you can reduce your problem down by calling factorial(n - 1).
    • In this step, you also assume your reduced problem gives you the correct answer (so factorial(n - 1) gives you the correct result - which is the recursive leap of faith)
  • How do I use that result to solve my problem?
    • Multiply by n
    • n * factorial(n - 1)
Slides by Antonio Kam (anto@)

Recursion vs Iteration

Recursion Iteration
Base case is needed for a recursive problem A condition for a while loop is needed
Need to reduce down to the base case Need to reduce down to the while condition
Can't use variables to keep track of values because they reset (need a helper function for that) Can have variables to keep track of values.
Needs lots of frames - takes up memory Loops happen in 1 frame
Slides by Antonio Kam (anto@)

Recursion vs Iteration

# Recursion
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

# Iteration
def factorial(n):
    result = 1
    while n > 0:
        result = result * n
        n -= 1
    return result
Slides by Antonio Kam (anto@)

Question 1 (Walkthrough)

Write a function that takes two numbers m and n and returns their product. Assume m and n are positive integers. Use recursion!

Hint: 5 * 3 = 5 + (5 * 2) = 5 + 5 + (5 * 1).

def multiply(m, n):
    """ Takes two positive integers and returns their product using recursion.
    >>> multiply(5, 3)
    15
    """
    "*** YOUR CODE HERE ***"
Slides by Antonio Kam (anto@)

Question 1

Write a function that takes two numbers m and n and returns their product. Assume m and n are positive integers. Use recursion!

def multiply(m, n):
    """ Takes two positive integers and returns their product using recursion.
    >>> multiply(5, 3)
    15
    """
    if n == 1: # Base case
        return m
    else:
        return m + multiply(m, n - 1) # Reducing case down
Slides by Antonio Kam (anto@)

Question 2 (10 minutes)

Draw an environment diagram for the following code:

def rec(x, y):
    if y > 0:
        return x * rec(x, y - 1)
    return 1

rec(3, 2)
Slides by Antonio Kam (anto@)

Question 3

Find the bug with this recursive function.

def skip_mul(n):
    """Return the product of n * (n - 2) * (n - 4) * ...

    >>> skip_mul(5) # 5 * 3 * 1
    15
    >>> skip_mul(8) # 8 * 6 * 4 * 2
    384
    """
    if n == 2:
        return 2
    else:
        return n * skip_mul(n - 2)
Slides by Antonio Kam (anto@)

Question 3

Find the bug with this recursive function.

def skip_mul(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    else:
        return n * skip_mul(n - 2)
Slides by Antonio Kam (anto@)

Question 5 (10 minutes)

Write a procedure merge(n1, n2) which takes numbers with digits in decreasing order and returns a single number with all the digits of the two, in decreasing order. Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.

def merge(n1, n2):
    """ Merges two numbers by digit in decreasing order
    >>> merge(31, 42)
    4321
    >>> merge(21, 0)
    21
    >>> merge (21, 31) 
    3211
    """
    "*** YOUR CODE HERE ***"
Slides by Antonio Kam (anto@)

Question 5

Write a procedure merge(n1, n2) which takes numbers with digits in decreasing order and returns a single number with all the digits of the two, in decreasing order. Any number merged with 0 will be that number (treat 0 as having no digits). Use recursion.

def merge(n1, n2):
    if n1 == 0:
      return n2
    if n2 == 0:
      return n1
    elif n1 % 10 < n2 % 10:
      return n1 % 10 + 10 * merge(n1 // 10, n2)
    else:
      return n2 % 10 + 10 * merge(n1, n2 // 10)
Slides by Antonio Kam (anto@)

Question 6 (10 minutes)

Write a function is_prime that takes a single argument n and returns True if n is a prime number and False otherwise. Assume n > 1. Use recursion. (Hint: You will need a helper function)

def is_prime(n):
    """Returns True if n is a prime number and False otherwise.
    >>> is_prime(2)
    True
    >>> is_prime(16)
    False
    >>> is_prime(521)
    True
    """
    "*** YOUR CODE HERE ***"
Slides by Antonio Kam (anto@)

Question 6

Write a function is_prime that takes a single argument n and returns True if n is a prime number and False otherwise. Assume n > 1. Use recursion. (Hint: You will need a helper function)

def is_prime(n):
    def helper(i):
        if i > (n ** 0.5):
            return True
        elif n % i == 0:
            return False
        return helper(i + 1)
    return helper(2)
Slides by Antonio Kam (anto@)

Question 4 (10 minutes)

Recall the hailstone function from Homework 2. First, pick a positive integer n as the start. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process until n is 1. Write a recursive version of hailstone that prints out the values of the sequence and returns the number of steps.

def hailstone(n):
    """Print out the hailstone sequence starting at n, and return the number of elements in the sequence.
    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    """
    "*** YOUR CODE HERE ***"
Slides by Antonio Kam (anto@)

Question 4

def hailstone(n):
    print(n)
    if n == 1:
      return 1
    if n % 2 == 0:
      return 1 + hailstone(n // 2)
    else:
      return 1 + hailstone(n * 3 + 1)
Slides by Antonio Kam (anto@)

Attendance
links.rouxl.es/disc

Slides by Antonio Kam (anto@)

Tree Recursion 🎄

Slides by Antonio Kam (anto@)

Tree Recursion

  • Tree recursion is recursion but with two (or more!) recursive calls
  • Useful when you need to break down a problem in more than 1 way
  • Useful when there are multiple choices to deal with at one function call
  • The recursive call diagram will expand similar to the roots of a tree
Slides by Antonio Kam (anto@)

Example 1: Recursive Fibonacci

def fib(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    return fib(n - 1) + fib(n - 2)
  • Notice how this still follows the rules of recursion
    • We have base case(s)
    • We reduce our problem (fib(n - 1) and fib(n - 2))
    • We connect it together (with +)
  • Often you combine things with +, -, *, / or some other function (max, min, etc).
Slides by Antonio Kam (anto@)

Example 1: Recursive Fibonacci

You can also write down

def fib(n):
  if n == 0 or n == 1:
    return n
  else:
    return fib(n - 1) + fib(n - 2)
Slides by Antonio Kam (anto@)

Mental Health Resources

  • CAPS:
    • If you need to talk to a professional, please call CAPS at 510-642-9494.
  • After Hours Assistance
    • For any assistance after hours, details on what to do can be found at this link
Slides by Antonio Kam (anto@)

Anonymous Feedback Form
links.rouxl.es/feedback

Thanks for coming! 🥳

Please give me feedback on what to improve!

Slides by Antonio Kam (anto@)

Draw recursive call diagram (not the environment diagram version)

By discuss I mean as a whole group, not in small groups