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 n
th 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
):
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 aboutn = 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)
andcount_stair_ways(n - 2)
represent?
Now, fill in the code for count_stair_ways
:
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.
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.)
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).
Run in 61A CodeHint: What happens if the insect hits the upper or rightmost edge of the grid?
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 CodeQ5: 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]
Run in 61A CodeHint: 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