Recursion in Javascript

The function calls itself until someone stops it. If no one stops it then it’ll recurse (call itself) forever.

Recursion can feel difficult to new developers. Perhaps that’s because many resources teach it using algorithmic examples like Fibonacci, linked-lists, etc. In this article I’ll try to demonstrate some simple examples to help you understand Recursion better.

What is Recursion Good For?

Recursive functions let you perform a unit of work multiple times. This is exactly what for/while loops let us accomplish! Sometimes, however, recursive solutions are a more elegant approach to solving a problem.

Some reasons that recursion is favored in functional programming languages is that:

• It allows for the construction of code that doesn’t require setting and maintaining state with local variables.
• Recursive functions are also naturally easy to test because they are easy to write in a pure manner, with a specific and consistent return value for any given input, and no side effects on external variable states.

Let’s see our first example:

We’ll create a countDownFrom function that takes a number parameter and countdown till 1.

countDownFrom(5);
// 5
// 4
// 3
// 2
// 1

First, we’ll implement it using ( for loop )

function countDownFrom(number) {
	for (let i = number; i > 0; i--) {
		console.log(i);
	}	
}

countDownFrom(5);
// 5
// 4
// 3
// 2
// 1

Now let’s try using recursive approach

function countDownFrom(number) {
	if (number === 0) {
		return;
	}

    console.log(number);    
    countDownFrom(number - 1);
}

countDownFrom(5);
// 5
// 4
// 3
// 2
// 1

It seems that both approaches gives the same results. But actually they do the same job in 2 different ways.

In the for loop approach we can see that it uses extra variable i, changing it’s value repeatedly untill it stop when i is no longer greater than 0 ( i > 0 ).

On the other hand; the recursive version doesn’t need extra variables to track its progress. That’s because each call to countDownFrom feeds it number - 1. By doing this we're passing along an updated parameter number each time. No extra state needed!

Infinite Loops

In your practice, you may have been warned about the dreaded infinite loop.

Since they’d theoretically run forever, an infinite loop will halt your program and possibly crash your browser. You can prevent them by always coding a stopping condition.

// THIS RUNS FOREVER, BE WARNED
while (true) { console.log('WHY DID YOU RUN THIS?!' }

// THIS DOES NOT RUN FOREVER
x = 0;
while (x < 3) { 
      console.log(x); 
      x++; 
}

Infinite Recursion

Recursion also presents the same danger. It’s not hard to write a self-referencing function that’ll crash your browser.

// THIS RUNS FOREVER, BE WARNED
function run() {
    console.log('running');
    run();
}

run();
// running
// running
// ...

// THIS DOES NOT RUN FOREVER
function run(x) {
    if (x === 3) return;
    
    console.log('running');
    run(x + 1);
}

run(0);
// running
// running
// running

// x is 3 now, we're done.

Without a stopping condition, run will forever call itself. We fixed that with an if statement.

Ready for another example ?

This example is one of the most famous recursion example. It returns the factorial of a supplied integer:

function factorial(x) {
  if (x < 0) return;
  if (x === 0) return 1;
  return x * factorial(x - 1);
}
factorial(3);
// 6

Before we go deep into this one, let’s understand what are factorials:

To get the factorial of a number you multiply that number by itself minus one until you reach the number one.

Example 1: The factorial of 4 is 4 * 3 * 2 * 1, or 24.

Example 2: The factorial of 2 is just 2 * 1, or 2.

Now can you get what’s happening with our function here.

It starts with a number and then it returns that number multiplied by itself -1, till it reaches 0 and in this case it returns 1 ending the recursion.

Now to sum up the three key features of recursion

1) A Termination Condition:

The Termination Condition is our recursion fail-safe. To prevent running the recursion in case of wrong or bad parameters.

if(something bad happened){ STOP };

In our factorial function it’s the if (x < 0) return; as it’s not possible to factorial a negative number. So we don’t even bother to run the function in this case.

2) A Base Case

The Base Case is similar to our termination condition in that it also stops our recursion. But it’s different in that it is the goal of our recursive function.

In the factorial example, if (x === 0) return 1; is our base case. We know that once we’ve gotten x down to zero, we’ve reached our goal and can determine the factorial successfully.

3) The Recursion

It’s simply our function calling itself.

In the factorial example, return x * factorial(x — 1); is where the recursion actually happens. We’re returning the value of the number x multiplied by the value of whatever factorial(x-1) evaluates to.

All Three Together

function factorial(x) {
  // TERMINATION
  if (x < 0) return;  
  // BASE
  if (x === 0) return 1;  
  // RECURSION
  return x * factorial(x - 1);
}
factorial(3);
// 6

Conclusion

• Recursion is when a function calls itself until someone stops it.
• It can be used instead of a loop.
• If no one stops it, it’ll recurse forever and crash your program.
• A termination condition and a base case are conditions that stop the recursion. Don’t forget to add them!
• Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.

Thanks for reading! Hopefully you’re now able to follow recursive functions in JavaScript and understand how they work.

Any comments or feedback are more than welcome 😊