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

## Recursion Revisited

### Fast Exponentiation

```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)```

### Counting List Nesting

```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, ]]
print x, count_nesting(x)```

## In-Lab problem

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, ], 'a', [2, , [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)```

## Solution

```def count_a(L):
if not len(L):
return 0
count_zero = 0
if isinstance(L, list):
count_zero = count_a(L)
elif L == 'a':
count_zero = 1
return count_zero + count_a(L[1:])

if __name__ == '__main__':
L1 = [1, 2, 3, 4]
L2 = [['a', 4, ], 'a', [2, , [3, ['a']]], 'ab']
L3 = [[[['a']]], ['a', 'a', 'a'], []]

for L in [L1, L2, L3]:
print L
print count_a(L)```        