#Part 1
def power(x,p):
    """returns x^p"""
    if p==0:
        return 1
    else:
        return x * power(x,p-1)



#Part 2
def sumList(lst):
    """returns of the sum of the elements in lst"""
    if lst == []:
        return 0
    else:
        return lst[0] + sumList(lst[1:])






#Part 3a
def searchList(lst, value):
    """returns True if value is in lst"""
    if lst == []:
        return False

    elif lst[0] == value:
        return True

    else:
        return searchList(lst[1:], value)
    






#Part 3b
def findInList(lst,value):
    """returns the index of value in lst, -1 otherwise"""
    if lst == []:
        print "Base Case: empty list, returning -1"
        return -1
    elif lst[0] == value:
        print "value found at head, returning 0"
        return 0
    else:
        print "value not found in head, searching tail ",lst[1:]
        ans = findInList(lst[1:],value)
        if ans >= 0:
            print "value found in tail, returning " +str(ans) +"+1"
            return ans+1
        else:
            print "value not found in tail, returning -1"
            return -1