Rao Discussion 4: Tree Recursion

This discussion worksheet is for the Rao offering of CS 61A. Your work is not graded and you do not need to submit anything.

Tree Recursion

A tree recursive function is a recursive function that makes more than one call to itself, resulting in a tree-like series of calls.

For example, this is the Virahanka-Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ....

Each term is the sum of the previous two terms. This tree-recursive function calculates the nth Virahanka-Fibonacci number.

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

Calling virfib(6) results in a call structure that resembles an upside-down tree (where f is virfib):

Virahanka-Fibonacci tree.

Each recursive call f(i) makes a call to f(i-1) and a call to f(i-2). Whenever we reach an f(0) or f(1) call, we can directly return 0 or 1 without making more recursive calls. These calls are our base cases.

A base case returns an answer without depending on the results of other calls. Once we reach a base case, we can go back and answer the recursive calls that led to the base case.

As we will see, tree recursion is often effective for problems with branching choices. In these problems, you make a recursive call for each branching choice.

Q1: Count Stair Ways

Imagine that you want to go up a flight of stairs that has n steps, where n is a positive integer. You can take either one or two steps each time you move. In how many ways can you go up the entire flight of stairs?

You'll write a function count_stair_ways to answer this question. Before you write any code, consider:

  • How many ways are there to go up a flight of stairs with n = 1 step? What about n = 2 steps? Try writing or drawing out some other examples and see if you notice any patterns.
  • What is the base case for this question? What is the smallest input?
  • What do count_stair_ways(n - 1) and count_stair_ways(n - 2) represent?

Now, fill in the code for count_stair_ways:

Run in 61A Code

Q2: Count K

Consider a special version of the count_stair_ways problem where we can take up to k steps at a time. Write a function count_k that calculates the number of ways to go up an n-step staircase. Assume n and k are positive integers.

Run in 61A Code

Q3: 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.)

Insect grids.

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?

Run in 61A Code

Q4: Max Product

Write a function that takes in a list and returns the maximum product that can be formed using non-consecutive elements of the list. All numbers in the input list are greater than or equal to 1.

Run in 61A Code

Q5: Flatten

Write a function flatten that takes a list and returns a "flattened" version of it. The input list may be a "deep list" (a list that contains other lists).

In the following example, [1, [[2], 3], 4, [5, 6]] is a deep list because [[2], 3] and [5, 6] are lists. Note that [[2], 3] is itself a deep list.

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Hint: you can check if something in Python is a list with the built-in type function. For example:

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
Run in 61A Code