Recursive Functions Explained

Mission: Attempt to explain recursive functions in the way that helped me understand them.

Intro

When I learned about recursive functions, they made absolutely no sense to me. I understood what output was expected and when to use them, but I didn’t know how they got there and I don’t like using things unless I fully understand them, not least because it makes debugging a nightmare.

When I looked for explanations online, all I could find were things along the lines of:

Ah, you see, it works on two sides. It works out the left side, and then the right.
It’s a function that calls itself until it doesn’t.

I was still none the wiser.

Of course, these explanations make sense to me now, but sometimes you need things explained to you in a different way, which is what I’m aiming to do for you today.

The way I finally understood how they worked was to write my own recursive function on this old fashioned device called a piece of paper. Knowing what the output would be, I worked backwards to see if I could figure it out… and I did! … then I felt stupid for not understanding it in the first place, but hey, that’s programming!

What are recursive functions used for?

A recursive function is a way of iterating over a block of code until a certain condition is met. If this sounds like a for loop or a while loop, it’s because their use cases are the same, they’re just different ways of achieving the same result.

Our function

Let’s create a recursive function in Python that prints the sum of all positive integers between 1 and the number we pass it. For example: if we pass our function the number 5, it should output 15 because 5 + 4 + 3 + 2 + 1 = 15.

def machine(n):
    if n == 1:
        return 1
    else:
        return n + machine(n - 1) 

What is happening?!

In order to explain how this works, I’m going to refer to our function by its name, machine. When we feed the machine a number (n), it first checks if n is equal to 1, and if it does it outputs (returns) 1. Basic stuff so far.

If, however, n does not equal 1, the machine outputs n + [ feed the machine (n - 1) ]. This is where it gets a bit confusing.

In order for the machine to complete its calculation, it first needs to work out what the result would be if it was fed n - 1. With this in mind, let’s run through the machine’s entire process one step at a time.

Step 1: Process 1
The machine is given the number 3.
Does 3 = 1? No, move on.
Output 3 + [ give machine 2 ]. Stop and give the machine 2.

Step 2: Process 2
The machine is given the number 2.
Does 2 = 1? No, move on.
Output 2 + [give machine 1] . Stop and give the machine 1.

Step 3: Process 3
The machine is given the number 1.
Does 1 = 1? YES! Output 1!

Step 4: Back to Process 2
Now that the machine knows the answer to [ give machine 1 ], it can finish its output calculation.
Output 2 + 1 = 3.

Step 5: Back to Process 1
Now the machine knows the answer to [ give machine 2 ], it can finish its output calculation.
Output 3 + 3 = 6.

The Result
The machine will output 6!

One more example

Let’s run the machine with the number 5 this time. Just to remind you of the code:

def machine(n):
    if n == 1:
        return 1
    else:
        return n + machine(n - 1) 

machine(5)

Feed machine 5
Output 5 + feed machine 4

Feed machine 4
Output 4 + feed machine 3

Feed machine 3
Output 3 + feed machine 2

Feed machine 2
Output 2 + feed machine 1

Feed machine 1
Output 1.

Feed machine 2 = 2 + 1 = 3.
Feed machine 3 = 3 + 3 = 6.
Feed machine 4 = 4 + 6 = 10.
Feed machine 5 = 5 + 10 = 15.

Result = 15!

The Pattern

You might start being able to see a really nice symmetrical pattern with how this works, and you may even start to see why people explain it as working on ‘2 sides’. If we wrote the above a bit differently, the ‘sides’ explanation might make more sense.

Read the left column from top to bottom, then the right column from bottom to top.

This process is referred to as ‘The Call Stack’: a stack of functions that need to be solved in turn, so the next function in the stack can be completed.

Can’t we just use a for loop?

Yep! Our machine function utilising a for loop might look something like this:

def machine(n):
    sum = n
    for x in range(n):
        sum += x
    return sum

What we’re doing here is setting a variable sum equal to the number we pass the function (n), then looping through numbers 0 - n (exclusively), then adding the current iteration to the value of sum. Then we return sum.

Pitfalls

Much like a for loop, we can set a recursive function to easily loop infinitely - not a good thing. Always make sure there is a ‘base case’ in a recursive function which will cause the recursion to stop.

In our recursive machine function, our ‘base case’ is: if n == 1: return n. We are also decrementing n with each recursive call with else: return n + machine( n - 1 ). This means that with each function call, we call the function with a number 1-less than the previous iteration, and we stop when n is equal to 1.

Where are all my Javascript homies?

I’ve written this post using Python as my language of choice, however, please see below the 2 functions I’ve written in Javascript.

// Recursive
function machine(n) {
    if (n === 1) {
        return n;
    } else {
        return n + machine(n - 1);
    }
} 

// Iterative
function machine(n) {
    let sum = n;
    for (let i = 0; i < n; i++) {
        sum += i;
    }    
    return sum;
}

Wrap it up wrap it up

I hope that this has helped you understand recursive functions. There are obviously a million and one use cases and examples we could go through, but by understanding how they work and the fundamentals behind them, hopefully you’ll be able to use them in a future project in your own way.

For further reading on recursive functions, I would highly recommend this article by Beau Carnes on Free Code Camp:

Free Code Camp Article

Happy coding :)