Getting Started

In this discussion, don't use a Python interpreter to run code until you are confident your solution is correct. Figure things out and check your work by thinking about what your code will do. Not sure? Talk to your group!

[Note] 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.

[For Fun] This emoticon of a guy in a cowboy hat is valid Python: o[:-D]

>>> o = [2, 0, 2, 4]
>>> [ o[:-D] for D in range(1,4) ]
[[2, 0, 2], [2, 0], [2]]

🤠

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 lecture, the recursive case is to add together the previous two Fibonacci numbers.
• In double_eights from lab, the recursive case is to check for double eights in the rest of the number.
• In count_partitions from lecture, 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.

In case you need a refresher on Tree Recursion, you can use the section below (dropdown if you're on the website)

def virfib(n):
    if n == 0 or n == 1:
        return n
    return virfib(n - 1) + virfib(n - 2)

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, n):
    """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
    """
    if m == 1 or n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)
    # Base case: Look at the two visual examples given. Since the insect
    # can only move to the right or up, once it hits either the rightmost edge
    # or the upper edge, it has a single remaining path -- the insect has
    # no choice but to go straight up or straight right (respectively) at that point.
    # There is no way for it to backtrack by going left or down.

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)), and slicing (e.g., s[1:]). Use those! There will be plenty of time for other list operations when we introduce them next week.

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:].

[<expression> for <element> in <sequence>]
[<expression> for <element> in <sequence> if <conditional>]

>>> [i*i for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

>>> result = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         result = result + [i*i]
>>> result
[4, 16]

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

Q2: Even weighted

Write a function that takes a list s and returns a new list that keeps only the even-indexed elements of s and multiplies them by their corresponding index. First approach this problem with a normal for loop (without list comprehension).

def even_weighted_loop(s):
    """
    >>> x = [1, 2, 3, 4, 5, 6]
    >>> even_weighted_loop(x)
    [0, 6, 20]
    """
    result = []
    for i in range(len(s)):
        if i % 2 == 0:
            result = result + [i * s[i]]
    return result

Now that you’ve done it with a for loop, try it with a list comprehension!

def even_weighted_comprehension(s):
    """
    >>> x = [1, 2, 3, 4, 5, 6]
    >>> even_weighted_comprehension(x)
    [0, 6, 20]
    """
    return [i * s[i] for i in range(len(s)) if i % 2 == 0]

If you get stuck, ask for help!

Trees

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_leaf(tree):
    return not branches(tree)

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

Q3: Has Path

Implement has_path, which takes a tree t and a list p. It returns whether there is a path from the root of t with labels p. For example, t1 has a path from its root with labels [3, 5, 6] but not [3, 4, 6] or [5, 6].

Important: Before trying to implement this function, discuss these questions from lecture about the recursive call of a tree processing function:

• What recursive calls will you make?
• What type of values do they return?
• What do the possible return values mean?
• How can you use those return values to complete your implementation?

If you get stuck, you can view our answers to these questions by clicking the hint button below, but please don't do that until your whole group agrees.

def has_path(t, p):
    """Return whether tree t has a path from the root with labels p.

    >>> t2 = tree(5, [tree(6), tree(7)])
    >>> t1 = tree(3, [tree(4), t2])
    >>> has_path(t1, [5, 6])        # This path is not from the root of t1
    False
    >>> has_path(t2, [5, 6])        # This path is from the root of t2
    True
    >>> has_path(t1, [3, 5])        # This path does not go to a leaf, but that's ok
    True
    >>> has_path(t1, [3, 5, 6])     # This path goes to a leaf
    True
    >>> has_path(t1, [3, 4, 5, 6])  # There is no path with these labels
    False
    """
    if p == [label(t)]:
        return True
    elif label(t) != p[0]:
        return False
    else:
        return any([has_path(b, p[1:]) for b in branches(t)])

If your group needs some guidance, you can click on the hints below, but please talk with your group first before reading the hints.

for ____:
    if ____:
        return True
return False

Discussion Time! Can the else case of has_path be written in just one line? Why or why not? You can ignore how fast the function will run.

Q4: Find Path

Implement find_path, which takes a tree t with unique labels and a value x. It returns a list containing the labels of the nodes along a path from the root of t to a node labeled x.

If x is not a label in t, return None. Assume that the labels of t are unique.

First talk through how to make and use the recursive call. (Try it yourselves; don't just click the hint button. That's how you learn.)

def find_path(t, x):
    """
    >>> t2 = tree(5, [tree(6), tree(7)])
    >>> t1 = tree(3, [tree(4), t2])
    >>> find_path(t1, 5)
    [3, 5]
    >>> find_path(t1, 4)
    [3, 4]
    >>> find_path(t1, 6)
    [3, 5, 6]
    >>> find_path(t2, 6)
    [5, 6]
    >>> print(find_path(t1, 2))
    None
    """
    if label(t) == x:
        return [label(t)]
    for b in branches(t):
        path = find_path(b, x)
        if path:
            return [label(t)] + path
    return None

Please don't view the hints until you've discussed with your group and can't make progress.

Description Time! When your group has completed this question, it's time to describe why this function does not have a base case that uses is_leaf. Come up with an explanation as a group and pick someone to present your answer.

Q5: Sprout Leaves

Define a function sprout_leaves that takes in a tree, t, and a list of leaf labels, leaves. It produces a new tree that is identical to t, but where each old leaf node has new branches, for each label in leaves.

For example, suppose we have the tree t = tree(1, [tree(2), tree(3, [tree(4)])]). Calling sprout_leaves(t, [5, 6]) produces the following tree:

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the labels in leaves at each leaf of
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    if is_leaf(t):
        return tree(label(t), [tree(leaf) for leaf in leaves])
    return tree(label(t), [sprout_leaves(s, leaves) for s in branches(t)])

Submit Attendance

You're done! Excellent work this week. Please be sure to ask your section TA for the attendance form link and fill it out for credit. (one submission per person per section).

Extra Practice

Q6: Tree Deciphering

What value is bound to result?

result = label(min(branches(max([t1, t2], key=label)), key=label))

How convoluted! (That's a big word.)

>>> s = [-3, -5, -4, -1, -2]
>>> max(s)
-1
>>> max(s, key=abs)
-5
>>> max([abs(x) for x in s])
5

In case you're wondering, this expression does not violate an abstraction barrier. [t1, t2] and branches(t) are both lists (not trees), and so it's fine to call min and max on them.