CS61A Lab 9: Recursion, Tree Recursion, and Tree Data Structures

October 17-19, 2012

This lab has some sample tree data structures for you to use, as well as a template to fill in for the questions. To get this template file:

In your terminal:

	cp ~cs61a/public_html/fa12/labs/lab09/lab9.py .

Open the python interpreter:

	from lab9 import *

Iteration and Recursion

For the following 2 questions, write both an iterative solution (uses a while or for loop) and a recursive solution (no while or for loops).

1.) Write a function add_ten which takes 2 integers n and x, and returns x + n*10. DO NOT simply put return x + 10*n as the answer. Instead, try to write 2 versions of the function that implement it iteratively and recursively. We aren't testing you on your arithmetic skills.

2.) The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 BC, realized that the greatest common divisor of a and b is the smaller value if it evenly divides the larger value or the same as the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value. So if a is greater than b and a is not divisible by b then:

gcd(a, b) == gcd(b, a % b)

Write the gcd function using Euclid's algorithm.

1.) 
def add_ten_iter(x, n):
    i, sum = 1, x
    while i <= n:
        sum += 10
        i += 1
    return 1
   
def add_ten_rec(x, n):
    if n == 0:
        return x
    return 10 + add_ten_rec(x, n-1)


def gcd_iter(a, b):
    if a < b:
        return gcd_iter(b, a)
    while a > b and not a % b == 0:
        a, b = b, a % b
    return b

def gcd_rec(a, b):
    if a < b:
        return gcd_rec(b, a)
    if a > b and not a % b == 0:
        return gcd_rec(b, a % b)
    return b

Recursion and Tree Recursion

Rewrite the following function recursively.

def func(a, b):
    i = 1
    while i <= a:
        print(i*b)
        i += 1

Now we're going to approximate the sine trigonometric function using 2 useful facts. One is that sin x is approximately equal to x as x gets small (for this problem, below 0.0001), and the other is the trigonometric identity

Using those two facts, write a function sine that returns the sine of a value in radians.
Consider an insect in a MxN grid. The insect starts at the top left corner, (0,0), and wants to end up at the bottom right corner, (M-1,N-1). The insect is only capable of moving right or down. Write a function count_paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. [There is an analytic solution to this problem, but try to answer it procedurally using recursion].

For example, the 2x2 grid has a total of two ways for the insect to move from the start to the goal. For the 3x3 grid, the insect has 6 different paths (only 3 are shown above).
Consider the following problem: How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? Write a function count_change(a, denoms) that returns the number of ways you can count an amount a (in cents) using denoms coins, where denoms is the list, sorted in increasing order, of the denominations of money you can use to make your amount ([1, 5, 10, 25, 50]).

Hint: Your base cases have something to do with having no money (a == 0), or, either having no coins left or having no denominations left (len(denoms) == 0 or a < 0). Why are these the base cases?

1.)
def func_rec(a, b):
    if a == 0:
        return
    func_rec(a-1, b)
    print(a*b)
2.)def sine(x):
    if abs(x) < 0.0001:
        return x
    return (3*sine(x/3) - 4*pow(sine(x/3), 3))
3.)def paths(x, y):
    if x == 1 or y == 1:
        return 1
    return paths(x-1, y) + paths(x, y - 1)
4.)def count_change(a, kinds):
    if a == 0:
            return 1
    if a < 0 or kinds == 0:
        return 0
    return count_change(a, kinds[1:]) + count_change(a - kinds[0], kinds)

General Trees (with infinite children)

Trees are a way we have of representing a hierarchy of information. A family tree is a good example of something with a tree structure. You have a matriarch and a patriarch followed by all the descendants. Alternately, we may want to organize a series of information geographically. At the very top, we have the world, but below that we have countries, then states, then cities. We can also decompose arithmetic operations into something much the same way.

The name “tree” comes from the branching structure of the pictures, like real trees in nature except that they’re drawn with the root at the top and the leaves at the bottom.

Terminology

	node 		-	a point in the tree. In these pictures, each node includes a label (value at each node)
	root 		- 	the node at the top. Every tree has one root node
	children	- 	the nodes directly beneath it. Arity is the number of children that node has.
	leaf 		- 	a node that has no children. (Arity of 0!)

Take a moment to study the implementation of trees. The implementation of trees is in the file ~cs61a/lib/python_modules/tree.py . Look at the constructors, selectors, and printing methods. We give you some premade trees that you can work with for each section.

Now, after loading the file, the variable kennedy contains the following tree:

What expression, when evaluated, would produce the value "Caroline"?

Mutual Recursion

Mutual Recursion occurs when you have a function that will deal with Trees, as well as a function that will deal with Forests (sequences of Trees). Both functions call each other to solve whatever problem is at hand.

def square_tree(tree):
    tree.datum = square(tree.datum)
    square_forest(tree.children)

def square_forest(forest):
    for tree in forest:
        square_tree(tree)

Note that square_tree mutates the given tree.

The variable t is defined in tree.py and is a tree of integers that you can use to test your functions. Try out the following to see how it works.

>>> t
_______________
>>> a = t.copy()
>>> square_tree(a)
>>> a
_______________

Exercise: Draw your interpretation of this tree on a piece of paper

Question 1:

Define the function max_of_tree which takes in a tree as an argument and returns the max of all of the values of each node in the tree.

>>> t
4
|
+-2
| |
| +-8
| | |
| | +-7
| |
| +-3
|   |
|   +-1
|   |
|   +-6
|
+-1
| |
| +-5
|
+-3
  |
  +-2
  |
  +-9
>>> max_of_tree(t)
9

      def max_of_tree(tree):
    if tree.size == 1:
        return tree.datum
    child_max = max([max_of_tree(t) for t in tree.children]))
    return max(child_max, tree.datum)

Question 2:

Define the function deep_tree_reverse, which takes a tree and reverses the given order.

>>> a = t.copy()
>>> deep_tree_reverse(a)
>>> a
4
|
+-3
| |
| +-9
| |
| +-2
|
+-1
| |
| +-5
|
+-2
  |
  +-3
  | |
  | +-6
  | |
  | +-1
  |
  +-8
    |
    +-7

def deep_tree_reverse(tree):
    tree.children = tree.children[::-1]
    for c in tree.children:
        deep_tree_reverse(c)

Question 3:

Define the function filter_tree which takes in a tree as an argument and returns the same tree, but with items included or excluded based on the pred argument.

Note that there is ambiguity about what excluding a tree means. For this function, when you exclude a subtree, you exclude all of its children as well.

>>> a = t.copy()
>>> filter_tree(a, lambda x: x % 2 == 0)
>>> a
4
|
+-2
  |
  +-8
>>> a = t.copy()
>>> filter_tree(a, lambda x : x > 2)
>>> a
4
|
+-3
  |
  +-9

def filter_tree(tree, pred):
    tree.children[:] = filter_forest(tree.children)
    return tree

def filter_forest(forest, pred):
    rval = []
    for tree in forest:
        if pred(tree.datum):
            rval.append(filter_tree(tree))
    return rval

Binary Search Trees

Binary Search Trees are a special case of regular Trees that are useful for organizing data and searching through it efficiently. Binary search trees have 2 special properties apart from regular trees:

At every node, the node's left children are all less than that node, and the node's right children are all greater than to that node.
Every node has at most two children.

To illustrate this, first, draw these trees out on a piece of paper. Then, determine if the trees are valid binary search trees. Some are solved for you, and the rest are given to you as an exercise.

Note: str(bst) prints out the left subtree first, and then the right subtree.


VALID
>>> bst_a
3
|
+-1
| |
| +-0
| |
| +-empty_bst
|
+-5
  |
  +-empty_bst
  |
  +-6

INVALID
>>> bst_b
3
|
+-1
| |
| +-empty_bst
| |
| +-0
|
+-5
  |
  +-empty_bst
  |
  +-6

>>> bst_c
6
|
+-5
| |
| +-4
| | |
| | +-3
| | | |
| | | +-2
| | | | |
| | | | +-1
| | | | |
| | | | +-empty_bst
| | | |
| | | +-empty_bst
| | |
| | +-empty_bst
| |
| +-empty_bst
|
+-empty_bst

>>> bst_d
5
|
+-4
| |
| +-1
| | |
| | +-empty_bst
| | |
| | +-2
| |
| +-empty_bst
|
+-9
  |
  +-6
  | |
  | +-empty_bst
  | |
  | +-8
  |   |
  |   +-7
  |   |
  |   +-empty_bst
  |
  +-empty_bst

Question 1:

Write a function valid_bst, that takes a given bst, and returns True if the bst is a valid binary search tree; that is, for every node, that node's left children are less than the node, and that node's right children are greater than that node. Test your function with the given binary search trees from above (these are already typed out in the lab9.py file) to make sure your function works properly.

      def get_max(bst):
    while not bst.right.is_empty:
        bst = bst.right
    return bst.datum

def get_min(bst):
    while not bst.left.is_empty:
        bst = bst.left
    return bst.datum

def is_valid_bst(bst):
    if not bst.left.is_empty:
        if not is_valid_bst(bst.left):
            return False
        if get_max(bst.left) > bst.datum:
            return False
    if not bst.right.is_empty:
        if not is_valid_bst(bst.right):
            return False
        if get_min(bst.right) < bst.datum:
            return False
    return True

Question 2:

Write a function bst_count_num which takes two arguments, bst and max. bst_count_num should return the number of items in the tree that are less than the given max. Implement bst_count in the following ways:

Using the bst_find function.
Using recursion.

def bst_count_num_find(bst, max):
    min = get_min(bst)
    num = 0
    while min < max:
        if bst.find(min):
            num += 1
        min += 1
    return num

def bst_count_num_recr(bst, max):
    tot = 0
    if not bst.left.is_empty
        tot += bst_count_num_recr(bst.left, max)
    if not bst.right.is_empty
        tot += bst_count_num_recr(bst.right, max)
    if bst.datum < max:
        tot += 1
    return tot

Question 3:

Write a function is_right_bigger, which takes a single argument bst, and returns whether or not the right subtree in this bst is larger (has more items) than the left subtree.

>>> is_right_bigger(bst_c)
False
>>> is_right_bigger(bst_d)
True

def is_right_bigger(bst):
    if not bst.left.is_empty and not bst.right.is_empty:
        return bst.right.size > bst.left.size
    return bst.left == empty_bst