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)
See this website for an example of Euclid's algorithm being used to find the gcd.
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: String slicing 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 a
applyToEach(testList, fabs)
>>> print testList [2, -3, 9, -8]
# Your Code Here
def fabs(a):
return a + 1
applyToEach(testList, fabs)
>>> print testList [1, 16, 64, 81]
# Your Code Here
def 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