1 

Write an iterative function iterPower(base, exp) that calculates the exponential baseexp by simply using successive multiplication. For example, iterPower(base, exp)should compute baseexp by multiplying base times itself exp times. Write such a function below.

This function should take in two values - base can be a float or an integer; exp will be an integer ≥ 0. It should return one numerical value. Your code must be iterative - use of the ** operator is not allowed.

def iterPower(base, exp):    result = base    while exp > 1:        result = result * base        exp = exp - 1    if exp == 0:    	return 1    else:    	return result

2

In Problem 1, we computed an exponential by iteratively executing successive multiplications. We can use the same idea, but in a recursive function.

Write a function recurPower(base, exp) which computes baseexp by recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by base to solve the initial problem.

This function should take in two values - base can be a float or an integer; exp will be an integer ≥0. It should return one numerical value. Your code must be recursive - use of the ** operator or looping constructs is not allowed.

def recurPower(base, exp):    if exp > 1:    	return base * recurPower(base, exp-1)    elif exp == 0:    	return 1    else:    	return base

3

The function recurPower(base, exp) from Problem 2 computed baseexp by decomposing the problem into one recursive case and one base case:

Another way to solve this problem just using multiplication (and remainder) is to note that

Write a procedure recurPowerNew which recursively computes exponentials using this idea.

def recurPowerNew(base, exp):    if exp > 0 and exp % 2 == 0:    	return recurPowerNew((base * base),exp/2)    elif  exp > 0 and exp % 2 != 0:    	return base * recurPowerNew(base, exp-1)    else:    	return 1

4

The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,

• gcd(2, 12) = 2

• gcd(6, 12) = 6

• gcd(9, 12) = 3

• gcd(17, 12) = 1

Write an iterative function, gcdIter(a, b), that implements this idea. One easy way to do this is to begin with a test value equal to the smaller of the two input arguments, and iteratively reduce this test value by 1 until you either reach a case where the test divides both a and b without remainder, or you reach 1.

def gcdIter(a, b):	if a > b:		t = a		a = b		b = t	t = a	while  t > 1:		if b % t == 0 and a % t == 0:			return t		t = t - 1

5

The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,

• gcd(2, 12) = 2

• gcd(6, 12) = 6

• gcd(9, 12) = 3

• gcd(17, 12) = 1

A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that a and b are two positive integers:

• If b = 0, then the answer is a

• Otherwise, gcd(a, b) is the same as gcd(b, a % b)

Write a function gcdRecur(a, b) that implements this idea recursively. This function takes in two positive integers and returns one integer.

def gcdRecur(a, b):	if b == 0:		return a	else:		return gcdRecur(b, a%b)

6

Although Python provides a built-in function for computing the length of a string, we can write our own.

Write an iterative function, lenIter, which computes the length of an input argument (a string), by counting up the number of characters in the string.

def lenIter(aStr):	cnt = 0	for x in aStr:		cnt = cnt + 1	return cnt

7

For this problem, write a recursive function, lenRecur, which computes the length of an input argument (a string), by counting up the number of characters in the string.

Hint:  may be useful in this problem...

def lenRecur(aStr):	if aStr == '':		return 0	else:		a = aStr[1:]		return 1+lenRecur(a)

8

We can use the idea of bisection search to determine if a character is in a string, so long as the string is sorted in alphabetical order.

First, test the middle character of a string against the character you're looking for (the "test character"). If they are the same, we are done - we've found the character we're looking for!

If they're not the same, check if the test character is "smaller" than the middle character. If so, we need only consider the lower half of the string; otherwise, we only consider the upper half of the string. (Note that you can compare characters using Python's <function.)

Implement the function isIn(char, aStr) which implements the above idea recursively to test if char is in aStr. char will be a single character and aStr will be a string that is in alphabetical order. The function should return a boolean value.

As you design the function, think very carefully about what the base cases should be.

def isIn(char, aStr):    '''    char: a single character    aStr: an alphabetized string     returns: True if char is in aStr; False otherwise    '''    # Base case: If aStr is empty, we did not find the char.    if aStr == '':        return False    # Base case: if aStr is of length 1, just see if the chars are equal    if len (aStr) == 1:        return aStr == char    # Base case: See if the character in the middle of aStr equals the     #   test character     midIndex = len (aStr) / 2    midChar = aStr[midIndex]    if char == midChar:        # We found the character!        return True    # Recursive case: If the test character is smaller than the middle     #  character, recursively search on the first half of aStr    elif char < midChar:        return isIn (char, aStr[:midIndex])    # Otherwise the test character is larger than the middle character,    #  so recursively search on the last half of aStr    else:        return isIn (char, aStr[midIndex + 1:])

9

A semordnilap is a word or a phrase that spells a different word when backwards ("semordnilap" is a semordnilap of "palindromes"). Here are some examples:

• nametag / gateman
• dog / god
• live / evil
• desserts / stressed

Write a recursive program, semordnilap, that takes in two words and says if they are semordnilap.

This recursive function is not entirely straightforward. There are a few things that you need to check the first time you look at the inputs that you should not check on subsequent recursive calls: you need to make sure that the strings are not single characters, and also you need to be sure that the strings are not equal. If you do this check every time you call your function, though, this will end up interfering with the recursive base case (which we don't want!).

There's a few different ways you can perform checks on the inputs the first time. The first way would be to use keyword arguments. The second way would be to use a global variable, which you'll see in the next lecture video; however, using global variables is always a bit risky and thus not the best way to do this.

The third way to perform checks on the inputs the first time you see them, but not any subsequent time, is to use a wrapper function. This wrapper function performs some checks, then makes a call to the recursive function.

The idea of a wrapper function is really important. You'll see more wrapper functions later. To introduce you to the idea, we are providing you with the wrapper function; your job is to write the recursive function semordnilap that the wrapper function calls. Here is the wrapper function:

def semordnilapWrapper(str1, str2):    # A single-length string cannot be semordnilap    if len(str1) == 1 or len(str2) == 1:        return False    # Equal strings cannot be semordnilap    if str1 == str2:        return False    return semordnilap(str1, str2)

def semordnilapWrapper(str1, str2):	# A single-length string cannot be semordnilap    if len(str1) == 1 or len(str2) == 1:        return False    # Equal strings cannot be semordnilap    if str1 == str2:        return False    if len(str1) != len(str2):        return False	    #other situation    return semordnilap(str1, str2)def semordnilap(str1, str2):    if (len(str1) == 2) & (str1[0] == str2[-1]) & (str1[-1] == str2[0]):        return True    if str1[0] == str2[-1]:        return semordnilap(str1[1:], str2[:-1])

10

Write a procedure called oddTuples, which takes a tuple as input, and returns a new tuple as output, where every other element of the input tuple is copied, starting with the first one. So if test is the tuple ('I', 'am', 'a', 'test', 'tuple'), then evaluatingoddTuples on this input would return the tuple ('I', 'a', 'tuple').

def oddTuples(aTup):    Out=()    n = 0    for i in aTup:    	n = n + 1    	if n % 2 == 1:    		Out += (aTup[n-1],)    return Out

11

Here is the code for a function applyToEach:

def applyToEach(L, f):    for i in range(len(L)):        L[i] = f(L[i])

Assume that

testList = [1, -4, 8, -9]

For each of the following questions (which you may assume is evaluated independently of the previous questions, so that testList has the value indicated above), provide an expression using applyToEach, so that after evaluation testList has the indicated value. You may need to write a simple procedure in each question to help with this process.

Example Question:

>>> print testList[5, -20, 40, -45]

>>> print testList  [1, 4, 8, 9]

def fabs(a):    if a < 0:        return -a    else:        return aapplyToEach(testList, fabs)

>>> print testList  [2, -3, 9, -8]

# Your Code Heredef fabs(a):    return a + 1     applyToEach(testList, fabs)

>>> print testList  [1, 16, 64, 81]

# Your Code Heredef fabs(a):    return a * a     applyToEach(testList, fabs)

13

Consider the following sequence of expressions:

animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}animals['d'] = ['donkey']animals['d'].append('dog')animals['d'].append('dingo')

We want to write some simple procedures that work on dictionaries to return information.

First, write a procedure, called howMany, which returns the sum of the number of values associated with a dictionary. For example:

>>> print howMany(animals)6

def howMany(animals):    s = 0    for e in animals:        s += len(animals[e])    return s

14

Consider the following sequence of expressions:

animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}animals['d'] = ['donkey']animals['d'].append('dog')animals['d'].append('dingo')

We want to write some simple procedures that work on dictionaries to return information.

This time, write a procedure, called biggest, which returns the key corresponding to the entry with the largest number of values associated with it. If there is more than one such entry, return any one of the matching keys.

Example usage:

>>> biggest(animals)'d'

If there are no values in the dictionary, biggest should return None.

def biggest(aDict):    result = None    biggestValue = 0    for key in aDict.keys():        if len(aDict[key]) >= biggestValue:            result = key            biggestValue = len(aDict[key])    return result