← Back

Chapter 12: Recursion

Every problem in the chapter beside the book’s answer, a chapter at a time as you scroll.

Chapter 12: Recursion

35 problems · 0 figures

Concepts in Practice 12.1.1 §12.1 source ↗

How is the problem of moving two rings solved using recursion?
  1. a.
    Move the small ring to the middle tower, move the bigger ring to the target tower, and move the small ring to the target tower.
  2. b.
    Move two rings from the source tower to the target tower.
  3. c.
    Cannot be solved with recursion.

Answer

A. Move the small ring to the middle tower, move the bigger ring to the target tower, and move the small ring to the target tower.
The move of the smaller ring, which is a smaller problem, is done twice on the way to solving for the two rings overall. The task of moving all three rings is broken down into smaller tasks of moving one ring at a time.

Concepts in Practice 12.1.2 §12.1 source ↗

How is the problem of moving three rings solved using recursion?
  1. a.
    Move three rings from the source tower to the target tower.
  2. b.
    Move two rings to the middle tower, then move the biggest ring to the target tower, and finally, move two rings to the target tower.
  3. c.
    Cannot be solved with recursion.

Answer

B. Move two rings to the middle tower, then move the biggest ring to the target tower, and finally, move two rings to the target tower.
The two-ring solution from question 1 is used in the solution for three rings.

Concepts in Practice 12.1.3 §12.1 source ↗

How many times is the two-ring solution used with three rings?
  1. a.
    1
  2. b.
    2
  3. c.
    0

Answer

B. 2
Once to move two rings to the middle tower following the rules, then to move two rings to the target tower.

Concepts in Practice 12.1.4 §12.1 source ↗

How many total steps does it take to solve two rings?
  1. a.
    1
  2. b.
    2
  3. c.
    3

Answer

C. 3
The small ring is moved to the middle tower. The bigger ring is moved to the target tower. Then, the small ring is moved from the middle to the target.

Concepts in Practice 12.1.5 §12.1 source ↗

How many total steps does it take to solve three rings?
  1. a.
    3
  2. b.
    4
  3. c.
    7

Answer

C. 7
To solve, the two-ring solution is used twice, and there is one extra step to move the biggest ring from the source to the target. Each solution of two rings requires three steps each. So 3 + 1 + 3 = 7 steps total.

Concepts in Practice 12.1.6 §12.1 source ↗

How many total steps does it take to solve four rings?
  1. a.
    15
  2. b.
    7
  3. c.
    3

Answer

A. 15
The four-ring problem uses the three-ring solution twice. The three smaller rings are moved to the middle tower, taking seven steps as in question 2. One step is needed to move the biggest ring from the source to the target. It takes seven more steps move three smaller rings from the middle to the target. The total is 7 + 1 + 7 = 15 steps.

Concepts in Practice 12.2.1 §12.2 source ↗

Can the following algorithms be written recursively?

The summation of 1 + 2 + 3 + . . . + (n - 1) + n where n is a positive integer.

Answer

The summation can be calculated using recursion because there is a regular pattern and the summation to n depends on the summation to n - 1.

Concepts in Practice 12.2.2 §12.2 source ↗

Can the following algorithms be written recursively?

Listing the odd numbers greater than 0 and less than a given number n.

Answer

Each number in the sequence can be found by adding 2 to the previous number, with the solution at 1 being 1 .

Concepts in Practice 12.2.3 §12.2 source ↗

Can the following algorithms be written recursively?

Listing the primary numbers (prime numbers) greater than 3.

Answer

A prime number does not depend on a smaller prime number; thus, no recursion can be found to generate new prime numbers based on an existing list of prime numbers.

Concepts in Practice 12.2.4 §12.2 source ↗

Can the following algorithms be written recursively?

Listing the Fibonacci sequence of numbers.

Answer

A given number in the Fibonacci sequence is found by summing the previous two numbers in the sequence, so the Fibonacci sequence can be found recursively.

Concepts in Practice 12.2.5 §12.2 source ↗

For the questions below, the function rec_fact() is another recursive function that calculates a factorial. What is the result of each definition of rec_fact() if n = 17 is the initial input parameter?

def rec_fact(n):
  return n * rec_fact(n - 1)
  1. a.
    355687428096000
  2. b.
    0
  3. c.
    no result / infinite computation

Answer

C. no result / infinite computation
There is a missing base case, so there is no place for the recursion to end.

Concepts in Practice 12.2.6 §12.2 source ↗

For the questions below, the function rec_fact() is another recursive function that calculates a factorial. What is the result of each definition of rec_fact() if n = 17 is the initial input parameter?

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return n
  else:
    return n * rec_fact(n - 1)
  1. a.
    355687428096000
  2. b.
    0
  3. c.
    no result / infinite computation

Answer

B. 0
This definition of rec_fact() uses a base case of n == 0, which works because, just like 1!, 0! = 1. However, the base case of n == 0 returns n, which at this stage is 0 , and therefore zeroes out the rest of the computation.

Concepts in Practice 12.2.7 §12.2 source ↗

For the questions below, the function rec_fact() is another recursive function that calculates a factorial. What is the result of each definition of rec_fact() if n = 17 is the initial input parameter?

def rec_fact(n):
  if n < 0:
    print("error")
  elif n == 0:
    return 1
  else:
    return n * rec_fact(n - 1)
  1. a.
    355687428096000
  2. b.
    0
  3. c.
    no result / infinite computation

Answer

A. 355687428096000
The recursive function begins returning correctly at the base case of n == 0. 0! = 1.

Concepts in Practice 12.2.8 §12.2 source ↗

For the questions below, the function rec_fact() is another recursive function that calculates a factorial. What is the result of each definition of rec_fact() if n = 17 is the initial input parameter?

def rec_fact(n):
  if n < 0:
    return -1
  else:
    return n * rec_fact(n - 1)
  1. a.
    355687428096000
  2. b.
    0
  3. c.
    no result / infinite computation

Answer

B. 0
The base case of n == 1 is not used in the function. When n is 0 , the overall multiplication becomes 0 . The recursion begins returning once the n < 0 base case is reached, initially returning -1. But the previous recursive call would return 0 , thereby zeroing out all computations and leaving an overall result of 0 .

Concepts in Practice 12.3.1 §12.3 source ↗

Refer to the animation above.

Which of the following does palindrome() recognize as a palindrome?
  1. a.
    madamm
  2. b.
    madaM
  3. c.
    madame
Video · Identifying a palindrome in the book ↗

Answer

B. madaM
Once changed to all lower case, the word "madam" is a palindrome, so the function will recognize the word as a palindrome.

Concepts in Practice 12.3.2 §12.3 source ↗

Refer to the animation above.

What would happen if the condition on line 4 of palindrome() is changed to if len(word) == 1:
  1. a.
    Only palindromes with an odd number of letters would be recognized correctly.
  2. b.
    Nothing. The function would work the same.
  3. c.
    The function would not recognize any palindromes.
Video · Identifying a palindrome in the book ↗

Answer

A. Only palindromes with an odd number of letters would be recognized correctly.
When a palindrome has an even number of letters, eventually an empty string is left as pairs of letters are removed. Thus, the base case should include len(word) == 0, which is resolved with the condition len(word) <= 1.

Concepts in Practice 12.3.3 §12.3 source ↗

Refer to the animation above.

What would happen if the condition in line 8 palindrome() is changed to if palindrome(word.strip(word[0])).
  1. a.
    Nothing. The function would work the same: the first and last letter would be removed.
  2. b.
    Some words, such as "madamm", would be incorrectly recognized as a palindrome.
Video · Identifying a palindrome in the book ↗

Answer

B. Some words, such as "madamm", would be incorrectly recognized as a palindrome.
The strip() function removes a given letter from the beginning and end of the string, including repeated letters. When strip('m') is used with "madamm" , the resultant string is "ada" .

Concepts in Practice 12.3.4 §12.3 source ↗

Refer to the above animation. What would permu_check() return for each pair of lists below?

list_num = [1, 7, 99, 2]
other_list = [99, 7, 1, 2]
  1. a.
    True
  2. b.
    False
Video · Checking list permutations in the book ↗

Answer

A. True
Both lists have the same items in a different order.

Concepts in Practice 12.3.5 §12.3 source ↗

Refer to the above animation. What would permu_check() return for each pair of lists below?

list_num = [22, 9, 15, 17, 15]
other_list = [17, 9, 22, 22, 15]
  1. a.
    True
  2. b.
    False
Video · Checking list permutations in the book ↗

Answer

B. False
The two lists have four overlapping items, but list_num has an extra 15, and other_list has an extra 22.

Concepts in Practice 12.3.6 §12.3 source ↗

Refer to the above animation. What would permu_check() return for each pair of lists below?

honors_list = ["Bo", "Joe", "Sandy"]
first_names_of_team_1 = ["Sandy", "Bo", "Joe"]
  1. a.
    True
  2. b.
    False
Video · Checking list permutations in the book ↗

Answer

A. True
Both lists have the same items in a different order. The function works for items of any type.

Concepts in Practice 12.3.7 §12.3 source ↗

Refer to the above animation. What would permu_check() return for each pair of lists below?

this_list = [1, 2, [3], [4], 5]
that_list = [[3], 1, 5, [4], 2]
  1. a.
    True
  2. b.
    False
Video · Checking list permutations in the book ↗

Answer

A. True
Both lists have the same items in a different order. The function works for items of any type, including other lists.

Concepts in Practice 12.3.8 §12.3 source ↗

Refer to the above animation. What would permu_check() return for each pair of lists below?

list_1 = [1, 2, 3]
list_2 = [1, 2, 3]
  1. a.
    True
  2. b.
    False
Video · Checking list permutations in the book ↗

Answer

A. True
Both lists have the same items in the same order.

Concepts in Practice 12.4.1 §12.4 source ↗

fib(9) results in _____.
  1. a.
    13
  2. b.
    21
  3. c.
    34

Answer

C. 34
fib(9) = fib(8) + fib(7). fib(9) = fib(8) + fib(7) = 21 + 13 = 34.

Concepts in Practice 12.4.2 §12.4 source ↗

How many calls to the base cases are made as a result of calling fib(5)?
  1. a.
    2
  2. b.
    5
  3. c.
    8

Answer

C. 8
There are eight calls to base cases as seen in the animation. Those calls result in the recursion returning and the final value being computed.

Concepts in Practice 12.4.3 §12.4 source ↗

A structure tracing the function calls made as a result of a complex recursive function call is called a _____.
  1. a.
    tree
  2. b.
    recursion tree
  3. c.
    iteration tree

Answer

B. recursion tree
The structure that shows which function calls are made is called a recursion tree. A recursion tree can be used to trace how the final values are computed.

Concepts in Practice 12.4.4 §12.4 source ↗

What is the GCD of 15 and 35?
  1. a.
    15
  2. b.
    20
  3. c.
    5

Answer

C. 5
5 * 3 = 15 and 5 * 7 = 35, so 5 is a the greatest common divisor of 15 and 35 .

Concepts in Practice 12.4.5 §12.4 source ↗

How many recursive calls are made with gcd(24, 30)?
  1. a.
    4
  2. b.
    1
  3. c.
    24

Answer

A. 4
The first call gcd(24, 30) results in 30 - 24 = 6, so the next call is gcd(24, 6). Thereafter, other calls are gcd(18, 6), gcd(12, 6), and gcd (6,6) for a total of four recursive calls after the initial function call.

Concepts in Practice 12.4.6 §12.4 source ↗

What is the GCD of 13 and 23?
  1. a.
    13
  2. b.
    1
  3. c.
    23

Answer

B. 1
When the two numbers have no common divisors, the GCD is 1.

Concepts in Practice 12.4.7 §12.4 source ↗

How many recursive calls are made with gcd(13, 23)?
  1. a.
    1
  2. b.
    8
  3. c.
    13

Answer

B. 8
The first call gcd(13, 23) results in 23 - 13 = 10, so the next call is gcd(13, 10). Thereafter, other calls are gcd(10, 3), gcd(7, 3), gcd (4,3), gcd(3,2), gcd(2,1), and gcd(1,1) for a total of eight calls.

Concepts in Practice 12.5.1 §12.5 source ↗

Which list can be searched with the binary search algorithm?
  1. a.
    [5, 2, 7, 1, 8]
  2. b.
    [9, 8, 7, 6, 5]
  3. c.
    [4, 5, 6, 7, 8]

Answer

C. [4, 5, 6, 7, 8]
This array is sorted in ascending order, as is required for using the binary search algorithm.

Concepts in Practice 12.5.2 §12.5 source ↗

If the binary_search() function is called with low = 4, and high = 7, mid computes to _____.
  1. a.
    5
  2. b.
    6
  3. c.
    11

Answer

A. 5
mid = (4 + 7) // 2 = 11 // 2 = 5. The operator // is used for floor division.

Concepts in Practice 12.5.3 §12.5 source ↗

How many calls to the binary_search() function occur in the animation?
  1. a.
    3
  2. b.
    4
  3. c.
    8
Video · Binary search in the book ↗

Answer

A. 3
The first call results in mid being 3 , next mid becomes 5 , and finally, mid becomes 4 . The element found at index 4 is equal to the key 16 .

Concepts in Practice 12.5.4 §12.5 source ↗

How many calls to the binary_search() function occur in the code example when searching 86?
  1. a.
    4
  2. b.
    14

Answer

A. 4
The first call results in mid being (0 + 13) // 2 = 6. The next call has mid (7 + 13) // 2 = 10. The next call has mid (11 + 13) // 2 = 12. At this point, 86 < 99, so the final call is to mid 11, after which there is nowhere else to go.

Concepts in Practice 12.5.5 §12.5 source ↗

For four rings, how many total lines will be printed by three_towers()?
  1. a.
    7
  2. b.
    15

Answer

B. 15
As seen in the code example for three rings, the solution requires seven steps. The seven steps are called twice, along with one additional step, for a total of 2 x 7 + 1 = 15.

Concepts in Practice 12.5.6 §12.5 source ↗

Would an iterative solution to the Three Towers problem be more complex or less complex?
  1. a.
    more complex
  2. b.
    less complex

Answer

A. more complex
The iterative solution to Three Towers requires significantly more code and uses additional programming capabilities.

Loading chapter 13…

Problems and answers are adapted from Introduction to Python Programming by Udayan Das, Aubrey Lawson, Chris Mayfield and Narges Norouzi, OpenStax, and are used under the CC BY-NC-SA 4.0 licence. Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction. Illustrations: Copyright Rice University, OpenStax, under CC BY-NC-SA 4.0 license. This adaptation is released under the same licence, is non-commercial, and is neither affiliated with nor endorsed by OpenStax or Rice University.