# Exercises (CT Chapter 7)

I don’t really have a lot of exercises for the chapter on recursion. I had planned to combine recursion with divide-and-conquer, but now the two topics are split over two weeks. Instead, I will have a project for the students to do while they learn about recursion; then it doesn’t matter so much that there are not that many exercises.

Anyway, exercises below and answers below that.

# Exercises

## Fibonacci

**Exercise:** Implement a recursive function that computes the n’th Fibonacci number.

**Exercise:** Draw the call stack for computing the fourth Fibonacci number using the implementation you did in the previous exercise.

## List exercises

**Exercise:** To compute the sum of the elements in a list, we can obviously do this iteratively:

```
result = 0
for e in x:
result += e
```

Implement a recursive function that computes the sum of the elements of a list.

**Exercise:** We can find the smallest element in a non-empty list, `x`

, like this:

```
smallest = x[0]
for e in x:
smallest = min(smallest, e)
```

Write a recursive function for finding the smallest element in a list. To avoid copying the list using slices, you will want to have the function take an index parameter as an argument.

**Exercise:** Modify your function, so it returns `None`

if the list is empty. The easiest way to do this is probably to include the “smallest element seen so far” as a parameter to the function, with a default value of `None`

. To compute the smallest value and still handle `None`

you can use this function:

```
def my_min(x, y):
return y if x is None else min(x, y)
```

**Exercise:** Write a recursive function that reverses a list.

**Exercise:** Recall the exercise where you had to translate a base-10 number into some other base b (where we restricted the base to be less than 16). We can get the last digit of a number i, in base b using this function:

```
def get_last_digit(i, b):
return digits[i % b]
```

where we defined the `digits`

list as

```
digits = {}
for i in range(0,10):
digits[i] = str(i)
digits[10] = 'A'
digits[11] = 'B'
digits[12] = 'C'
digits[13] = 'D'
digits[14] = 'E'
digits[15] = 'F'
```

We can then reduce the problem to the second-to-last digit by dividing i by b. Implement this idea using a recursive function.

## Tail-Recursion

**Exercise:** Rewrite your recursive function for computing the sum of a list of numbers such that it becomes tail-recursive.

**Exercise:** Rewrite your recursive function for finding the smallest element in a list to a version that is tail-recursive.

**Exercise:** Do the tail-recursion transformation for your tail-recursive summation function.

**Exercise:** Do the tail-recursion transformation for your tail-recursive “find minimum” function.

**Exercise:** Consider our recursive implementation of binary search:

```
def bsearch(x, e, low = 0, high = len(x)):
if low >= high:
return False
mid = (low + high) // 2
if x[mid] == e:
return True
elif x[mid] < e:
return bsearch(x, e, mid + 1, high)
else:
return bsearch(x, e, low, mid)
```

This function is tail-recursive, so use the transformation to replace it with a loop. Compare it to the iterative solution we considered before this chapter.

# Answers

## Fibonacci

**Exercise:** Implement a recursive function that computes the n’th Fibonacci number.

```
def Fib(n):
if n <= 2: return 1
else: return Fib(n - 1) + Fib(n - 2)
```

**Exercise:** Draw the call stack for computing the fourth Fibonacci number using the implementation you did in the previous exercise.

## List exercises

**Exercise:** To compute the sum of the elements in a list, we can obviously do this iteratively:

```
result = 0
for e in x:
result += e
```

Implement a recursive function that computes the sum of the elements of a list.

```
def recsum(x):
if x == []: return 0
else: return x[0] + recsum(x[1:])
```

**Exercise:** We can find the smallest element in a non-empty list, `x`

, like this:

```
smallest = x[0]
for e in x:
smallest = min(smallest, e)
```

Write a recursive function for finding the smallest element in a list. To avoid copying the list using slices, you will want to have the function take an index parameter as an argument.

```
def min_rec(x, i = 0, acc = None):
if i == len(x): return acc
acc = x[i] if acc is None else min(acc, x[i])
return min_rec(x, i + 1, acc)
```

**Exercise:** Modify your function, so it returns `None`

if the list is empty. The easiest way to do this is probably to include the “smallest element seen so far” as a parameter to the function, with a default value of `None`

. To compute the smallest value and still handle `None`

you can use this function:

```
def my_min(x, y):
return y if x is None else min(x, y)
```

My solution from above already works this way.

**Exercise:** Write a recursive function that reverses a list.

```
def reverse_rec(x, acc = []):
if x == []: return acc
return reverse_rec(x[1:], [x[0]] + acc)
```

This implementation is very inefficient due to how Python lists are implemented. It would be very efficient if we used linked lists. With array-like vectors, we wouldn’t usually need recursion—it is easier to solve that reversal problem iteratively.

**Exercise:** Recall the exercise where you had to translate a base-10 number into some other base b (where we restricted the base to be less than 16). We can get the last digit of a number i, in base b using this function:

```
def get_last_digit(i, b):
return digits[i % b]
```

where we defined the `digits`

list as

```
digits = {}
for i in range(0,10):
digits[i] = str(i)
digits[10] = 'A'
digits[11] = 'B'
digits[12] = 'C'
digits[13] = 'D'
digits[14] = 'E'
digits[15] = 'F'
```

We can then reduce the problem to the second-to-last digit by dividing i by b. Implement this idea using a recursive function.

```
def to_base(n, b, rev_digits = None):
# get an empty list if argument is None
rev_digits = rev_digits or []
if n == 0:
if rev_digits == []: return "0"
return "".join(reversed(rev_digits))
else:
rev_digits.append(digits[n % b])
return to_base(n // b, b, rev_digits)
```

## Tail-Recursion

**Exercise:** Rewrite your recursive function for computing the sum of a list of numbers such that it becomes tail-recursive.

```
def recsum_tr(x, acc = 0):
if x == []: return acc
else: return recsum_tr(x[1:], acc + x[0])
```

**Exercise:** Rewrite your recursive function for finding the smallest element in a list to a version that is tail-recursive.

```
def min_rec(x, i = 0, acc = None):
if i == len(x): return acc
acc = x[i] if acc is None else min(acc, x[i])
return min_rec(x, i + 1, acc)
```

**Exercise:** Do the tail-recursion transformation for your tail-recursive summation function.

```
def recsum_tr(x, acc = 0):
while True:
if x == []: return acc
x, acc = x[1:], acc + x[0]
```

**Exercise:** Do the tail-recursion transformation for your tail-recursive “find minimum” function.

```
def min_rec(x, i = 0, acc = None):
while True:
if i == len(x): return acc
acc = x[i] if acc is None else min(acc, x[i])
i += 1
```

**Exercise:** Consider our recursive implementation of binary search:

```
def bsearch(x, e, low = 0, high = len(x)):
if low >= high:
return False
mid = (low + high) // 2
if x[mid] == e:
return True
elif x[mid] < e:
return bsearch(x, e, mid + 1, high)
else:
return bsearch(x, e, low, mid)
```

This function is tail-recursive, so use the transformation to replace it with a loop. Compare it to the iterative solution we considered before this chapter.

The direct translation is this:

```
def bsearch(x, e, low = 0, high = len(x)):
while True:
if low >= high:
return False
mid = (low + high) // 2
if x[mid] == e:
return True
elif x[mid] < e:
return bsearch(x, e, mid + 1, high)
else:
return bsearch(x, e, low, mid)
```

If we just change the loop condition we get the usual function:

```
def bsearch(x, e, low = 0, high = len(x)):
while low < high:
mid = (low + high) // 2
if x[mid] == e:
return True
elif x[mid] < e:
return bsearch(x, e, mid + 1, high)
else:
return bsearch(x, e, low, mid)
return False
```