Introduction to Recursion with JavaScript

Copy Link LinkedIn Message Facebook Email X

In this lesson, you are going to get to grips with a concept that is common in interviews, recursion.

Understand Recursion in JavaScript

Recursion in programming is a powerful method to get things done in a very concise and elegant way.

It's a bit of a mind-bending concept to get your head around, but don't worry, you will get better at it as time goes on.

A reminder that understanding something that you read in a course and actually being able to use it are two very different things. You have to practice a bunch, especially when you are getting started. Doing drills, warm-ups, and practice questions are essential! So practice along with the course and do your labs! Additionally, try out recursion problems on coding challenge sites like LeetCode.

Visualize Recursion in JavaScript

In a general sense, when thinking of recursion, there are several types of images that are associated with it:

The above image is a zoomed-in view of the Mandelbrot set. It's a fractal, which is a shape that repeats itself at different scales. This is a good analogy for recursion because it's like a function that calls itself, and the function is the same at different scales at which it's called.

Practical Use Cases of JavaScript Recursion

This is to get your head around the idea of what recursion is and what it can look like.

The risk of infinite loops is very high in this section. You will definitely run into them a few times. Remember where your task manager is. In Chrome it's in the menu > more tools > task manager. Or shift + esc on Windows. Be ready to kill a JavaScript process so as not to crash your whole computer.

The Factorial Problem

To understand how programmers use this concept, it's best to jump right in with an example problem. Here is a common code challenge:

Write a recursive function that calculates the factorial of a number.

5 factorial, for example, annotated as 5! in math, is the result of:

5 x 4 x 3 x 2 x 1 = 120
5! = 120

The input can only be a non-negative number.

Learn by Doing

There is both a recursive and iterative way to do this. Iterative in this case means without recursion. Try to solve it in any way you can and commit your work before looking at the solution below.

If you're doing this course step-by-step, and especially if you're in the mentorship program, please be sure to push your work to GitHub when you're done.

The Iterative Approach

Starting off with the iterative version:

function factorial(n) {
	if (!Number.isInteger(n) || n < 0)
		throw new Error('Input must be a non-negative integer.');

	let result = 1;
	for (let i = n; i != 0; i--) {
		result *= i;
	}
	return result;
}

A for loop is set up based on the input number. This counts down the numbers, multiplying them by the result every time. This will correctly give you a factorial.

The Recursive Approach

You've handed this to the interviewer and they like the fact that you are error checking, and that you get the right result, however, they now ask for the recursive version of this function.

When this is asked, they usually want you to write the function in a way that will end up with the function calling itself.

This is a bit of a strange way to say it because it doesn't call itself, it calls another execution of the function.

To illustrate this, here is a simple example of an infinitely recursive function that will crash your browser tab, so use it with caution:

function iAmInfinite() {
	iAmInfinite();
}

This is like a while (true) loop. If you call iAmInfinite() in your code, it will block right there and eventually crash your system.

What is happening with this exactly?

Assuming that the above function has been actually called, the following happens:

1. An execution of the function is created based on the function prototype, which, for the purposes of this explanation, is called execution 1. This execution is pushed onto the call stack
2. Execution 1 now needs to create a new execution, execution 2 of the function iAmInfinite() so it does so. So execution 2 is now pushed onto the call stack too
3. Execution 2 now needs to create a new execution, execution 3 of the function iAmInfinite() so it does so. execution 3 is now also on the call stack
4. This process repeats until the call stack gets so large that the JavaScript interpreter will automatically raise an error, or the browser tab will just crash

This short example illustrates why recursive functions require an exit condition. Much like the while loop, if you don't think carefully about how your function will stop, then it might run away from you!

An Example Recursive Countdown Function

In this section, you will examine a recursive function that counts down numbers:

function countDown(n) {
	if (n === 0) {
		console.log('GO!');
		return; // Essential return which terminates the recursion
	}
	console.log(n);
	return countDown(n - 1);
}

countDown(5);
/* OUTPUT
5
4
3
2
1
GO!
*/

When you call countDown(5), the following happens:

1. The function countDown() is called with the argument 5
2. The function checks if n is equal to 0, it isn't, so it continues
3. The function logs n to the console, which is 5
4. The function calls itself with the argument n - 1, which is 4
5. The function countDown() is called with the argument 4
6. The function checks if n is equal to 0, it isn't, so it continues
7. The function logs n to the console, which is 4
8. The function calls itself with the argument n - 1, which is 3
9. And so on...

With the final return keyword, once n reaches 0, makes the infinite duplication of functions stop, and the final function returns a value, in this case undefined, and then this value gets passed down the chain of functions on the call stack until it reaches its original callers return and finally exits.

The Recursive Factorial Function

The iterative version of the factorial function you have so far is:

function factorial(n) {
	if (n < 1) throw 'must be positive integer';
	if (!Number.isInteger(n)) throw 'must be an integer';

	let result = 1;
	for (let i = n; i != 0; i--) {
		result *= i;
	}
	return result;
}

Here is one way to solve it:

function factorial(n) {
	if (!Number.isInteger(n) || n < 0) throw 'must be a non-negative integer';

	if (n === 0) return 1;
	return n * factorial(n - 1);
}

If this isn't making sense to you, try it out in JavaScript Tutor which will let you visualize the call stack as it is executing.

Summary: Recursion with JavaScript

In this lesson you've:

• Got to grips with recursion, a concept that elegantly solves problems where a function can call itself.
• Learned the importance of having an exit condition to prevent infinite loops.
• Walked through the factorial problems, starting with an iterative approach before diving into the recursive solution.
• Visualized the recursive process with a countdown example, helping you see how each function gets pushed onto the call stack until the base case is reached.
• Finally, created a recursive version of the factorial function that elegantly calls itself until it reaches the base case.