'''Write the following methods recursively. You may need to write helper
functions for some of them.

They are mostly exercises that were collected from various sources on
the internet:

  http://academics.tjhsst.edu/compsci/CS2C/U3/recurlab.html
  http://www.cs.arizona.edu/classes/cs227/spring06/misc/24RecursionExercises.htm
  http://www.engr.mun.ca/~theo/Courses/ds/recursion_practice.html
  http://www.cs.arizona.edu/classes/cs227/spring06/misc/50RecursionExercises.htm
'''

def rev(n):
    '''Return the result of reversing the digits in integer n. For example,
    rev(512) should return 215.'''
    pass

def add_commas(n):
    '''Return a string version of integer n with commas added. For example,
    add_commas(15866321) should return "15,866,321".'''
    pass

def index(L, v):
    '''Return the index of v in list L.'''
    pass
    
def sum(L):
    '''Return the sum of the numbers in list L.'''
    pass

def _binary_search(L, v, i, j):
    '''Return the index of v in L[i:j], or j if v is not in L.'''
    pass
    
def binary_search(L, v):
    return _binary_search(L, v, 0, len(L))

def power(x, n):
    '''Return x to the power n using this formula:

    http://www.enel.ucalgary.ca/People/Norman/engg335_fall1997/recurs/power_t.gif
    '''

class Node:
    '''A node in a binary tree.'''
    def __init__(self, v):
        self.value = v
        self.left = None
        self.right = None

def count(root, v):
    '''Return the number of times v appears in the tree rooted at Node
    v.'''
    pass

def copy(root):
    '''Return a copy of the tree rooted at root.'''
    pass

def count_at_depth(root, d):
    '''Return the number of nodes that are at depth d in the tree rooted at
    Node root.'''