Recursive Functions Explained
Tags: python, javascript, beginners, tutorial
Published: 2021-02-10 12:41:43

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`.

```python
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:

```python
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:

```python
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.


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

<a href="https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/" target="_blank">Free Code Camp Article</a>

Happy coding :)