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

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.

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.
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"
```

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

## 12.4 More math recursion

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.

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

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.