16.11: Chapter 12

12.1 Recursion basics

1. a. 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.

2. b. The two-ring solution from question 1 is used in the solution for three rings.

3. b. Once to move two rings to the middle tower following the rules, then to move two rings to the target tower.

4. c. 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.

5. c. 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.

6. a. 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.

12.2 Simple math recursion

1. 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.

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

3. 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.

4. 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.

5. c. There is a missing base case, so there is no place for the recursion to end.

6. b. 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.

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

8. b. 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 .

12.3 Recursion with strings and lists

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

2. a. 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.

3. b. 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" .

4. a. Both lists have the same items in a different order.

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

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

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

8. a. Both lists have the same items in the same order.

12.4 More math recursion

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

2. c. 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.

3. b. 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.

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

5. a. 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.

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

7. b. 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.

12.5 Using recursion to solve problems

1. c. This array is sorted in ascending order, as is required for using the binary search algorithm.

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

3. a. 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 .

4. a. 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.

5. b. 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.

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