Tutorial 11: Recursion 101

Exercise 1: Greatest common divisor

Remember from your math classes that the greatest common divisor gcd(a, b) of two non-negative integers a and b is the greatest integer that divides both a and b. In principle, we could compute gcd(a, b) by going over all positive integers smaller than a and b and testing if they divide both numbers. But it is obvious that when a and b are big, then this will be terribly inefficient.

Fortunately, it has been known for more than two thousand years that there is a more efficient way of computing gcd(a, b). This algorithm relies on two observations:

1. For all non-negative integers x we have gcd(x, 0) = gcd(0, x) = x.
2. For all positive integers x and y we have gcd(x, y) = gcd(y, x mod y) (where x mod y is the remainder when dividing x by y).

Write a function gcd(x, y) that turns the two observations above into a recursive algorithm.

Test your function:

In [0]: gcd(2, 5)
Out[0]: 1

In [0]: gcd(28, 12)
Out[0]: 4

In [1]: gcd(217190401, 216144349)
Out[1]: 593

Upload your file recursion.py:

Exercise 2: Palindromes

A palindrome is a string (or word) that is the same read from the front and from the back. For example, 'ANNA' is a palindrome, as are 'ANA' and 'OTTO'. In contrast, 'DAVE', 'MARIA' and 'BLARB' are not palindromes. On the other hand, both '' (the empty string) and 'A' are palindromes.

In this exercise, we will write a function is_palindrome() that checks if a given word is a palindrome. Your function should begin as follows:

def is_palindrome(word):
    """Check if input is a palindrome."""

The function is_palindrome(word) should return True if and only if word is a palindrome. The idea for a recursive test for being a palindrome is simple: a word is a palindrome if and only if it has the same letter at the beginning and at the end, and if the sub-word that we get by omitting the first and last of its letters is also a palindrome.

Test your function, for example as follows:

In [1]: is_palindrome('ABBA')
Out[1]: True

In [2]: is_palindrome('ABA')
Out[2]: True

In [3]: is_palindrome('ABAB')
Out[3]: False

Upload your file recursion.py:

Exercise 3: Recursive powering

Assume that you would like to compute a large power of an integer, say 2¹⁰⁰⁰. One was to do this would be to multiply 2 by itself 999 times. This will require 999 multiplication. Can we do better? Yes, we can use 499 multiplications to compute 2⁵⁰⁰ and then get 2¹⁰⁰⁰ with a single multiplication. We can continue this line of reasoning and compute 2⁵⁰⁰ from 2²⁵⁰, from 2¹²⁵, etc.

Based on this, we propose the following algorithm from computing a^b:

1. if b == 0 or b == 1, return the result,
2. if b is even, compute a^b/2 and square it,
3. if b is odd, compute a^{(b - 1)/2}, square, and multiply by a.

You can see, that this algorithm is naturally recursive since it uses smaller powers to compute the larger ones. Implement this algorithm by completing the function rec_pow below:

def rec_pow(a, b):
    """Compute a**b recursively"""
    if b == 0:
        pass # your code here
    if b == 1:
        pass # your code here
    if b % 2 == 0:
        pass # your code here
    # your code here 

Test your function:

In [4]: rec_pow(2, 3)
Out[4]: 8

In [5]: rec_pow(2, 9)
Out[5]: 512

In [6]: rec_pow(3, 100)
Out[6]: 515377520732011331036461129765621272702107522001

Upload your file recursion.py:

Remark: A natural variation of the algorithm above would be to compute and multiply a^{(b - 1)/2} and a^{(b + 1)/2} in the case of odd b. However, this is not really a good idea in terms of efficiency. Why?

Interlude: Some dangers of recursion

Recursion is a very popular concept in particular in more theoretical parts of computer science, because it allows to express algorithms in a very concise and elegant way. In practice however, there are some problems that often appear…

Consider the following little toy function that decides if a given number is even.

def even(n):
    """Return True if and only if the given number is even."""
    if n == 0:
        return True
    if n == 1:
        return False
    return even(n-2)

Stack limits

Copy the function even() above to your file recursion.py. Then run it on the console for example as follows:

In [7]: even(0)
Out[7]: True

In [8]: even(10)
Out[8]: True

In [9]: even(1)
Out[9]: False

In [10]: even(100)
Out[10]: True

In [11]: even(101)
Out[11]: False

In [12]: even(10000)

The last call should give you a long error message that ends similar to

...
RecursionError: maximum recursion depth exceeded in comparison

To understand what the problem is here, we have to think about how recursion works on the computer: whenever a function is called, Python remembers that call until the function executes a return statement. These calls are remembered in an area of the memory that is called the stack, because when one function calls another, the two calls are stacked on another.

In a recursive function, for each function call that has not yet finished, the stack contains some information on that call. For example, when we call even(1000) the stack should at some point contain information on even(1000), even(998), even(996) and so on, all the way down to even(0). Unfortunately, the space on the stack is limited! To avoid this space from filling up too much, Python has a limit on how deep a recursion can be before causing an error such as the one we see above.

In Python, there are only two ways around this problem: make sure that the function is only called on inputs where you know that the stack never contains too many recursive calls (for example, when calling even() only for numbers up to 1000, everything should be fine). The only other solution is to avoid recursion altogether when the recursion depth would be too big and instead work with loops.

We can also modify the depth of recursion that Python will allow. For example, we can decrease the allowed depth to only 120 recursive calls by adding the following lines to the top of recursion.py:

import sys
sys.setrecursionlimit(120)

We recommend that you add these lines now. Otherwise, the error messages of problematic programs often become to long to find errors efficiently.

Termination

To illustrate another problem you might encounter, run even(-2). You should again get an error message telling you that you have reached the recursion limit. This time the problem is a little different than before: the problem is not that the space required to compute the result is too big, but rather that the recursion for input -2 never reaches a base case of the recursion. If there was no limit on the recursion depth, then the recursion would never terminate and the program would go into an infinite loop.

To avoid this type of problem, it is important to make sure that for every possible input the recursion will terminate eventually. For the function even() this is relatively straightforward to do, but for more complex recursions this is sometimes highly non-trivial.

Exercise 4: Binary search

Implementation

One very important operation that is performed in many applications is finding an element in a list. As was already discussed when sets were introduced in this course, generally this problem requires one to go over all elements in the list.

An important special case is that of ordered data, i.e., the case in which the elements in the list are ordered with respect to some order. If this is the case, we can proceed as follows:

• If the list contains just one element, we make a direct comparison and are done afterwards.
• Otherwise, we compare the element e that we are looking for with the element m in the middle of the list.
  • If e and m are equal, we have found e in the list and we are done.
  • If m is greater than e, then e must be in the first half of the list (if it appears at all) and thus we can recursively look for it there.
  • Otherwise, e must appear in the second half of the list (if it appears at all) and thus we can perform recursion on the second half.

The algorithm that we described above is called binary search and is one of the most fundamental algorithms. It is the first instantiation of the divide and conquer algorithm design principle, where one solves a problem by cutting it into smaller subproblems that can then be solved more easily.

Implement binary search by writing the following function:

def binary_search(sorted_list, lower, upper, element):
    """Return the position of the element in the sublist of sorted_list
    starting at position lower up to (but excluding) position upper 
    if it appears there. Otherwise return -1.
    """

Afterwards, test your function for example as follows (note that strings can be compared exactly as numbers; for the comparisons the lexicographical order is used):

In [13]: s = ['b', 'c', 'd', 'f', 'g', 'h']

In [14]: binary_search(s, 0, 6, 'd')
Out[14]: 2

In [15]: binary_search(s, 0, 6, 'b')
Out[15]: 0

In [16]: binary_search(s, 0, 6, 'h')
Out[16]: 5

In [17]: binary_search(s, 0, 3, 'h')
Out[17]: -1

In [18]: binary_search(s, 0, 6, 'e')
Out[18]: -1

In [19]: binary_search(s, 0, 6, 'a')
Out[19]: -1

In [20]: binary_search(s, 0, 6, 'z')
Out[20]: -1

Upload your file recursion.py:

Performance tests

Recall that Python lists have a .index() method, which computes essentially the same thing as binary_search: if l is a list, then

• l.index(x) finds the index of (the first occurrence of) x in l;
• binary_search(l, x, 0, len(l)) finds the index of x in l.

Testing membership is similar. We know that x in l returns True if x is in l, and False if it is not; but we could also use binary_search(l, x, 0, len(l)) != -1 to get exactly the same result.

Why would we bother writing and using binary_search, rather than just using index and in? The answer is that on large sorted lists, binary_search can compute the index much faster. The index method and the in operator do not know, and cannot take advantage of, the fact that the data is sorted; they are obliged to plod linearly through the list, inspecting every single element until they find the one they are looking for. In contrast, binary_search can use the fact that the data is sorted to quickly zoom in towards the position where the required element should be found.

To test whether binary search really is faster than the in operator, we use the module timeit that can be used to call a function several times and measure the time it needs to run.

We start by importing the timeit module:

In [21]: import timeit

To have some benchmark instances, we create sorted random lists of integers using the following function, which you should copy into your recursion.py file.

import random

def random_increasing_integer_sequence(length):
    """Return an increasing list of integers of the given length."""
    current = 0
    res = []
    for i in range(length):
        current += random.randint(1, 10)
        res.append(current)
    return res

Now we can test the performance of our function:

In [22]: s = random_increasing_integer_sequence(20000)

In [23]: 10000 in s
Out[23]: False

In [24]: timeit.timeit('10000 in s', number=10000, globals=globals())
Out[24]: 2.6033250330074225

In [25]: timeit.timeit('binary_search(s, 0, len(s), 10000)', number=10000, globals=globals())
Out[25]: 0.055350435999571346

(You might get slightly different results, but the speed difference should be clear.)

Each of our calls of timeit.timeit executes the given statement 10000 times (that’s what the number=10000 argument does). The returned value is the total time (in seconds) that these executions took. You should see that your binary_search outperforms the standard list lookup easily. If not, you should check if you have implemented the right algorithm.

The function binary_search that we have just written not only allows to look for integers but also for all other objects that can be ordered in Python. To illustrate this, copy the following function to your file:

def pp_words():
    with open('sortedpp.txt') as file:
        return [w.strip() for w in file]

The function pp_words returns a list containing all words that appear in Pride and Prejudice in lexicographic order. Test your function binary_search for this input as well:

In [26]: s = pp_words()

In [27]: timeit.timeit('"TELEVISION" in s', number= 40000, globals = globals())
Out[27]: 2.9767137309972895

In [28]: timeit.timeit('binary_search(s, 0, len(s)-1, "TELEVISION")', number= 40000, globals = globals())
Out[28]: 0.19482769099704456

Pride and prejudice, being from the 19th century, predates television; so searching for the word “TELEVISION” in the text represents a worst-case search.

Exercise 5: Generating subsets

Our goal in this exercise would be to list all the subsets of a given set. For example, if the input set was {1, 2, 3}, the algorithm is expected to return {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} (in some order). One can do this recursively as follows: 1. take any element of the set (for example, 1) 2. using a recursive call, compute the subsets of the set without the chosen element (in the example, {}, {2}, {3}, {2, 3}) 3. for each computed subset S, append to the final result both S and a copy of S with 1 added (for example, {2, 3} would yield both {2, 3} and {1, 2, 3}).

Implement this approach in the function find_subsets, we give a starter code below

def find_subsets(s):
    """Return a list of all the sub sets of set `s`
    (in any order)
    """
    if len(s) == 0:
        return [set()]
    # to use `copy` function, add `from copy import copy` at the beginning of your file
    s_copy = copy(s)
    elem = s_copy.pop()
    result = find_subsets(s_copy)
    ...

You can test your function by typing

In [29]: find_subsets(set())
Our[29]: [set()]

In [30]: find_subsets({1, 2})
Out[30]: [set(), {2}, {1}, {1, 2}]

In [31]: find_subsets({4, 5, 6})
Out[31]: [set(), {6}, {5}, {5, 6}, {4}, {4, 6}, {4, 5}, {4, 5, 6}]

Upload your file recursion.py:

Exercise 6: Generating permutations

Now we will write a function to find all permutations of several distinct objects. For example, if the input list was [1, 2, 3], the algorithm is expected to return [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] (in some order). One can do this recursively as follows:

1. take any element of the set (for example, 1)
2. using a recursive call, compute the permutations of the list without the chosen element (in the example, [2, 3], [3, 2])
3. for each computed permutation P, add the element 1 at all possible positions and append such permutations to the final result. For example, 1 and [2, 3] would yield [1, 2, 3], [2, 1, 3] and [2, 3, 1].

Implement this approach in the function find_permutations.

def find_permutations(arr):
    """Return a list of all the permutations of the list arr."""
    ...

You can test your function by typing

In [32]: find_permutations([])
Out[32]: [[]]

In [33]: find_permutations([1, 2])
Out[33]: [[2, 1], [1, 2]]

In [34]: find_permutations(['a', 'b', 'c'])
Out[34]: [['c', 'b', 'a'], ['b', 'c', 'a'], ['b', 'a', 'c'], ['c', 'a', 'b'], ['a', 'c', 'b'], ['a', 'b', 'c']]

Upload your file recursion.py:

Exercise 7: Finding acronyms

For given phrase, say How are you, we will call an acronym a word formed by taking one letter from each of the words in the phrase (letters are taken in the same order as the words in the phrase). For example, we can obtain HEY as How arE You. Our goal will be to write a function taking as input a phrase and a dictionary of legible words and returning a set of all possible acronyms.

We will do this by writing a recursive function find_acronyms_rec(phrase_words, prefix, word_list) where phrase_words is a list of words, prefix is a string, and word_list is a list of words. The function should return all the words from word_list which start with a prefix followed by an acronym of the phrase formed by phrase_words. The idea is that, on each step, we choose all possible first letters of the acronym from the first word, and run recursively on the remaining phrase. To give some intuition, let us apply this strategy to our example.

1. We start with prefix = '' and phrase_words = ["how", "are", "you"].
2. The first letter in the sought acronym must come from the word "how", so there are three options: 'h', 'o', and 'w'.
3. For each of the three options, we want to complement the chosen letter with an acronym for ["are", "you"], so we run the function find_acronyms_rec recursively three times setting prefix to be "h", "o", and "w", phrase_words to be ["are", "you"], and dictionary to be the same as before, and then we take a union of the results.
4. At the bottom level of the recursion, we will arrive at a situation when prefix is a three-letter word and pharse_words is an empty list, so it will remain to check if prefix appears in dictionary.

For convenience, this recursive function will be wrapped into a non-recursive one as follows:

def find_acronyms(phrase, word_list):
    """Find each word in word_list that can be constructed
    by taking one letter from each word in phrase, in order.
    """
    return find_acronyms_rec(phrase.split(), '', word_list)

def find_acronyms_rec(phrase_words, prefix, word_list): 
    pass

We will use the following function to load a list of words (for example, this one):

def load_dictionary(filename):
    with open(filename, 'r') as f:
        words = [line.strip() for line in f]
        return words

Once you complete find_recursive_rec, you can test your code:

In [35]: words = load_dictionary("wordlist.txt")

In [35]: find_acronyms('how are you', words)
Out[35]: {'way', 'hay', 'wry', 'hao', 'hey', 'oro'}

In [36]: find_acronyms('per aspera ad astra', words)
Out[36]: {'erat', 'peat', 'rear', 'peas', 'pear'}

Upload your file recursion.py:

Remark that, if word_list is sorted, you can speed up the computation by using the binary search function you have implemented before.