What is Recursion?

Introduction

To understand recursion, you must first understand recursion.

Software development is full of recursive jokes like the one above. GNU, the open source software crucial to Linux, stands for 'GNU's Not Unix'. Joking aside, recursion is a very useful approach in programming. It can also have terrible side effects. Think of a computer trying to get the joke above. It is so literal-minded, it never gets to the punchline, ending up stuck in a self-reflective loop. This article will focus on the benefits of recursion, along with how to avoid its pitfalls.

Recursion in Action

In practical terms, recursion in programming is when a function calls itself in order to break down a task into smaller parts. Let's take a simple example and see how we might improve it with recursion

Jane is a girl scout who wants to sell some cookies. She starts by visiting all the houses on her street.

Let's code this in Python:

customers = ["House #1", "House #2", "House #3"]

def sell_cookies_one_by_one():
    for customer in customers:
        print("Selling cookies to", customer)

sell_cookies_one_by_one()

Jane lives on a small street, so this simple approach works fine. However, she wants to expand her cookie selling empire to the whole town, perhaps even the country. How best to do this without getting over-whelmed? Let's imagine Jane can call on two more girl scouts to help her. Each of those girl scouts can call on two more to split the work further. To avoid infinite recursion, there is a limiting factor: no more calling on friends if the work can't be split any further; just sell to the house instead.

Let's write this out in pseudocode:

1. Jane starts with the full total of houses to sell to. Four, in this example.
2. Jane calls on two friends and halves the work between them.
3. Each of the friends now has two houses to sell to. They each call two more friends and hand off the work to them.
4. Now there are four girl scouts with a house to sell to.

You may have spotted the recursion in the pseudo-code, i.e. when Jane's friends do exactly what Jane does. There is also a halting condition to make sure the selling actually gets done. Let's see what this looks like in Python:

customers = ["House #1", "House #2", "House #3", "House #4"]

# Each call is a decision to split work or actually sell.
def sell_cookies_recursively(customers):
    # Girl Scout actually selling cookies
    if len(customers) == 1:
        customer = customers[0]
        print("Selling cookies to", customer)
    # Otherwise calling two more girl scouts to do work.
    else:
        middle = len(customers) // 2 # integer division
        first_set_of_customers = customers[:middle]
        second_set_of_customers = customers[middle:]
        # Divide the work
        sell_cookies_recursively(first_set_of_customers)
        sell_cookies_recursively(second_set_of_customers)

sell_cookies_recursively(customers)

For ease of illustration, the example above only has four customers but it would work equally well for four thousand customers. The key thing to note is that the function calls itself and each time it makes a decision whether to halve the list of customers or to sell to a single house and stop calling further.

Conclusion

Let's conclude this discussion with a question that might come up in a coding job interview. You might be asked: "Starting at zero, give the value of any particular number in the Fibonacci sequence?"

First of all, what is the Fibonacci sequence? Although this mathematical concept has many applications today, it was first imagined by the Italian mathematician Fibonacci in the thirteenth century. His goal was to map the explosive reproductive rate of breeding pairs of rabbits. Looking at the data, his insight was that the number of rabbits in any given year was equal to the sum of the number of rabbits born in each previous year, starting with one pair of rabbits in the first year.

The Fibonacci sequence starts at 0 and 1 and then each number is a sum of the previous two numbers. I.e. 0, 1, 1, 2, 3, 5, 8

To put it mathematically, to get the number of rabbits born in any year n, we can use the following recursive formula:

F_n = F_n-1 + F_n-2

Starting with the base assumption of:

F₀ = 0 and F₁ = 1

Before looking at the solution below, why not try coding the answer yourself first?

def fibonacci_sum(n):
    # Special cases to stop function when necessary
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # Otherwise sum the previous two numbers
    else:
        return fibonacci_sum(n-1) + fibonacci_sum(n-2)

print(fibonacci_sum(6))

The above solution will return 8 as element number 6 (zero based) in the Fibonacci sequence. The special cases of zero and one prevent the recursive call from continuing indefinitely. As the code uses recursion to build up the sequence, the solution is short and concise and a fine illustration of the benefits of recursion.