Recursive functions are one of my favorite development techniques. It's not a complicated thing. On the contrary, they are only functions used differently.
⚠️ Read more of my blog posts about tech and business on my personal blog! ⚠️
When we learn recursion, and more broadly, iteration in programming, we always stop at the classic iteration structures, loops. But they do not have a monopoly on iteration! In this article, I'll quickly tell you about another recursion structure.
😅
I thought for a long time that I wrote an article here on recursive functions. I discovered today that this is not the case, so I corrected that.
Recursion and loops
When we talk about recursion or iteration, we are usually talking about repeating things. In computing, it is the ability to repeat a defined quantity of instructions.
As we said, the classic way is to use loops for this. Programming languages generally offer several types of loops:
-
while
loops -
do...while
loops -
for
loops
But, there are still others. In JavaScript, for example, we can add these to the list:
-
for...in
loops -
for...of
loops
Generally, the loops added by the languages, in addition to the first three, are ultimately only specific variations of the first three loops.
I'm not going to explain loops to you here. They could be the subject of an article on their own. What must be remembered here is that loops are iterative structures offered by a language to allow a set of instructions to be repeated.
const list = ['one', 'two', 'three']
for(const element of list) {
// everything between the two braces
// will be repeated as many times as
// there are elements in list
}
Example of loop in JavaScript
Recursion and functions
Unlike loops, functions are not iterative structures as such. They make it possible to separate a sequence of instructions from the rest of the code in order to be able to execute them again later, on demand.
This last sentence looks a bit like an iterative structure, but here are the main differences that can be noted:
- A defined function may be called only once, or even never.
- If there is repetition (execution several times), it will be neither immediate nor linear unlike a loop.
A function is therefore not an iterative structure provided by the language. What will make a function recursive, and therefore allow iteration, is the use that the developer will make of it.
Let's see how to make a function recursive.
function addOne(base, times = 1) {
let result = base
for (let i = 0; i < times; i++) {
result += 1
}
return result
}
addOne(5, 3) // === 8
Function that uses iteration through a loop
This function is not recursive. It adds 1
to a number given as a parameter as many times as specified by the times
variable.
How to do now, to have the same result without the loops?
function addOne(base, times = 1) {
if (times <= 0) return base
const result = base + 1
return addOne(result, times - 1) // everything happens here
}
addOne(5, 3) // === 8
Function that uses iteration through recursion
The recursive function does not change signature. It always takes the base
and times
variables as parameters. It always returns a number.
What changes here: the function calls itself. That's all.
Let's go through the steps again with the parameters base=5
and times=3
to understand:
- Is
times
less than or equal to0
? No, it is equal to3
, we continue. -
result
is equal tobase
plus1
, i.e.5 + 1
, i.e.6
. - We pass the
result
andtimes - 1
to theaddOne
function and we will directly return its return value when done. - Is
times
less than or equal to0
? No, it is equal to2
, we continue. -
result
is equal tobase
plus1
, i.e.6 + 1
, i.e.7
. - We pass the
result
andtimes - 1
to theaddOne
function and we will directly return its return value when done. - Is
times
less than or equal to0
? No, it is equal to1
, we continue. -
result
is equal tobase
plus1
, i.e.7 + 1
, i.e.8
. - We pass the
result
andtimes - 1
to theaddOne
function and we will directly return its return value when done. - Is
times
less than or equal to0
? Yes, we returnbase
, which is equal to8
.
By doing it step by step, we better understand how a recursive function can completely replace an iteration structure like the loop.
☝️
No solution is better between recursive function and loops. Everything depends on the situation. Think of it as an additional tool that you can use for some particular algorithms.
The secret to mastering recursive functions is practice. Below you will find some exercises that I have prepared for you to progress on the topic 👇
You can also get the Training Sheet: Recursive Functions as a one-time-purchase on the shop.
Top comments (0)