## What are 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.

A recursion is to call a function from within itself.

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

Recursion is the act of calling a function from within itself, whereas a recursive function is a function that performs this action.

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 function

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:

$n! = n \times (n - 1)$

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:

$n! = \begin{cases} 1 &\text{if } n = 0 \text{ or } n = 1 \\ n \times (n - 1)! &\text{otherwise} \end{cases}$

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 rightaway 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)
1
factorial(1)
1
factorial(3)
6
factorial(4)
24
factorial(10)
3628800

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.

## The Fibonacci sequence

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:

$\text{F}(n) = \text{F}(n - 2) + \text{F}(n - 1) \space\space\space\space (\text{for } n \ge 2)$

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:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34$

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)
0
fib(1)
1
fib(5)
5
fib(9)
34

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.

## How recursion works?

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.

#### Parsing a function in JavaScript

When reading a JavaScript program, the moment a function is encountered, its body is alloted space in memory after being compiled.

'Compiled' simply means that the body is converted into a set of precise machine instructions so that each time the function is called, there is no need to convert the body to machine code again and again.

Once this allotment of space in memory is done, step two is to take the address of the location where this code dwells in memory and assign that address to the name of the function. Hence, after alloting space to a function f()'s body, f would internally point to some memory location containing its respective body.

In the case of a recursive function (which contains a call to itself in its body), there is absolutely nothing special to be done by the engine to parse and consequently compile it.

The recursive call inside the function simply refers to the address where the function's code sits in memory. All the magic of recursion automatically happens when the machine code of the function's body (in memory) refers to itself via the same memory address.

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.

#### Frames and the call stack

The moment a function is called in JavaScript, all the local variables and parameters of the function are created in a new unit commonly referred to as a context, or a frame. This whole unit is alloted space in a special data structure known as the call stack.

The reason for choosing a stack for holding function frames is due to the nature of nested function calls.

That is, the last call in a series of nested function calls is to be evaluated first, followed by the second last call, followed by the third last call, and so on, until we reach the initial function. This resembles the stack data structure where the last item added is evaluated/removed first.

Anyways, coming back to the idea of a function frame, the point at which the function exits, this whole frame is removed — or better to say, popped off — from the stack.

In the case of a recursion, when the main function is called, its frame is pushed (i.e. added) on to the stack, followed by the execution of its body.

Since it's a recursive function, its body calls itself. This pushes another frame on to the call stack, followed by executing this new function's body. Once again, another recursive call leads to another frame. And so on and so forth.

As we reach the base case of the recursion, the current function exits and then one-by-one all the pending functions are exited starting with the ones called last. When the functions exit, their frames are popped off the stack (including all local variables and parameters) thereby freeing up memory space.

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:

Uncaught RangeError: Maximum call stack size exceeded at r (<anonymous>:4:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4) at r (<anonymous>:5:4)
recursionLimit
13953

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.