JavascriptProgrammingTechnology

Easy Guide to Javascript Recursion

I have a confession to make.

Out of many Javascript’s programming concepts, there are few which give me nightmares.

Among them is the concept of Javascript Recursion.

For those who are not aware of this concept, it’s basically a Javascript function calling itself.

Or in other words, it’s a function within a function.

Or for the movie savvy geeks, it’s the “Inception” of Javascript functions.

I hope I’ve made it easier for you.

However, don’t get me wrong, the concept within itself is not complicated at all. It’s quite simple. So you won’t find it difficult to get the basic gist of the matter.

The real issue comes when you have to design a program which revolves around this concept or even worse, have to read and analyze a program, written by someone else getting things done through Javascript recursion.

So I thought why not go ahead, write down an article simplifying recursions along with bunch of examples to make it easier for you guys to understand the concept.

So let’s get started.

What is Javascript Recursion?

Javascript Recursion occurs when a function in a Javascript program calls itself either directly or indirectly.

One of the main purpose of writing javascript recursive function is that the code looks elegant plus it saves a lot of time when executing code. However, at the same time, Javascript Recursion should be used with care as it may have its own pitfalls.

 

Why Javascript Recursion is Used?

As said above, the main reason for writing Javascript Recursion is that it saves time of otherwise writing chunk of code. So you may get things done in fewer lines (or in some cases, consuming less resource) as compared to when you don’t use recursions.

This way, the code looks more elegant and concise.

 

Javascript Recursion Example

Without further ado, let’s get started with an example. After all, you learn more from an example rather than boring theory.

So here’s the first one. This time, let’s keep it simple just to let you know how Javascript Recursion actually looks like:

That’s the very first example I want to show you. But remember, “Don’t try this at home”.

What this program is doing is that it first creates a function called recursion and then calls itself within itself.

The last line is just executing the function.

The job of the function recursion is nothing but to call itself. So if you run this program in your system, you’ll get stuck with an infinite loop and your system will eventually freeze.

I hope now you get it why why I asked you not to try this at home.

Let’s Raise Our Game a Bit

Let’s try a bit complicated example than the last one. Shall we?

Suppose, you want to write a program, which prints numbers from 0 to 10. How’d you normally write it (without using a recursive function)?

Let me help you here:

The same can be achieved by using recursive function in Javascript.

If you execute the above code in console, it will print numbers from 1 to 10 by the function countTill() calling itself until it reaches the terminating condition which is “n is less than or equal to 10”.

That’s the basic example of a recursive function in Javascript.

Why Use Javascript Recursion?

As you may have noticed, there’s not big difference if you use a for (or other loop) instead of Javascript recursion. So all this fuss any way?

The basic reason is that it helps keep our code clean by avoiding creating unnecessary variables and putting onus on the javascript’s engine.

Above, in the program which contains a for loop, we have to create a new variable “i” in order to execute the program whereas in the second program, we executed the function itself hence there was no need to create any new variable.

Gradually as you transform into a “pro-programmer”, you will realize that it’s not a good idea to create unnecessary new variables every now and then and avoid it as much as one can.

I will discuss the reasons in detail in other article. So stay tuned.

How does Javascript Recursion Work?

In order to figure out and understand how recursion work in Javascript, we will have to dissect and go a bit deeper.

Theoretically speaking, the recursion breaks the execution of code into chunks and before jumping to the next chunk, it sees if the condition meets the terminating condition in our code.

If it doesn’t, it keeps on repeating the code and keep calling itself and as soon as it does, the code stops executing and the output is displayed.

So the important point to remember when writing a recursive function is that your code needs to have a terminating condition otherwise it will keep on going forever.

Let’s try something more complicated.

A classic example to understand recursion is calculating factorial.

Those who have no idea, what factorial actually is, it is actually the product of the series of number where every next number is one (1) less than it’s predecessor.

It’s a mathematical concept and represented by the sign, “!”

So factorial of 3 will be represented as 3! and its factorial will be:

3 x 2 x 1 = 6

Let’s write two programs to calulate the factorial of 7 (7!) and see how we can calculate factorial of any number using one of the javascript loops and then using javascript recursion.

Factorial Without Recursion


Factorial With Recursion

Talking about the above code, we have a terminating condition that as soon as the “num” variable is 0, return 1.

Otherwise, keep multiplying the num with factorial(num-1).

This means that before each multiplication, factorial() function is executed to see if the num variable is 0. If not then subtract 1 from the last instance of num and then multiply it by the last instance of num.

Keep doing it till num is 0 and as soon as it is, multiply whatever you have with 1.

Stop executing the code and then return the output.

I hope that this has start making sense now.

 

Reversing a String Using Javascript Recursion.

This is a bit complicated example so I want you to be attentive.

Before, starting on it, let me express my courtesies to Kevin Annis as this example has been inspired from one of his article, Recursion in Javascript.

Let’s start.

Say you want to reverse a string for e.g. “bear” so that the resulting string would be, “raeb”.

How can you do it using Javascript?

Note: I’m assuming that you know what the “substr” method does in Javascript.

The Javascript code to reverse a string using recursive function is:

Let’s dissect the Javascript code:

The function takes the string, “bear” and then checks if the length of the string is either 1 or less than 1. In case it’s not, then execute further.

return reverse( str.substr( 1 ) ) + str[ 0 ]; removes the first character of the string, “b”, and add it at the end of the remaining string so that “ear” and becomes “ear” + “b”.

The above result is “stacked” and the function runs again but this time with the string, “ear”, it takes the string, “ear”, removes “e” from it and adds it at the end of the string such that it becomes, “ar” + “e”.

The third time, it takes the string, “ar”, removes “a” and add it after “r” such that it becomes, “r” + “a”.

At the fourth execution, we reach our terminating condition. Since the length of the string is now 1, it’s time to stop executing the function and display the output.

Or in other words, return str;.

This process is also called as unwinding of the stack when every information which was stored (or stacked) by the Javascript is now displayed.

In our case, the output displayed is, “raeb”.

One important question that arises here that how the unwinding of the stack displays information in the manner explained above? Why not simply unwind in the sequence in which the information was stored in the first place.
For that, read my other article, How Javascript Stack Works?

So that’s it. I hope I have helped clear some of the basic confusion pertaining to the Javascript Recursion.

For any suggestions or corrections, don’t hesitate commenting below.

One thought on “Easy Guide to Javascript Recursion

Comments are closed.