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.

Input	Output
Feed machine 3 = 3 + feed machine 2	3 + 3 = 6
Feed machine 2 = 2 + feed machine 1	2 + 1 = 3
Feed machine 1 = 1	1

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 :)