Understand recursive functions

Nathanaël Cherrier -

Recursive functions are one of my favorite development techniques. It's not a complicated thing. On the contrary, they are only functions used differently.

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:

  1. Is times less than or equal to 0? No, it is equal to 3, we continue.
  2. result is equal to base plus 1, i.e. 5 + 1, i.e. 6.
  3. We pass the result and times - 1 to the addOne function and we will directly return its return value when done.
  4. Is times less than or equal to 0? No, it is equal to 2, we continue.
  5. result is equal to base plus 1, i.e. 6 + 1, i.e. 7.
  6. We pass the result and times - 1 to the addOne function and we will directly return its return value when done.
  7. Is times less than or equal to 0? No, it is equal to 1, we continue.
  8. result is equal to base plus 1, i.e. 7 + 1, i.e. 8.
  9. We pass the result and times - 1 to the addOne function and we will directly return its return value when done.
  10. Is times less than or equal to 0? Yes, we return base, which is equal to 8.

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. You can get some exercises that I have prepared for you to progress on the topic in the shop : look for the Training Sheet: Recursive Functions.