How does recursion work?
In a nutshell, recursion in computer science describes a function call within its own definition. It's most commonly used to iterate through a list of similar items.
Let's look at a showcase. The following code function recursively prints each entry of a given array:
const items = ['one', 'two', 'three']
function printItemsRecursively(arrayOfItems, currentIndex) {
// Condition to finish function execution at some point
// In this case, we can use the array's length
if(currentIndex >= arrayOfItems.length) {
console.log("Finished iteration");
return;
}
// Log the current item
console.log(arrayOfItems[currentIndex]);
// Recursive function call
printItemsRecursively(arrayOfItems, currentIndex + 1);
}
printItemsRecursively(items, 0);
Similar functionality can also be achieved using `for` or `while` loops:
function printItemsForLoop(arrayOfItems) {
const maxLength = arrayOfItems.length
// Condition to finish function execution at some point
for(let currentIndex = 0; currentIndex < maxLength; currentIndex++) {
// Log the current item
console.log(arrayOfItems[currentIndex]);
}
}
function printItemsWhileLoop(arrayOfItems) {
const maxLength = arrayOfItems.length;
let currentIndex = 0;
// Condition to finish function execution at some point
while(currentIndex < maxLength) {
// Log the current item
console.log(arrayOfItems[currentIndex])
// Increment index
currentIndex++;
}
}
printItemsForLoop(items)
printItemsWhileLoop(items)
At first glance, recursion looks more complex:
- We must actively pass an additional argument into the function while the other loops handle the `currentIndex` internally.
- We must implement an if-check to finish execution ourselves while the other loops have this check built-in.
- If we forget to manually return in the if-check, we will always run into an infinity loop
Traversing tree structures
While these constraints might seem intimidating, they can prove helpful in tree structures. Tree structures are represented as nodes, where one node has one or many child nodes. You can find this structure in
- Your project directory
- Organizational charts with departments as the nodes
- Generally speaking: Hierarchical data or information that is connected by references
The tree data structure
Let's look at an example. The following tree structure displays a hierarchy of employees with their superiors and associates.
The same structure can be expressed in JSON format or as a Javascript object:
const organisation = {
name: 'John Doe',
associates: [
{
name: 'Jane Doe',
superior: 'John Doe',
associates: [
{
name: 'Mark Smith',
superior: 'Jane Doe',
associates: [
{
name: 'Marie Curie',
superior: 'Mark Smith',
},
],
},
{
name: 'Andy Joy',
superior: 'Jane Doe',
},
],
},
{
name: 'Mycroft Holmes',
superior: 'John Doe',
associates: [
{
name: 'Milly Smith',
superior: 'Mycroft Holmes',
associates: [
{
name: 'Max Doe',
superior: 'Milly Smith',
},
{
name: 'Linus White',
superior: 'Milly Smith',
},
],
},
],
},
],
};
Moving through the tree's data
Our task now is the following:
- Print each employee's data
- Include the employee's superior
- Include the level within the tree
For Linus White, the following statement would be correct:
Linus White is on level 3 of the tree. Their superior is Milly Smith.
Using recursion
With recursion, implementing these features is surprisingly straightforward:
function printEmployeeDataRecursive(employee, level) {
// This is the lowest level of the tree
// Print the message and return to prevent from infinity loops
if (!employee.hasOwnProperty('associates')) {
console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior}`);
return;
}
// Print the superior, if maintained.
console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior || 'outside this structure'}`);
// Print the count of their associates
console.log(`${employee.name} has ${employee.associates.length} associate(s):`);
// Apply printEmployeeData recursively to each associate
employee.associates.forEach((associate) => printEmployeeDataRecursive(associate, level + 1));
}
Let's do it step by step, just to be sure we understand what's going on:
We check if the employee has any associates
- If they don't, we're at the lowest level of the tree. We write out the employee's data, and that's it
- If they do, we're not at the lowest level. We write out the employee's data, move to the next level, and start again
Note how we're using the additional complexity from earlier to our advantage here. It feels like the function keeps track of itself while moving through the tree's structure.
Using a queue
Let's look at an alternative without recursion. The most forward way I could come up with is to use a queue.
function printEmployeeDataQueue(employee, level) {
const queue = [{employee: employee, level: level}];
while (queue.length > 0) {
const current = queue.shift();
if (!current.employee.hasOwnProperty('associates')) {
console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior}`);
continue;
}
console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior || 'outside this structure'}`);
console.log(`${current.employee.name} has ${current.employee.associates.length} associate(s):`);
for (let associate of current.employee.associates) {
queue.push({employee: associate, level: current.level + 1});
}
}
}
This approach is perfectly valid. Its only drawback is the overhead logic required to make it work:
- A queue to process employee entries
- A while - statement to check whether to run the procedure
- A for-loop to add child nodes to the queue
You could also work your way through the tree nodes manually. But this would introduce additional, possibly unnecessary, and verbose code.
Digression: Without additional internal data structures
I was curious if there was a generic solution for this problem without recursion or additional data structures. Since I couldn't come up with one that does not make assumptions about the tree's depth, I asked ChatGPT.
ChatGPT: Rewrite the following function without using recursion, a queue or a stack: <paste the function from above>
I'll spare you the details (you can try to replicate this case yourself at https://chat.openai.com), but even ChatGPT could not provide a working solution to this problem that worked without recursion, a queue, or a stack.
Wrap up
Given the proper application, recursion is very elegant. While recursive functions introduce additional complexity, there are cases in which they come in handy. One example this article illustrated were tree-structures. Compared to a more classic iterator function, recursion introduced no internal processing logic, keeping the code clean and less verbose.
Sources and further reading
- https://cbselibrary.com/advantages-and-disadvantages-of-recursion/
- https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/
- https://chat.openai.com/
Full Code Reference
const organisation = {
name: 'John Doe',
associates: [
{
name: 'Jane Doe',
superior: 'John Doe',
associates: [
{
name: 'Mark Smith',
superior: 'Jane Doe',
associates: [
{
name: 'Marie Curie',
superior: 'Mark Smith',
},
],
},
{
name: 'Andy Joy',
superior: 'Jane Doe',
},
],
},
{
name: 'Mycroft Holmes',
superior: 'John Doe',
associates: [
{
name: 'Milly Smith',
superior: 'Mycroft Holmes',
associates: [
{
name: 'Max Doe',
superior: 'Milly Smith',
},
{
name: 'Linus White',
superior: 'Milly Smith',
},
],
},
],
},
],
};
function printEmployeeDataRecursive(employee, level) {
// This is the lowest level of the tree
// Print the message and return to prevent from infinity loops
if (!employee.hasOwnProperty('associates')) {
console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior}`);
return;
}
// Print the superior, if maintained.
console.log(`${employee.name} is on level ${level + 1}. Their superior is ${employee.superior || 'outside this structure'}`);
// Print the count of their associates
console.log(`${employee.name} has ${employee.associates.length} associate(s):`);
// Apply printEmployeeData recursively to each associate
employee.associates.forEach((associate) => printEmployeeDataRecursive(associate, level + 1));
};
function printEmployeeDataQueue(employee, level) {
const queue = [{employee: employee, level: level}];
while (queue.length > 0) {
const current = queue.shift();
if (!current.employee.hasOwnProperty('associates')) {
console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior}`);
continue;
}
console.log(`${current.employee.name} is on level ${current.level + 1}. Their superior is ${current.employee.superior || 'outside this structure'}`);
console.log(`${current.employee.name} has ${current.employee.associates.length} associate(s):`);
for (let associate of current.employee.associates) {
queue.push({employee: associate, level: current.level + 1});
}
}
}
