Recursion: Heads Or Tails
A recursive function is one that calls itself. Whether it’s diving deeper into the meaning of life by asking “why” over and over again (spoiler: the answer is pizza), or traversing nested data structures, recursion plays a critical role.
For many, iteration is a coder’s first major tool in dynamic programming. It’s generally more straightforward to learn, and in many cases iteration has negligible performance differences from recursion.
Let’s look at calculating 4! both iteratively and recursively.
Iteratively:
function iterativeFactorial(num) {
let result = 1; for (let i = 1; i < num + 1; i++) {
result *= i;
} return result;
}iterativeFactorial(4);
=> 24
Recursively:
function recursiveFactorial(num) {
if (num === 0) {
return 1;
}
return num * factorial(num - 1);
}recursiveFactorial(4);
=> 24
In such cases, the real gain is just improving code readability. The recursive example uses one less line of code and sheds the more convoluted looping logic of the iterative example. Is it a big deal? Probably not.
There are, on the other hand, times when recursion is almost necessary. In fact, a common use case is traversing nested data structures.
Consider the below data structure with a seemingly unknown amount of nested arrays:
const data = [
{ id: "0" },
{
id: "1",
children: [
{
id: "1.1",
children: [
{
id: "1.1.1",
children: [
{
id: "1.1.1.1",
children: [
{ id: "1.1.1.1.1" },
{ id: "1.1.1.1.2" },
{ id: "1.1.1.1.3" }
]
},
{ id: "1.1.1.2" },
{ id: "1.1.1.3" }
]
},
{ id: "1.1.2" },
{ id: "1.1.3" },
]
},
{ id: "1.2" },
{ id: "1.3" }
]
},
{ id: "2" },
{ id: "3" }
];If we want to collect all of the objects’ id values in one array, iteration is not feasible. Please turn in your computer for an abacus if you are considering manually counting out how nested each object is. What if we are consuming an API and the above is dynamically rendered JSON? We need a solution that works dynamically.
Enter recursion.
A recursive function returning an array of all of the ids may be:
function returnIdArr(data, result = []) {
for (let i = 0; i < data.length; i++) {
result.push(data[i].id);
if (data[i].children) {
returnIdArr(data[i].children, result);
}
}
return result;
}returnIdArr(data);
=> ['0', '1', '1.1', '1.1.1', '1.1.1.1', '1.1.1.1.1', '1.1.1.1.2', '1.1.1.1.3', '1.1.1.2', '1.1.1.3', '1.1.2', '1.1.3', '1.2', '1.3', '2', '3']
The function loops through the array, and if any of the objects includes a ‘children’ property, the function recursively calls itself on the nested children array ad infinitum (or until there is no more ‘children’). Each id is pushed to the result array which itself is passed as an argument with each recursive call.
Breaking down the thread of execution for the first few frames:
...
// the first iteration of the loop pushes '0' into the result array
result.push(data[0].id); // result = ['0']if (data[0].children)... // false/* ------------------------------------------------ */...
// the second iteration pushes '1' into the result array
result.push(data[1].id); // result = ['0', '1']// now true:
if (data[1].children) {
returnIdArr(data[1].children, ['0', '1']);/* recursively calls the function with the children and current result array as arguments */.../* ------------------------------------------------ *//* the first iteration of this new loop (nested one level down) pushes '1.1' into the result array */result.push(data[0].id); // result = ['0', '1', '1.1']// true again:
if (data[0].children)...
returnIdArr(data[1].children, ['0', '1', '1.1']);// and recursion again......
We can see the value of recursion in instances like this — our relatively simple returnIdArr function acts as a Swiss Army knife returning an id array for any version of this data structure. It is effective, readable, and dynamic.
Now looking at the above frames in the call stack with a more discerning eye, we may even start to consider the implications on memory. None of the frames on the call stack can pop off until every item in the current array has been iterated through. This means all of the children properties in the current array must also be evaluated first, and the children properties in those as well. In fact, the first level of the array, ending with an object whose id property is ‘3’, stays on the call stack the entire time until every other nested array has been totally looped through.
Are there other ways to handle this?
In fact, there are two common implementations in this type of direct recursion: head and tail recursion.
Head recursion calls the recursive function at the beginning before other processes. Typically, the function determines that recursion is needed and calls itself with a decremented parameter.
Here’s some (contrived) head recursion at work:
function headCount(num) {
if (num === 0) {
return;
} else {
countDown(num - 1);
} console.log(num);
}count(3)
// 1
// 2
// 3
The headCount function evaluates if its num argument is 0. If not, the function recursively calls itself with the decremented number as argument.
The two things of note are:
- The recursion occurs at the top, or head, of the function/processing
- The logged numbers start at 1 (not 3) and increment
On the other hand with tail recursion, it’s the opposite — the processing occurs before the recursive call.
Here’s some (equally contrived) tail recursion:
function tailCount(num) {
if (num === 0) {
return;
} else {
console.log(num)
} countDown(num - 1);
}countDown(3)
// 3
// 2
// 1
As opposed to our headCount function, tailCount logs out numbers starting at 3 and then decrementing. In order for this difference to exist, the frames on the respective call stacks must be different upon reaching the console.log statements.
The headCount function must create frames for each execution context from each recursive call. Only after reaching the base case, num === 0, can the frames begin to pop off the stack, thereby reaching each respective console.log.
On the other hand, the tailCount function replaces its execution context with each recursive call. The called recursive function logs out its number and has no need for any of context from the previous call. Because of Tail Call Optimization, many compilers ensure there only exists one frame on the call stack throughout the duration of the thread of execution.
Minor difference in actual written code, but huge difference in behavior.
Learning recursion comes with a steep curve and probably many failed infinite loops, but the nuanced performance gains and necessary use cases make it a critical tool for any programmer.
Oh, while I have you here, you may want to read this article: Recursion: Heads Or Tails
