# CS 51 Prep Workshop: Recursion Solutions

Welcome! To start coding, press Duplicate.

This platform is called Deepnote, and it allows you to edit and run Python online. We'll be using it to avoid needing to install software.

Note that CS 51 uses OCaml, not Python, but the concepts will be similar.

You can run Deepnote cells one at a time by selecting the cell and typing ⌘ Enter (Ctrl Enter on Windows). Try it below!

### Exercise 1.1: Write a function `length`

that recursively determines the length of a list.

For this problem, assume that the list can be of any type.

Example behavior:

```
length([2, 7, 5, 1, 3]) = 5
length([]) = 0
length([[], [1, 2], [5, 7]]) = 3
length(["this", "is", "a", "list", "of", "strings"]) = 6
```

**Hint:** This problem is similar to the movie theater example we covered earlier.

- If there’s no one in front of you, you’re in row 1.
- Otherwise, "call on" the person in front of you and add 1 to their answer.

How can you use this similarity to write a function for `length`

?

Complete the function below.

### Solution 1.1

The smallest unit of a list is the empty list. If `lst == []`

, you know the length is 0.

Here, we're trying to process the input `lst`

one element at a time. So, pretend that you only know about the first element.
If the list is not empty, you know that the length of the entire of the list is `1 + length(remainder of lst)`

, which in Python is expressed as `lst[1:]`

.

It's helpful to use an example. Let's say that you're given the list `[1, 2, 3, 4, 5]`

. You can figure out the length of this list by solving for the length of a smaller list, `[2, 3, 4, 5]`

and adding `1`

to that answer.
In the movie theater example, you were trying to figure out which row you were in, so you asked the person in front of you and added one to their answer. "Asking the person in front of you" is equivalent to making the recursive call.

We recommend testing your code on a variety of inputs to make sure it works. You can run tests in the cell below.

Note: Python has its own length function, `len`

. You can verify that your recursive `length`

function returns the same answer as Python's built-in function.

### Exercise 1.2: Write a function `row_joe`

that takes in a list of names and returns which position "Joe" is in.

If Joe is nowere to be found, return `None`

.

We assume that all elements in the list are strings, and there is at most one "Joe."

Example behavior:

```
row_joe(["Ben", "Melissa", "Brian", "Joe"]) = 4
row_joe(["Ben", "Joe", "Brian", "Melissa"]) = 2
row_joe(["Ben", "Stuart", "Brian", "Melissa"]) = None
```

Complete the `row_joe`

function below.

**Hint**: There are two possible outcomes: you either find Joe or reach the end of the list without finding Joe. How can you modify the base case of the `length`

function you wrote to account for these cases?

### Solution 1.2

`row_joe`

is quite similar to `length`

: it's asking you to find the length of a list up to and including the element "Joe."

First, let's handle the base cases.

- If the list is empty, Joe is not present, so we return
`None`

. - If the first element of the list is "Joe", then "Joe" is in row 1.

The tricky part here is the recursive call. We first set `row = row_joe(lst[1:])`

.

- If Joe is found,
`row`

will be equal to Joe's row number*relative to the person behind you*. To figure out his row*relative to you*, you need to add 1. - If Joe is not present,
`row`

will be`None`

. If the person behind you can't find Joe, then it follows that you won't be able to find Joe either. So you return`None`

.

The solution presented during the bootcamp was incorrect (sorry!). Hope this clarification helps.

Finally, note that we're trying to minimize the number of recursive calls, which why we set `row_joe(lst[1:])`

to a variable.

```
# Bad - makes multiple recursive calls for the same thing
return 1 + row_joe(lst[1:]) if row_joe(lst[1:]) else None
# Better - stores the result of the recursive calls
row = row_joe(lst[1:])
return 1 + row if row else None
```

### Exercise 1.3: Write a function `num_even_elements`

that recursively counts the number of even elements in a list.

In this case, we assume that all elements in the list are integers. Example behavior:

```
num_even_elements([2, 7, 5, 1, 3]) = 1
num_even_elements([]) = 0
num_even_elements([2, 4, 6, 8]) = 4
```

### Solution 1.3

Again, our base case is going to be the empty list: if we're calling `num_even_elements`

on an empty list, there are going to be 0 even elements!
We're going to handle the first element and let recursion do the rest. If the first element is even, the *total* number of even elements is `1 + the number of even numbers in the rest of the list`

.
If the first element is odd, it's not contributing any even elements to our final count. So the total number of even elements is just the number of even numbers in the rest of the list.

One concise way of expressing this conditional is to set an `increment`

variable that equals 1 if the first element is even and 0 otherwise.

Then, we make the recursive call by adding increment to the result of `num_even_elements`

on the rest of the list.

### Exercise 2: Write a function `merge_sort`

that recursively sorts a list according to the following pseudocode.

- Divide the input array into two subarrays of roughly equal size.
- Recursively mergesort each of the subarrays.
- Merge the newly-sorted subarrays into a single sorted array.

You'll first need to write a function `merge`

that takes two **sorted** lists as input and returns a merged list.

Example behavior:

```
merge([2, 5, 6], [1, 6, 8, 11, 20]) = [1, 2, 5, 6, 6, 8, 11, 20]
merge([], [1, 7, 8]) = [1, 7, 8]
merge([], []) = []
```

Complete the `merge`

function below:

### Solution 2.1

We're presenting the iterative solution, not the recursive solution, because `merge`

is in PSET 1 and we didn't want to give away the answer!
But if you did implement the recursive version, you might have noticed that it's more elegant than the iterative version.

Once you get `merge`

working, you can now write `merge_sort`

according to the recursive instructions above.

Example behavior:

```
merge_sort([]) = []
merge_sort([8]) = [8]
merge_sort([17, 3]) = [3, 17]
merge_sort([1, 5, 2, 7, 3, 7, 4, 9]) = [1, 2, 3, 4, 5, 7, 7, 9]
```

**Tip:** when you recursively call `merge_sort`

on the smaller lists, you don't need to worry about how the smaller lists are getting sorted. If it's helpful, you can simply assume that the "Recursion Fairy" returns the sorted sublists, and it's up to you to merge them together.

**Hint:** What is the base case for merge sort? When can we stop dividing the list into smaller chunks?

**Hint**: In the previous exercises, you made a recursive call on *one* smaller sublist (namely, the sublist that included all but the first element). In this exercise, you'll need to make recursive calls on *two* smaller sublists.

### Solution 2.2

If a list has 0 or 1 elements, it is already sorted. This is our base case: the problem that we can solve directly.

If the problem cannot be solved directly, we "divide and conquer" — call `merge_sort`

on the two halves of the list individually and then `merge`

the two together.

# Congratulations! 🥳

We'll be going over solutions in the main room. If you want, you can attempt the **optional** challenge problem, which uses recursion but is outside the scope of CS 51.

### Challenge Problem 1: Inversions in an array

An inversion in an array `A[1 .. n]`

is a pair of indices `(i, j)`

such that `i < j`

and
`A[i] > A[j]`

. In other words, the number of inversions is the number of element pairs that are "out of order." The number of inversions in an n-element array is between 0 (if the array is sorted) and $n \choose 2$ (if the array is sorted backward).

Expected behavior:

```
inversions([]) = 0
inversions([5, 1]) = 1
inversions([5, 1, 4]) = 2
inversions([0, 1, 2, 3]) = 0
```

Write the function `inversions`

to recursively count the number of inversions in an array.

**Hint**: This problem has a very similar structure to `merge_sort`

. To see why, examine the two sorted lists `[1, 4, 5, 7]`

and `[2, 3, 6]`

. How many inversions do you get purely from merging the two sorted lists together?

### Challenge Problem Solution

To start, let's unpack the hint.

When we put `[1, 4, 5, 7]`

and `[2, 3, 6]`

together, we get `[1, 4, 5, 7, 2, 3, 6]`

. Note that `[1, 4, 5, 7]`

and `[2, 3, 6]`

are both sorted, so each of the sub-lists have 0 inversions.

When we merge `[1, 4, 5, 7]`

and `[2, 3, 6]`

, we can count the number of inversions in `[1, 4, 5, 7, 2, 3, 6]`

as follows:

Result | Remaining lists | New inversions |
---|---|---|

`[]` | `[1, 4, 5, 7]` and `[2, 3, 6]` | 0 |

`[1]` | `[4, 5, 7]` and `[2, 3, 6]` | 0 (1 is the minimum. Since it's on the left, it's already at the front of the list.) |

`[1, 2]` | `[4, 5, 7]` and `[3, 6]` | 3 (2 has inversions with 4, 5, and 7) |

`[1, 2, 3]` | `[4, 5, 7]` and `[6]` | 3 (3 has inversions with 4, 5, and 7) |

`[1, 2, 3, 4]` | `[5, 7]` and `[6]` | 0 |

`[1, 2, 3, 4, 5]` | `[7]` and `[6]` | 0 |

`[1, 2, 3, 4, 5, 6]` | `[7]` and `[]` | 1 (6 has an inversion with 7) |

`[1, 2, 3, 4, 5, 6, 7]` | `[]` and `[]` | 0 |

The total number of inversions in `[1, 4, 5, 7, 2, 3, 6]`

is $0 + 0 + 3 + 3 + 0 + 0 + 1 + 0 = \boxed{7}$. Since the two halves are already sorted, the minimum of the list will either be the first element of the left list or the first element of the right list.

If the minimum overall element comes from the left list, it's already in the right place. Thus, it provides 0 new inversions. If we take an element from the right list, that means that the minimum overall element has inversions with *all* of the remaining elements in the left list.

Thus, our algorithm works like this:

- If the list has zero or one elements, it has 0 inversions.
- Otherwise, split the list in half (or nearly half, if it has an odd number of elements). The total number inversions equals the inversions within the left side + inversions within the right side + inversions from merging the two together.

In `merge_inversions`

, we use Python's `pop`

method to remove the first element from the array because it's more readable than using indices.