CS 190C LAB 14: Friday, April 24, 2009

def recPower(a, n):
# raises a to the n-th power
    print "n =", n
    if n ==  0:
        return 1
    else:
        factor = recPower(a, n/2)
        if n%2 == 0:    	# n is even
            return factor*factor
        else:           	# n is odd
            return factor*factor*a
 
if __name__ == "__main__":
    print recPower(2,25)

def count_nesting(L):
    nesting = 0
    for item in L:
        if isinstance(item, list):
            nesting = max(nesting, 1 + count_nesting(item))
    return nesting
 
if __name__ == '__main__':
    x = range(10)
    print x, count_nesting(x)
    x = [1, [4, 5], 3, 6, 8, [3, [2]]]
    print x, count_nesting(x)

Write a recursive function count_a(L) which takes a list L and returns the number of times character 'a' occurs in L. The recursion should operate on the following principle:

• If the list is empty (it has length zero), return 0.
• If the list contains one or more element, consider the first element of L.
  • If the first element is not a list, check whether the first element is equal to 'a' and return the value 0 or 1, depending on the outcome of the comparison
  • If the first element is a list, make a recursive call using the first element as the argument. The call will return the number of 'a's occurring in this list.
• After handling the first element of the list, make a recursive call on the list without the first element. Add the value returned from this recursive call to the value generated in step 2.
• Return the value representing the solution for list L.

The Python function isinstance(test, list) returns True when variable test represents a list and False otherwise.

Here are some example lists that you can use to test your function:

L1 = [1, 2, 3, 4]
L2 = [ ['a', 4, [4]], 'a', [2, [4], [3, ['a']]], 'ab']
L3 = [[[['a']]], ['a', 'a', 'a'], []]
 
print L1
print count_a(L1)
 
print L2
print count_a(L2)
 
print L3
print count_a(L3)

def count_a(L):
    if not len(L):
        return 0
    count_zero = 0
    if isinstance(L[0], list):
        count_zero = count_a(L[0])
    elif L[0] == 'a':
        count_zero = 1
    return count_zero + count_a(L[1:])
 
if __name__ == '__main__':
    L1 = [1, 2, 3, 4]
    L2 = [['a', 4, [4]], 'a', [2, [4], [3, ['a']]], 'ab']
    L3 = [[[['a']]], ['a', 'a', 'a'], []]
 
    for L in [L1, L2, L3]:
        print L
        print count_a(L)