# Mailund on the Internet

On Writing, Science, Programming and more

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

## 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])


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