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:
Happy coding :)
Top comments (0)