Discussion 4: Tree Recursion

IMPORTANT! Add your email address and then press "Join Group" above!

Attendance

Your TA will come around during discussion to check you in. You can start on the worksheet before being checked in; you don't need to wait for your TA to get started.

If you didn't attend for a good reason (such as being sick), fill out this form (within 2 weeks of your discussion): attendance form

If you get stuck, there are walkthrough videos (@berkeley.edu login to YouTube required).

Getting Started

Say your name and your favorite tree (a particular tree or a kind of tree) in honor of today's topic: tree recursion.

Definition: Tree recursive functions are functions that call themselves more than once.

Recursion takes practice. Please don't get discouraged if you're struggling to write recursive functions. Instead, every time you do solve one (even with help or in a group), make note of what you had to realize to make progress. Students improve through practice and reflection.

VERY IMPORTANT: In this discussion, don't check your answers until your whole group is sure that the answer is right. Figure things out and check your work by thinking about what your code will do. Your goal should be to have all answers right the first time! If you need help, ask.

Tree Recursion

For the following questions, don't start trying to write code right away. Instead, start by describing the recursive case in words. Some examples:

• In fib from Section 1.7 of the textbook, the recursive case is to add together the previous two Fibonacci numbers.
• In skip_factorial from Discussion 3 (Q2), the recursive case is to multiply n by the skip factorial of n - 2.
• In count_partitions from Section 1.7 of the textbook, the recursive case is to partition n-m using parts up to size m and to partition n using parts up to size m-1.

Q1: Insect Combinatorics

An insect is inside an m by n grid. The insect starts at the bottom-left corner (1, 1) and wants to end up at the top-right corner (m, n). The insect can only move up or to the right. Write a function paths that takes the height and width of a grid and returns the number of paths the insect can take from the start to the end. (There is a closed-form solution to this problem, but try to answer it with recursion.)

In the 2 by 2 grid, the insect has two paths from the start to the end. In the 3 by 3 grid, the insect has six paths (only three are shown above).

Hint: What happens if the insect hits the upper or rightmost edge of the grid?

def paths(m: int, n: int) -> int:
    """Return the number of paths from one corner of an
    m by n grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """

Hint 1: Recursive Case (at the end)

Presentation Time: Once your group has converged on a solution, it's time to practice your ability to describe why your recursive case is correct. Nominate someone and have them present to the group for practice. If you want feedback, ask.

Tree Recursion with Lists

Some of you already know list operations that we haven't covered yet, such as append. Don't use those today. All you need are list literals (e.g., [1, 2, 3]), item selection (e.g., s[0]), list addition (e.g., [1] + [2, 3]), len (e.g., len(s)), slicing (e.g., s[1:]), for statements, range, and list comprehensions. Use those!

Important: The most important thing to remember about lists is that a non-empty list s can be split into its first element s[0] and the rest of the list s[1:]. Slicing works from other positions too: s[2:] is everything after the first two elements. Slicing past the end of a list never errors; it just gives [] (see the List Slicing review in Lab 3).

>>> s = [2, 3, 6, 4]
>>> s[0]
2
>>> s[1:]
[3, 6, 4]
>>> s[2:]
[6, 4]
>>> len(s)
4
>>> s[4:]
[]
>>> [][1:]
[]

Q2: Max Product

Implement max_product, which takes a list of integers and returns the maximum product that can be formed by multiplying together non-consecutive elements of the list. Assume that all numbers in the input list are greater than or equal to 1.

def max_product(s: list[int]) -> int:
    """Return the maximum product of non-consecutive elements of s.

    >>> max_product([10, 3, 1, 9, 2])   # 10 * 9
    90
    >>> max_product([5, 10, 5, 10, 5])  # 5 * 5 * 5
    125
    >>> max_product([5, 10, 5, 10, 5, 10]) # 10 * 10 * 10
    1000
    >>> max_product([])                 # The product of no numbers is 1
    1
    """

Hint 2 (at the end)

Hint 3: More Help (at the end)

Description Time: Now try to complete this sentence together: "The recursive case is to choose the larger of ___ and ___." When you're done, see how your answer compares to ours.

Hint 4: Answer (at the end)

Q3: Sum Fun

Implement sums(n, m), which takes a total n and maximum m. It returns a list of all lists:

1. that sum to n,
2. that contain only positive numbers up to m, and
3. in which no two adjacent numbers are the same.

Important: Two lists with the same numbers in a different order should both be returned.

Here's a recursive approach that matches the template below: build up the result list by building all lists that sum to n and start with k, for each k from 1 to m. For example, the result of sums(5, 3) is made up of three lists:

• [[1, 3, 1]] starts with 1,
• [[2, 1, 2], [2, 3]] start with 2, and
• [[3, 2]] starts with 3.

Hint: Use [k] + s for a number k and list s to build a list that starts with k and then has all the elements of s.

Important: The hint references that your recursion should build each list by deciding its first element and prepending it to the result of the recursive call on the rest ([k] + rest, not rest + [k]). Both are valid ways to solve the underlying problem, but only the [k] + rest order matches the order that our doctests below expect.

>>> k = 2
>>> s = [4, 3, 1]
>>> [k] + s
[2, 4, 3, 1]

Hint (first blank): k is the first number in a list that sums to n, and rest is the rest of that list, so build a list that sums to n.

def sums(n: int, m: int) -> list[list[int]]:
    """Return lists that sum to n containing positive numbers up to m that
    have no adjacent repeats.

    >>> sums(5, 1)
    []
    >>> sums(5, 2)
    [[2, 1, 2]]
    >>> sums(5, 3)
    [[1, 3, 1], [2, 1, 2], [2, 3], [3, 2]]
    >>> sums(5, 5)
    [[1, 3, 1], [1, 4], [2, 1, 2], [2, 3], [3, 2], [4, 1], [5]]
    >>> sums(6, 3)
    [[1, 2, 1, 2], [1, 2, 3], [1, 3, 2], [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """
    if n < 0:
        return []
    if n == 0:
        sums_to_zero = []     # The only way to sum to zero using positives
        return [sums_to_zero] # Return a list of all the ways to sum to zero
    result = []
    for k in range(1, m + 1):
        result = result + [ ___ for rest in ___ if rest == [] or ___ ]
    return result

Hint 5: Second Blank (at the end)

Hint 6: Third Blank (at the end)

If you get stuck (which many groups do), ask for help!

Tree Recursion on Exams

Tree recursion problems often appear on exams. Here's one:

Q4: A Perfect Question

This question was Fall 2023 Midterm 2 Question 4(a) (find it with the other past exams). The original exam version had an extra blank (where total < k * k appears below), but also included some guidance via multiple choice options and hints.

Definition. A perfect square is k*k for some integer k.

Implement fit, which takes positive integers total and n. It returns True or False indicating whether there are n positive perfect squares that sum to total. The perfect squares need not be unique.

def fit(total: int, n: int) -> bool:
    """Return whether there are n positive perfect squares that sums to total.

    >>> [fit(4, 1), fit(4, 2), fit(4, 3), fit(4, 4)]  # 1*(2*2) for n=1; 4*(1*1) for n=4
    [True, False, False, True]
    >>> [fit(12, n) for n in range(3, 8)]  # 3*(2*2), 3*(1*1)+3*3, 4*(1*1)+2*(2*2)
    [True, True, False, True, False]
    >>> [fit(32, 2), fit(32, 3), fit(32, 4), fit(32, 5)] # 2*(4*4), 3*(1*1)+2*2+5*5
    [True, False, False, True]
    """
    def f(total, n, k):
        if ____:
            return True
        elif total < k * k:
            return False
        else:
            return ____
    return f(total, n, 1)

Hint 7: Why the False cases are False (at the end)

Optional Question

If your group finishes early, here's one more. It's a relative of Q1: the number of paths through an m by n grid is an entry in Pascal's triangle, pascal(m + n - 2, m - 1).

Q5: Pascal's Triangle

Pascal's triangle is a recursively defined mathematical structure. Here are its first five rows:

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1

Every number in Pascal's triangle is the sum of the number above it and the number above and to the left of it. Rows and columns are zero-indexed; that is, the first row is row 0 and the first column is column 0. For example, the number at row 2, column 1 is 2.

Define pascal, which takes a row and a column and returns the value of the number at that position in Pascal's triangle. Both row and column will always be non-negative.

Hint: For which positions can we find the corresponding number without recursion? Remember that positions are zero-indexed!

def pascal(row: int, column: int) -> int:
    """Return the value at the given position of Pascal's triangle.

    >>> pascal(0, 0)  # The top left (the point of the triangle)
    1
    >>> pascal(0, 5)  # Empty entry; outside of Pascal's triangle
    0
    >>> pascal(3, 2)  # Row 3 (1 3 3 1), column 2
    3
    >>> pascal(4, 2)  # Row 4 (1 4 6 4 1), column 2
    6
    """