Functions: Recursive functions

A function has the ability to call itself.

This is what we call recursion.

Recursion allows us to solve some specific problems in a smart way.

You need a function with a name, which can be either a “regular” function, or an arrow function:

function test() {

}

or 

const test = () => {

}

Now you can call test() inside test().

function test() {
  test()
}

//or

const test = () => {
	test()
}

The simplest example we can make is calculating a factorial of a number.

The factorial of a number is what we get by multiplying the number for (number - 1), (number - 2), and so on until we reach the number 1.

The factorial of 3 is

(3 * (3 - 1) * (3 - 2)) = 3 * 2 * 1

which is 6

The factorial of 4 is

(4 * (4 - 1) * (4 - 2) * (4 - 3)) = 4 * 3 * 2 * 1

which is 24.

We can create a recursive function to calculate the factorial automatically:

function factorial(n) {
  return n >= 1 ? n * factorial(n - 1) : 1
}

Now we can call this function passing the number for which we want to calculate the factorial.

factorial(1) //1
factorial(2) //2
factorial(3) //6
factorial(4) //24

We can also use an arrow function if we prefer, there’s no difference:

const factorial = (n) => {
  return n >= 1 ? n * factorial(n - 1) : 1
}

With recursive functions you have to pay attention to not generating an error by calling a function an infinite amount of times.

What do I mean? Imagine we do an error, and instead of calculating the factorial as

const factorial = (n) => {
  return n >= 1 ? n * factorial(n - 1) : 1
}

we do this:

const factorial = (n) => {
  return n >= 1 ? n * factorial(n) : 1
}

As you can see, instead of decreasing n each time we call factorial(), we are now calling factorial(n) ad infinitum. There’s no end, because we forgot to lower it on every call.

If you run this code, you’ll get this error:

RangeError: Maximum call stack size exceeded

Every time a function is invoked, JavaScript needs to remember the current context before switching to the new one, so it puts that context on the call stack. As soon as the function returns, JavaScript goes to the call stack and picks the last element that was added, and resumes its execution.

Maximum call stack size exceeded means that too many elements were put on the stack, and your program crashed.

It’s similar to having an infinite loop, because the program can’t continue its execution.

Lessons in this unit:

0: Introduction
1: Function parameters
2: Returning values from a function
3: Arrow functions
4: Nesting functions
5: Immediately-invoked functions
6: ▶︎ Recursive functions
Want to learn more? Check out our courses