1) Consider the triangleArea function from the textbook shown below:
1. def triangleArea(sideLength) :
2. if sideLength <= 0 :
3. return 0
4. if sideLength == 1 :
5. return 1
6. smallerSideLength = sideLength - 1
7. smallerArea = triangleArea(smallerSideLength)
8. area = smallerArea + sideLength
9. return areaWhere is/are the recursive call(s)?
A) line #7
2) Consider the triangleArea function from the textbook shown below:
1. def triangleArea(sideLength) :
2. if sideLength <= 0 :
3. return 0
4. if sideLength == 1 :
5. return 1
6. smallerSideLength = sideLength - 1
7. smallerArea = triangleArea(smallerSideLength)
8. area = smallerArea + sideLength
9. return areaWhere is/are the terminating condition(s)?
A) lines #3 and #5
3) Consider the following code snippet for recursive addition:
1. def add(i, j) :
2. # assumes i >= 0
3. if i == 0 :
4. return j
5. else :
6. return add(i - 1, j + 1)Identify the terminating condition in this recursive function.
A) if i == 0 :
4) Consider the following code snippet for calculating Fibonacci numbers recursively:
1. def fib(n) :
2. # assumes n >= 0
3. if n <= 1 :
4. return n
5. else :
6. return fib(n - 1) + fib(n - 2)Identify the terminating condition in this recursive function.
A) n <= 1
5) Consider the following recursive code snippet:
1. def mystery(n, m) :
2. if n <= 0 :
3. return 0
4. if n == 1 :
5. return m
6. return m + mystery(n - 1, m)Identify the terminating condition(s) of function mystery?
A) n <= 0 or n == 1
6) Consider the following recursive code snippet:
1. def mystery(n, m) :
2. if n == 0 :
3. return 0
4. if n == 1 :
5. return m
6. return m + mystery(n - 1, m)What value is returned from a call to mystery(1, 5)?
A) 5
7) Consider the following recursive code snippet:
1. def mystery(n, m) :
2. if n == 0 :
3. return 0
4. if n == 1
5. return m
6. return m + mystery(n - 1, m)What value is returned from a call to mystery(3,6)
A) 18
8) Consider the recursive function myPrint:
1. def myPrint(n) :
2. if n < 10 :
3. print(n)
4. else :
5. m = n % 10
6. print(m)
7. myPrint(n / 10)What is printed for the call myPrint(8)?
A) 8
9) Complete the code for the recursive function printSum shown in this code snippet, which is intended to return the sum of digits from 1 to n:
1. def printSum(n) :
2. if n == 0 :
3. return 0
4. else :
5. ________________________________A) return n + printSum(n – 1)
10) Consider the code for the recursive function myPrint shown in this code snippet:
1. def myPrint(n) :
2. if n == 0 :
3. return 0
4. else :
5. return n + mysteryPrint(n - 1)To avoid infinite recursion, which of the following lines of code should replace the current terminating case?
A) if n <= 0
11) Consider the following code segment:
def fib(n) : # Line 1
if n <= 2 :
return 1 # Line 2
else :
return fib(n - 1) + fib(n - 2) # Line 3
print(fib(6)) Which line is the base case for this recursive function?
A) Line 2
12) The following function is supposed to use recursion to compute the area of a square from the length of its sides. For example, squareArea(3) should return 9.
def squareArea(sideLength) :
if sideLength == 1 :
return 1
else :
____________________What line of code should be placed in the blank to achieve this goal?
A) return 2 * (sideLength – 1) + squareArea(sideLength – 1)
13) Consider the following code segment:
def triangleArea(sideLength) :
if sideLength == 1:
return 1
return triangleArea(sideLength - 1) + sideLength
print(triangleArea(5))How many times is the triangleArea function called when this code segment executes?
A) 5
14) Consider the following recursive function:
def myPrint(n) :
if n < 10 :
print(n)
else :
m = n % 10
print(m)
myPrint(n // 10)What does this function do?
A) It prints a positive value backward, digit by digit
15) Consider the following recursive function:
def myPrint(n) :
if n < 10 :
print(n)
else :
m = n % 10
print(m, end="")
myPrint(n // 10)What is printed for the call myPrint(821)?
A) 128
16) Consider the following code segment:
def mysteryPrint(n) :
if n == 0 :
return 0
else :
return n + mysteryPrint(n - 1)What is returned for the call mysteryPrint(-4)?
A) Nothing. The program crashes with a runtime error.
17) Consider the following function for computing the greatest common divisor of two integers greater than 0:
def gcd(x, y): # Line 1
if x % y == 0: # Line 2
return y # Line 3
else:
return gcd(y, x % y) # Line 4Which line contains a recursive function call?
A) Line #4
18) This function is supposed to recursively compute x to the power n, where x and n are both non-negative integers:
1. def power(x, n) :
2. if n == 0 :
3. ________________________________
4. else :
5. return x * power(x, n - 1)What code should be placed in the blank to accomplish this goal?
A) return 1
19) What is required to make a recursive function successful?I. One or more special cases that handle the simplest computations directlyII. A recursive call to a smaller or simpler version of the problemIII. Mutually recursive calls
A) I and II only
20) Consider the triangleArea function from the textbook shown below:
1. def triangleArea(sideLength) :
2. if sideLength <= 0 :
3. return 0
4. if sideLength == 1 :
5. return 1
6. smallerSideLength = sideLength - 1
7. smallerArea = triangleArea(smallerSideLength)
8. area = smallerArea + sideLength
9. return areaWhat will happen if line #6 is changed to:
smallerSideLength = sideLengthA) smallerSideLength = sideLength
21) Consider the triangleArea function from the textbook shown below:
1. def triangleArea(sideLength) :
2. if sideLength <= 0 :
3. return 0
4. if sideLength == 1 :
5. return 1
6. smallerSideLength = sideLength - 1
7. smallerArea = triangleArea(smallerSideLength)
8. area = smallerArea + sideLength
9. return areaWhat will happen if lines #2 and #3 are replaced with the following code segment?
if sideLength <= 0 :
return sideLengthA) The function will still return correct results for all triangles with non-negative side lengths.
22) A recursive computation solves a problem using the solution to the same problem with ____________________ inputs.
A) simpler
23) Consider the following code segment:
____________________
if x % y == 0:
return y
else:
return gcd(y, x % y)Which statement should be placed in the blank to complete the recursive function definition?
A) def gcd(x, y) :
24) What term is used to describe a function that keeps on calling itself until the program crashes?
A) Infinite Recursion
25) How many recursive calls to the fib function shown below would be made from an original call to fib(4)? (Do not count the original call)
1. def fib(n) :
2. # assumes n >= 0
3. if n <= 1 :
4. return n
5. else :
6. return fib(n - 1) + fib(n - 2)A) 8
26) Which of the following options could be used as a terminating condition for a recursive function that finds the middle character of a String with any number of characters?I. the length of the String is 1II. first and last String characters matchIII. the String is not empty
A) I
27) Consider the function powerOfTwo shown below:
1. def powerOfTwo(n) :
2. if n == 1 :
3. return True
4. elif n % 2 == 1 :
5. return False
6. else :
7. return powerOfTwo(n / 2)How many recursive calls are made from the original call powerOfTwo(63) (not including the original call)?
A) 0
28) Consider the function powerOfTwo shown below:
1. def powerOfTwo(n) :
2. if n == 1 :
3. return True
4. elif n % 2 == 1 :
5. return False
6. else :
7. return powerOfTwo(n / 2)How many recursive calls are made from the original call powerOfTwo(64) (not including the original call)?
A) 6
29) Complete the code for the myFactorial recursive function shown below, which is intended to compute the factorial of the value passed to the function:
1. def myFactorial(n) :
2. if n == 1 :
3. return 1
4. else :
5. _______________________ A) return n * myFactorial(n – 1)
30) Complete the code for the myFactorial recursive function shown below, which is intended to compute the factorial of the value passed to the function:
1. def myFactorial(n) :
2. if _____________________________ :
3. return 1
4. else :
5. return n * myFactorial(n - 1)A) n == 1
31) Complete the code for the myFactorial recursive function shown below, which is intended to compute the factorial of the value passed to the function:
1. def myFactorial(n) :
2. if n == 1 :
3. _____________________________
4. else :
5. return n * myFactorial(n - 1)A) return 1
32) Complete the code for the calcPower recursive function shown below, which is intended to raise the base number passed into the function to the exponent power passed into the function:
1. def calcPower(base, exponent) :
2. answer = 0
3. if exponent == 0 :
4. answer = 1
5. else :
6. _____________________________
7. return answerA) answer = base * calcPower(base, exponent – 1)
33) Given the following code:
def main() :
recurse(3)
def recurse(n) :
total = 0
if n == 0 :
return 0
else :
total = 3 + recurse(n - 1)
print(total)
return total
main()What values will be printed when this code is executed?
A) 3, 6, and 9
34) Given the following code:
def main() :
recurse(4)
def recurse(n) :
total = 0
if n == 0 :
return 0
else :
total = 4 + recurse(n - 2)
print(total)
return total
main()What values will be printed when this code is executed?
A) 4 and 8
35) The following code segment is supposed to sum the numbers from 1 up to and including n using recursion.
def sumOneToN(n) :
if n == 0 :
return 0
____________________Which statement should be placed in the blank to achieve this goal?
A) return n + sumOneToN(n – 1)
36) What is displayed by the following code segment?
def mystery(n) :
if n == 0 :
return 0
else :
return n % 10 + mystery(n // 10)
print(mystery(0))A) 0
37) What is displayed by the following code segment?
def mystery(n) :
if n == 0 :
return 0
else :
return n % 10 + mystery(n // 10)
print(mystery(-1))A) A runtime error is reported
38) What is displayed by the following code segment?
def mystery(n) :
if n == 0 :
return 0
else :
return n % 10 + mystery(n // 10)
print(mystery(123))A) 6
39) Consider the following code segment:
def mystery(s, c) :
if len(s) == 0 :
return False
elif s[i] == c :
return True
else :
return mystery(s[1 : ], c)What does the mystery function do?
A) It determines whether or not c occurs in s
40) What is displayed when the following program executes?
def mystery(s) :
return s[len(s) - 1] + mystery(s[0 : len(s) - 1])
mystery("123")A) 321
41) When a recursive function is called, and it does not perform recursion, what must be true?
A) The terminating condition was true.
42) Consider the triangleArea function from the textbook shown below:
1. def triangleArea(sideLength) :
2. if sideLength <= 0 :
3. return 0
4. if sideLength == 1 :
5. return 1
6. smallerSideLength = sideLength - 1
7. smallerArea = triangleArea(smallerSideLength)
8. area = smallerArea + sideLength
9. return areaWhat will happen if lines 4 and 5 are replaced with the following lines of code?
if sideLength == 1 :
return 2A) It would increase the result calculated by the function for all calls except those where sideLength <= 0
43) Consider the triangleArea function from the textbook shown below:
1. def triangleArea(sideLength) :
2. if sideLength <= 0 :
3. return 0
4. if sideLength == 1 :
5. return 1
6. smallerSideLength = sideLength - 1
7. smallerArea = triangleArea(smallerSideLength)
8. area = smallerArea + sideLength
9. return areaAssume that line #5 is changed to this:
smallerArea = triangleArea(sideLength)This would cause infinite recursion for __________________________________
A) triangles with sideLength greater than or equal to 1
44) Consider the following function:
1. def mystery(n, m) :
2. if n == 0 : # special case 1
3. return 0
4. if n == 1 : # special case 2
5. return m
6. return m + mystery(n - 1), m)What will happen if lines #2 and #3 were swapped with lines #4 and #5?
A) The original function and the modified function will return the same result for all integer values of n and m.
45) Consider the function powerOfTwo shown below:
1. def powerOfTwo(n) :
2. if n == 1 :
3. return True
4. elif n % 2 == 1 :
5. return False
6. else :
7. return powerOfTwo(n / 2)What is the best interpretation of lines 2 and 3?
A) One is a power of two.
46) A palindrome is a word or phrase spelled which reads the same forward or backward. Consider the following code snippet:
def palindrome(s) :
return isPal(s, 0, len(s) - 1)
def isPal(s, left, right) :
if left >= right :
return True
elif s[left] == s[right] :
return isPal(s, left + 1, right - 1)
else :
return FalseWhat does the function palindrome return?
A) the Boolean value returned from the isPal function
47) What is the purpose of a recursive helper function?
A) Shield the user of the recursive function from the recursive details
48) Consider the following code segment:
def sumList(data) :
return sumListIndex(data, 0)
def sumListIndex(data, i) :
if i == len(data) :
return 0
else :
return data[i] + sumListIndex(data, i + 1)This code segment contains an example of
A) a recursive helper function
49) The printList function is supposed to print all of the elements in a list, one per line. What line of code should be placed in the blank to achieve this goal?
def printList(data) :
____________________
def printHelper(data, i) :
if i == len(data) :
return
print(data[i])
printHelper(data, i + 1)A) printHelper(data, 0)
50) The following code segment is supposed to determine whether or not a string is a palindrome, meaning that it is the same forward and backward.
def isPalindrome(s) :
return palindromeHelper(s, l, h)
def palidromeHelper(s, l, h) :
if h <= l :
return True
if s[l] != s[h] :
return False
____________________What line of code should be placed in the blank to achieve this goal?
A) palindromeHelper(s, l + 1, h – 1)
51) A palindrome is a word or phrase that reads the same forward and backward. Consider the functions palindrome and isPal shown below:
def palindrome(s) :
return isPal(s, 0, len(s) - 1)
def isPal(s, left, right) :
if left >= right :
return True
elif s[left] == s[right] :
return isPal(s, left + 1, right - 1)
else :
return FalseThe function isPal as shown here would be considered to be a ____ function.
A) helper
52) Why does the best recursive function usually run slightly slower than its iterative counterpart?
A) Each recursive function call takes processor time.
53) Which statement(s) about recursion are true?I. Recursion is faster than iterationII. Recursion is often easier to understand than iterationIII. Recursive design has an economy of thought
A) II and III
54) In recursion, the terminating condition is analogous to a loop _________.
A) termination condition
55) Consider the following code segment for computing Fibonacci numbers. How many times is fib(3) computed in order to compute fib(7)?
def fib(n) :
if n <= 2 :
return 1
else :
return fib(n - 1) + fib(n - 2)A) 5
56) How many squares are drawn by the following code segment?
def tSquare(width, x, y, canvas) :
canvas.drawRect(x, y, width, width)
if width >= 4 :
tSquare(width / 2, x, y, canvas)
tSquare(width / 2, x + width / 2, canvas)
tSquare(width / 2, x, y + width / 2, canvas)
tSquare(width / 2, x + width / 2, y + width / 2, canvas)
# Code to setup the canvas has been omitted
tSquare(0, 0, 8, canvas)A) 5
57) How many squares are drawn by the following code segment?
def tSquare(width, x, y, canvas) :
canvas.drawRect(x, y, width, width)
if width >= 4 :
tSquare(width / 2, x, y, canvas)
tSquare(width / 2, x + width / 2, canvas)
tSquare(width / 2, x, y + width / 2, canvas)
tSquare(width / 2, x + width / 2, y + width / 2, canvas)
# Code to setup the canvas has been omitted
tSquare(0, 0, 16, canvas)A) 21
58) Which of the following strings is a palindrome?
A) “B”
59) The string “eat” has ____ permutations.
A) 6
60) A unique permutation is one that is different from any other generated permutation. How many unique permutations does the string “bee” have?
A) 3
61) How many permutations are in a 5 letter word?
A) 120
62) Which of the following statements about recursion is correct?
A) In many cases, a recursive solution will be easier to understand and to implement than an iterative solution.
63) Which of the following statements about palindromes is correct?
A) All strings of length 0 or 1 are palindromes.
64) Recall the permutations function from Section 11.5 in the textbook.
def permutations(word) :
result = []
____________________
result.append(word)
return result
else:
for i in range(len(word)) :
shorter = word[ : i] + word[i + 1 : ]
shorterPermutations = permutations(shorter)
for string in shorterPermutations :
result.append(word[i] + string)
return resultIn the textbook, the line now represented by the blank was if len(word) == 0 :. What line of code could be used instead to achieve the same list of permutations?
A) if len(word) == 1 :
65) Recall the permutations function from Section 11.5 in the textbook.
def permutations(word) :
result = []
if len(word) == 0 :
result.append(word)
return result
else:
____________________
shorter = word[ : i] + word[i + 1 : ]
shorterPermutations = permutations(shorter)
for string in shorterPermutations :
result.append(word[i] + string)
return resultIn the textbook, the line now represented by the blank was for i in range(len(word)) :. What would happen if the blank was filled in with for i in range(len(word) - 1, -1, -1) :
A) The same permutations of the word would be generated in the reverse order
66) Recall the permutations function from Section 11.5 in the textbook.
def permutations(word) :
result = []
if len(word) == 0 :
result.append(word)
return result
else:
for i in range(len(word)) :
shorter = word[ : i] + word[i + 1 : ]
shorterPermutations = permutations(shorter)
for string in shorterPermutations :
result.append(word[i] + string)
return resultWhat is the base case for this function?
A) The empty string
67) Recall the permutations function from Section 11.5 in the textbook.
def permutations(word) :
result = []
if len(word) == 0 :
result.append(word)
return result
else:
for i in range(len(word)) :
shorter = word[ : i] + word[i + 1 : ]
shorterPermutations = permutations(shorter)
for string in shorterPermutations :
result.append(word[i] + string)
return resultHow permutations will be generated by calling permutations("code")?
A) 24
68) _______________ is a problem-solving technique that examines partial solutions, abandons unsuitable ones, and returns to consider other candidate solutions.
A) Backtracking
69) Recall the backtracking strategy outlined in the textbook. A similar strategy can be used to solve Sudoku puzzles.
def solve(gameBoard) :
status = examine(gameBoard)
if status == CONTINUE :
for nextBoard in extend(gameBoard) :
solve(nextBoard)
elif status == ACCEPT:
____________________What code should be placed in the blank to complete the solution to this problem?
A) print(gameBoard)
70) Which statement about backtracking is correct?
A) Backtracking builds up partial solutions that get increasingly closer to the goal.
71) Which problem is well suited to being solved with a backtracking algorithm?
A) Finding a solution to the eight queens problem
72) Recursion will take place if any of the following happen:I. function A calls function B, which calls function CII. function A calls function B, which calls function AIII. function A calls function A
A) II and III
73) Consider the following code snippet:
def isEven(num) :
if num % 2 == 0 :
return True
else :
return isOdd(num)
def isOdd(num) :
if num % 2 == 1 :
return True
else :
return isEven(num)For any given value of num, what is the maximum number of function calls that could occur?
A) 2
74) Complete the following code snippet, which is intended to determine if a value is even or odd using mutual recursion:
def isEven(num) :
if num == 0 :
return True
else :
return isOdd(abs(num) - 1)
def isOdd(num) :
if num == 0 :
________________________
else :
return isEven(abs(num) - 1)A) return False
75) Consider the following code segment:
def f1(n) :
if n < 0 :
return 0
if n % 2 == 1 :
return n
return f2(n + 1)
def f2(n) :
if n < 0 :
return 0
if n % 2 == 0 :
return n
return f1(n // 2)This code segment would be classified as:
A) mutually recursive
76) Consider the following code segment:
def f1(n) :
if n < 0 :
return 0
if n % 2 == 1 :
return n
return f2(n + 1)
def f2(n) :
if n < 0 :
return 0
if n % 2 == 0 :
return n
return f1(n // 2)
print(f1(10))When this code is run, it will display:
A) 5
77) Consider the following code segment:
def f1(n) :
if n < 0 :
return 0
if n % 2 == 1 :
return n
return f2(n + 1)
def f2(n) :
if n < 0 :
return 0
if n % 2 == 0 :
return n
return f1(n // 2)
print(f2(7))When this code is run, it will display:
A) 3
78) Consider the following code segment:
def f(n) :
if n == 1 :
return n
elif n == 2 :
____________________
else :
return f(n // 2)
def g(n) :
if n % 2 == 0 :
return n - 1
else :
return f(n - 1)What statement should be placed in the blank to make these functions mutually recursive?
A) return g(n – 1)
79) The following code segment is supposed to determine if an integer, n, is even or odd using mutual recursion.
def isEven(n) :
if n == 0 :
return True
else :
return isOdd(abs(n) - 1)
def isOdd(n) :
____________________
return False
else :
return isEven(abs(n) - 1)What code should be placed in the blank to achieve this goal?
A) if n == 0 :
80) What library is used to load a webpage into a data structure that makes it easy to extract the page’s tags and the information between the tags?
A) Beautiful Soup
81) Which statement finds all of the links in a webpage?
A) elements = doc.find_all(“a”)
82) Assume that the address variable currently holds the URL for webpage. Which statement(s) store a structured representation of that webpage in the doc variable?
A) response = urllib.request.urlopen(address)
doc = bs4.BeautifulSoup(response)
83) Which problem is well suited to being solved with mutually recursive functions?
A) Evaluating a numeric expression