Recursive functions

A Recursive Function is essentially just a function that calls itself. Recursive functions are not unique to JavaScript - its a very common programming technique which can be used with most programming languages with functions. Also, there's no special notation for recursive functions in JavaScript, meaning that you don't have to add a special keyword to the function declaration or anything like that - if the function calls itself, it is considered a recursive function.

But why would you ever need a function to call itself? Actually, there are many use cases for this technique, especially when you start solving more complex tasks. But for this tutorial, let's start with a simple example to show you how they work.

A simple recursion example: The countdown

Let's say that you would like to do a simple countdown, where we start with a number, show it to the user, decrease the value by 1 and then show the new number to the user. We want a function to display the number to the user. Without the use of recursive functions, it might look like this:

function CountDown(number)
{
	alert(number + "!");	
}

let number = 3;

CountDown(number--);
CountDown(number--);
CountDown(number--);

This solution works, but it's definitely not very elegant! We can easily fix this by turning it into a recursive function, but how? As mentioned, a recursive function just have to call itself to be recursive, but you need to be careful how you do it - there has to be something stopping the recursive calls at some point, because otherwise you will end up with an endless loop, which will likely crash the JavaScript environment (e.g. the browser).

Let's have a look at the recursive version of our countdown example:

function CountDown(number)
{
	alert(number + "!");
	number--;
	if(number > 0)
		CountDown(number);
}

let number = 3;
CountDown(number);

In our example, the stop-check is quite simple: We only call the CountDown() function recursively if our number is bigger than 0, making sure that the function is properly exited as soon as the countdown is done.

Also notice that now our function handles everything, including decreasing the number on each iteration, allowing us to just call the function once and then the rest is taken care of.

A complex recursion example: The tree structure

I recognize that the above example was very simple, perhaps a bit boring and not quite illustrative of how powerful a recursive function can be. I want to remedy that by showing you a more complex example, which also illustrates something that recursion is often used for: To create a tree structure.

Quick warning: In this example, I will be using a heavy mix of arrays and objects and some techniques which haven't been fully covered in this tutorial yet. If this seems to advanced for you at this stage of your learning process, feel free to skip this example and come back to it later.

Tree structures are used quite a lot on computers, to illustrate hierarchical data, but also in the real world, like a family tree etc. If you have worked with computers for more than a couple of hours, you have likely seen its folders and files displayed as a tree structure.

For my example, I would like to take some hierarchical data, representing (some of) the folders and files found on a Windows computer, and display them as a tree. In my example, the visual representation is just a very simple, text-only tree, but you could easily spice it up visually by adding icons etc. Here's what it will look like:

C:
----Program Files
--------Common Files
------------start.exe
------------readme.txt
----Windows
--------System32
------------Drivers
--------explorer.exe
--------notepad.exe
T:
----Data
----Secret Stuff

Really simple tree, really simple content, as it can be found on many Windows computers. Folders and files are listed by their name and if they have any child folders and/or files, they are listed below, with added indentation, to signal which parent folder they belong to.

To generate this, we need a function which will take an array of items, print the names and for each item, also print its child items (if it has any). It has to do this repeatedly until it has been through all items and all child-items. In other words, we need a recursive function. Here's how it could look:

function PrintTree(items, level)
{		
	for(let item of items)
	{
		let indentation = "-".repeat(level * 4);
		console.log(indentation + item.name);		
		if(item.items != null)
			PrintTree(item.items, level + 1);
	}
}

Notice how few lines we need to generate that big tree. The function is even very simple - as promised, it just prints the name, with a proper amount of indentation. We base the indentation on the current level, starting with 0, and for each level of the tree, we increment the level variable and pass it when we recursively call the PrintTree() function. We use the level variable to generate the indentation string, which is just a bunch of hyphens.

So, with that in place, let's have a look at the complete example, where we combine tree data, in the form of objects in arrays, with the function just shown:

let fileFolderTree = 
[
	{
		name: "C:",
		items:
		[
			{
				name: "Program Files",
				items:
				[
					{
						name: "Common Files",
						items:
						[
							{
								name: "start.exe"
							},
							{
								name: "readme.txt"
							}
						]
					}
				]
			},
			{
				name: "Windows",
				items: 
				[
					{
						name: "System32",				
						items: 
						[
							{
								name: "Drivers"
							}
						]
					},
					{
						name: "explorer.exe"
					},
					{
						name: "notepad.exe"
					}
					
				]
			}
		]
	},
	{
		name: "T:",
		items: 
		[
			{
				name: "Data"
			},
			{
				name: "Secret Stuff"
			}
		]
	}	
];


function PrintTree(items, level)
{		
	for(let item of items)
	{
		let indentation = "-".repeat(level * 4);
		console.log(indentation + item.name);		
		if(item.items != null)
			PrintTree(item.items, level + 1);
	}
}

PrintTree(fileFolderTree, 0);

As you can see, it takes quite a bit of code to contain all the folders and files as a hierarchical set of data. Normally, this would just come directly from the underlying system, but since we don't have access to that from JavaScript-through-the-browser, I have recreated some data for us to work with.

After all the data, we have the recursive function called PrintTree(), as we already discussed. On the very last line, we have our simple call to the recursive function, which will set it all in motion - we just call it once, because it will be sure to call itself as many times as needed. I simply pass in our data and the first level (0) and our recursive function takes care of the rest.

Summary

When a function calls itself, it's referred to as a recursive function, and as you can see from the examples of this article, this can be really useful. Recursive functions, which are a common programming technique and not specific to JavaScript, are not used all the time, but they are extremely practical when you need to solve specific problems, e.g. dealing with hierarchical data.