Five Minute Introduction: Recursion

Along with iteration, recursion is one of the basic principals of software engineering. It can be a graceful solution to problems, but it's often misunderstood and it can have practical disadvantages.

In computer science, a recursive function is one that calls itself. At first this seems like an odd thing to want to do, but by doing this you can reduce the complexity of your original function. For example, calculating the factorial of a number.

The factorial function is:

    n! = 1 * 2 * 3 * ... * (n - 2) * (n - 1) * n
       = Prod(1..n)

It's simple to calculate this iteratively in a function:

def factorial_iterative(value: int) -> int:
    return prod(range(1, value + 1))

Or you can express the definition slightly differently:

    n! = n * (n - 1)! where n > 1, and 1! = 1

Because there is now a factorial function on both sides of this equation, it can be written as a recursive function, like this:

def factorial_recursive(value: int) -> int:

    if value == 1:
        return 1

    return value * factorial_recursive(value - 1)

One important thing to notice in this example is where it checks whether the argument is one. This is called a limiting condition, because it stops the function calling itself an infinite number of times. An infinite number of calls isn't a problem, at least not theoretically, for iterative functions. It is for recursive functions though: each function call in the recursive funding adds the current state to the call stack, and eventually that will fill it up and crash your program. So, make sure you always have a limiting condition.

A slightly more complex example, that often crops up in interviews, uses the Fibonacci series. If you've never encountered it, the Fibonacci series starts:

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Every number is the sum of the preceding two numbers, so if F is the Fibonacci function:

    F(n) = F(n - 1) + F(n - 2) for n > 2, F(0) = 0, F(1) = 1

A popular question in interviews is to write code that returns the nth number in the series. It's possible to use an iterative method, like the one below:

def fibonacci_iterative(index: int) -> Iterable[int]:
    if index == 0:
        return 0

    current_number = 0
    next_number = 1
    for _ in range(index):
        current_number, next_number = next_number, current_number + next_number

    return current_number


print(f"Factorial iterative: {factorial_iterative(limit)}")

Although this works, it could be expressed more simply. For example, the statement:

    current_number, next_number = next_number, current_number + next_number

uses a Python feature allowing multiple variables to be assigned in one statement. In most other languages, a temporary variable would be needed which would make it even more verbose.

Alternatively, using the original definition for the Fibonacci function, the code could be written using recursion:

def fibonacci_recursive(index: int) -> int:
    if index == 0:
        return 0
    if index == 1:
        return 1

    return fibonacci_recursive(index - 1) + fibonacci_recursive(index - 2)


print(f"Factorial recursive: {factorial_recursive(limit)}")

This is a much simpler implementation, down to there being one clause for each part of the original function definition. It would be possible to replace the two if statements that form the limiting conditions with one. However I decided against that for this example for the sake of clarity.

Something a Little More Challenging

In a previous job, we used to set a small coding challenge for prospective Software Engineers before we interviewed them. One of the challenges was to write a simulation of the predictive text function of a cellphone. The idea was that as you provided letters, the words from a list that matched the letters would be displayed. For example:

At the time we were using C# and we received a variety of user interfaces - some went as far as providing an ASP.NET application, whereas most provided a desktop WinForms application. The successful applicants usually implemented unit tests and and some sort of installer. I'm not going to do that here, but those things always help if you're applying anywhere.

Regardless of the front ends, the main code was all pretty much the same: a C# LINQ expression that selected words that started with the provided characters from a collection. Some used a List of words, others used HashSets and others used SortedSets. The Set-based implementations seemed more scalable, but because hash-based values like Sets only search their contents effectively with exact matches, they weren't. Regardless of the collection type, they still ended up needing to search the whole collection.

So far, it's hard to see what a LINQ query over a collection has to do with anything, but it's an iterative query and as we've already seen, these can often be replaced by recursion. It might be possible to make searches more efficient than the O(n) searches from the original solutions.

Looking at the original assignment, what we want is to be able to search for words based on their first few letters. So, we want some form of data structure that allows that and is also efficient. This sounds like the sort of job that a tree would be good for and, as I'm going to use Python to write the example, I'll implement a tree using the dictionary type. Splitting the words up into individual letters, and storing these letters in nested dictionaries will result in a time complexity of O(1), which is much more efficient that the O(n) we'd get from lists.

The letters from the above list of words would be stored in a tree like this:

When these are stored in nested dictionaries, they'll look like this:

{ 'c': { 'a': { 't': { '': {},
                       'e': { 'r': { 'p': { 'i': { 'l': { 'l': { 'a': { 'r': { '': { }}}}}}}}}}},
         'r': { 'e': { 'a': { 's': {'e': {'': {}}},
                              't': {'e': {'': {}, 'd': {'': {}}}}},
                       'p': {'e': {'': {}}}}},
         'u': {'p': {'': {}, 'b': {'o': {'a': {'r': {'d': {'': {}}}}}}}}}}

Adding words to the tree, and then retrieving them will need two separate functions. Adding the words requires that the first letters of the words are added to one node in the tree, and every subsequent letter is added to a new node under the current one. It's easy to see this on the tree diagram above, where shared letters follow a single path, and this splits when the words differ. In the dictionaries implementation, this point is where there's a dictionary with multiple entries. You can see this where 'create' and 'crease' diverge. We also need to add markers to show the ends of words, so that we can store words like 'create' and 'created' in the same set of dictionaries.

Retrieving the letters involves traversing every possible path of the tree, building up a word as you follow each route. When you reach the word end marker, you add the word to the list of words, and then follow the next route.

These functions can be shown in the diagrams below:

The function to add words from a list to the dictionaries is described in the following diagram.

And the function to retrieve the words from the dictionaries and put them back into a list is described by:

Both of these look complex, maybe too complex. I'm happy to admit my UML diagram skills aren't perfect, but they're not THAT far out. This is where the simplification that recursion offers comes into play.

The actual code to add words to the tree is:

def store_words(node: Dict[str, Dict[str, Any]], remaining_characters: str):
    if not remaining_characters:
        # Terminal condition - no characters left in the word
        node[""] = {}
    else:
        if remaining_characters[0] not in node:
            # First remaining character is not in the current node, add it
            # with a child dictionary
            node[remaining_characters[0]] = {}

        # Call this function recursively, passing the second and later
        # characters, and the child node.
        store_words(node[remaining_characters[0]], remaining_characters[1:])

From this code you can see that the terminal condition is checked first. If it's not met, a new node is created and the function is called recursively with the remaining letters of the string. When this runs, it creates a map, implemented with Python dictionaries, and fills it with all of the words in the list.

The code to retrieve words from the map is even simpler:

def retrieve_words(node: Dict[str, Dict[str, Any]], words: List[str], current_word: str):
    for item in node.keys():
        if not item:
            words.append(current_word)
        else:
            retrieve_words(node[item], words, current_word + item)

This code iterates through every possible path in the map, following each until it reaches a termination marker. Every time a termination marker is reached, the word formed by the letters along that path is added to the list or words extracted from the map.

Summary

Recursion can make your solutions to problems simpler and more graceful than other approaches. It's not suitable for all problems, but it's usually worth seeing whether it fits. With experience, as with other aspects of development, you'll learn to recognize situations where recursion can be used.

Recursion also has disadvantages, as I mentioned earlier. With every function call more data is added to the call stack. This can run through the system's memory quite quickly and can crash your program. It can also be slightly slower than iteration, because adding multiple items to the call stack in a recursive call is slower than changing values in an iterative function. However, systems are now at a stage where this isn't usually a problem. The processors and memory are fast enough to make the difference in performance minimal, and compiler optimizations minimize this even more. If you find the performance isn't what you need, or you run out of memory, use a different solution AFTER you've identified the recursion as the cause of the problems.