JavaScript Function Recursions

Recursions aren't a concept native to programming. In fact, long before programming become a routine activity, recursions were a paramount part of mathematics.

There were ideas of recurrence relations, recursive functions, solving these recurrences using various theorems, and so on and so forth. Let's also not forget the famous Fibonacci sequence which was also defined as a recurrence relation. Even to some extent, mathematical induction is a form of recursion.

So, in short, programming didn't introduce the powerful idea of recursion — it existed well before it. But what programming did was to largely benefit from this ingenious mathematical idea and even make it way more practical than it might have otherwise been.

Now let's come to the main question: what is recursion?

We'll use the perspective of JavaScript.

On the same lines, a recursive function is a function that implements recursion.

When a recursive function is called, it's body executes where it calls itself. Then that second invocation happens and it also calls itself. Next, the third invocation happens and then it calls itself, again. This goes on and on until a termination point when the whole chain of successive calls of the function start to end.

This termination point is referred to as the base case of the recursion. All other cases are called recursive cases.

And that's it.

Time to consider some examples from our old friend — mathematics.

The factorial of an integer ::n::, commonly denoted as ::n!::, is the product of all integers from ::n:: down to ::1::. In format notation, this can be expressed as:

Notice how the factorial function exists on both sides of the equation. This is why it is termed as a recursive function, i.e. its definition includes itself.

The case when the recursion ends is when we reach ::1!::, which is simply equal to ::1::. As a side case, even ::0!:: is defined in order to make certain expressions defined.

Altogether, we can represent the factorial function as follows:

Now let's come back to programming.

If we want to express this mathematical function as it is in JavaScript, we can do that very easily:

function factorial(n) {
   if (n === 0 || n === 1) {
      return 1;
   }
   return n * factorial(n - 1);
}

Notice very carefully the definition of factorial() here. First, we have an if conditional to check for the case when we have an answer right away and don't need to perform a recursion.

If the conditional fails, we return the expression n * factorial(n - 1). This is where the recursion comes into the game.

Let's try running the factorial() function on a couple of integers:

factorial(0)

factorial(1)

factorial(3)

factorial(4)

factorial(10)

Quite amazingly, the results are all correct. And they should be — after all, the definition of factorial() is identical to the mathematical definition shown above.

If you're thinking on how could factorial()'s definition refer to itself, know that this requires just a little bit of insight into the internals of the language. We'll cover these shortly in the latter part of this course.

As another example to help understand recursion much better, we'll use the well-renowned Fibonacci sequence.

The Fibonacci sequence is an outcome of a recurrence relation attributed to the italian mathematician Leonardo Bonacci. It's popular because of its relation to the golden ratio which can be seen in an array of natural phenomena.

The recurrence relation is the following:

with the initial conditions ::\text{F}(0) = 0:: and ::\text{F}(1) = 1::. Using this recurrence relation, the first 10 elements of the sequence are as follows:

Let's now define this function in JavaScript.

function fib(n) {
   if (n === 0) {
      return 0;
   }
   if (n === 1) {
      return 1;
   }
   return fib(n - 2) + fib(n - 1);
}

Time to test it:

fib(0)

fib(1)

fib(5)

fib(9)

And it works flawlessly.

Note that this time the function fib() recursively calls itself twice, for each call. Previously, the factorial() function called itself recursively only once. There is technically no limit to the number of per-call recursions we can make.

However, typically they are just one, two or three (or maybe, even four) in most, if not all, cases.

Alright, it's now finally time to see how recursion works under the hood in JavaScript. The information given below can be applied to recursions in nearly all mainstream programming languages.

To start with, let's understand how is a function parsed in JavaScript.

With the parsing of a function understood, the next step is to understand the idea of a call stack.

Call stacks are really important for programmers to be aware of since they are used in error messages when a program runs into a recursion with many pending calls or, in the worst case, into an infinite recursion.

To boil it all down, under the hood, recursion in JavaScript happens quite intuitively, without really having to make any kind of special arrangements.

One important thing to note before ending this section is that since recursive functions (which are an instance of nested functions) line up on the call stack as called, there is a limit to this stack imposed by the JavaScript engine. At least, in the browser environment, there is no way to increase this limit, but to strictly remain below it.

The exact limits vary from browser to browser.

One very simple code can be used to check the exact limit. Here's the code:

var recursionLimit = 0;

function r() {
   recursionLimit++;
   r();
}

r();

Run this code and wait for the browser to throw an error when the number of recursions lying on the call stack exceed the maximum allowed. At that point, just retrieve the value of recursionLimit.

Below is an illustration from Google Chrome's developer's console:

The output 13953 here tells us that in Google Chrome, the recursion limit is close to 14,000.

Anyways, due to this limit on the number of recursions allowed, it's usually advised to favor iteration over recursion whenever possible.

Iteration typically has less overhead than recursion, in addition to having no limit on the number of iterations allowed. Many recursive algorithms can be implemented very easily using an iterative approach.