A little bit of Recursion with JavaScript

Let’s begin trying to understand recursion by making a simple search on google for “recursion”. As you can see, I didn’t type it wrong or misspelled it but they keep trying to suggest me the very same word every time I click it. Why? Because it’s just a glimpse of what recursion is.

recursiongoogle
A joke by Google

By definition, “recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem”. That’s a good way to define it but let’s make it simpler, shall we?

Recursion is the process in which a function has the ability to invoke itself.

A recursive function typically has three sections, the safe or termination case implemented to prevent errors caused by bad data, a base case used to stop further invocations, and last but not least the recursive call which gives the ability to continue calling the same function. Take in consideration that each section has a return statement (or at least storage a value, depending on the implementation),  and the order of those sections may vary depending on the problem to be solved, and like anything in life, nothing is black or white so you will have to find a way to reach an equilibrium between a theoretical solution and practical one to meet your requirements.

Now that we have described what is recursion and how it’s composed, it is time to see it in action. In this example, we’ll create a recursive method to raise a given value to the power n.

32 = 3 x 3 = 9
24 = 2 x 2 x 2 x 2 = 16
...
valn = val x val x ... x val = X

https://gist.github.com/SergioR82/66690a0fec0106c7385350a233b75265

PowExample gist code in case you can’t see it

As you can see, we have implemented a function called PowExample with two arguments, val (base value) and exp (exponent number).
First it verifies if val is equal to zero or if one of the arguments is not a number and in case it’s true, the function will return a zero value.
The second verification correspond to the exponent number, because we need to take into account that every number raised to the power of 0 is equal to 1, so regardless of val the function will ALWAYS return 1.
The third conditional is our recursive base case, meaning in this example that we are calculating val1 and as you already know, every value raised to the power of 1 is equal to the value itself.
As for the last line, val * PowExample(val, exp1) is in charge of multiply val with the result of the subsequent invocations of PowExample and then return the result to the caller.

It’s time to test it, so pretend you need to calculate 33 and then print it to the console:

console.log(PowExample(3,3));

  1. console.log(PowExample(3,3));
  2. PowExample(3,3) => 3 x PowExample(3,2)
  3. PowExample(3,2) => 3 x PowExample(3,1)
  4. PowExample(3,1) => 3
  5. PowExample(3,2) resume step 3 => 3 x 3
  6. PowExample(3,3) resume step 2 => 3 x 9 = 27
  7. console.log(27);

For this example, the number of calls to the function will be determined by the exp argument, which in this case will be 3 nested calls. This number can be referred as the recursion depth and the max number of invocations to a function will be limited not only by the engine executing your code, but also by the available resources for the Stack.
Remember that the Call Stack is a LIFO data structure used by the engine to store the execution context of every function call (even Global/ Main), therefore, depending on the memory allocated to each active context and the engine’s limit itself, you will count with a restricted recursion depth.

Ok, it’s time to work on a more realistic example. Consider the following structure:

[{
booktitle: “This is a TEST”,
author: “cosme fulanito”,
chapters: [
{ chapternbr: 0, title: “preface”, pages:1},
{ chapternbr: 1, title: “main chapter”, pages:50},
{ chapternbr: 2, title: “final thoughts”, pages:2}
]},
{
booktitle: “Another Test”,
author: “cosme menganito”,
chapters: [
{ chapternbr: 0, title: “preface”, pages:1},
{ chapternbr: 1, title: “main chapter”, pages:50},
{ chapternbr: 2, title: “final thoughts”, pages:2}
]
}];

We have an array filled with books and its chapters described inside. The requirement is to flat that array, in some way by using recursion in order to get a new one with a fusion between the book header and its corresponding chapters.

FlatBooks
Expected Result

So the function to achieve this could be like this:

TraverseArray gist code in case you can’t see it

TraverseRecursiveArray function expects three parameters, a source array, the position being processed and an object. The first invocation could be made with just the array because at this time, we only need the data source.
On line 11, the safe case is present to assure data is as expected, otherwise an empty array will be returned. The code block between lines 21 and 32 holds the function main process and it can be divided in two tasks, one to get all header values (resultObj) and the other to instantiate the successive calls to the TraverseRecursiveArray function.
Once each recursive call is finished, an object is returned with the detail data to be joined with its corresponding header data. At the end of the function, in line 40 we make the second recursive call to process all pending items in the current array, either main or property arrays.

As always, this code can be improved or even rewritten with different approaches (using map, reduce, etc). The purpose of this is to let you know that exists more than one method to achieve this and all of them are valid, as long you meet your requirements.

You just need to practice and when you feel you got it,  practice a lot more.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s