## DEV Community is a community of 636,345 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

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