What are recursions?

Recursions or recursive functions are functions that call themselves in their definition. This creates a looping effect similar to for and while loops.

Now since recursions call themselves and operate similiar to loops, there has to be some point at which they stop calling themselves - or else the recursion would keep on running and running! This point is always brought about by a conditional statement and is called the base case. The base case is defined as the point at which the recursive functions stops calling itself.

Before the base case, every case we have is called the recursive case i.e the function calls itself.

Recursions are an integral part of modern day algorithmic computing and can be used to solve a lot of problems of code. Understanding them well is a key part to you being able to solve such problems. Let's now move on to grill those recursions but know that this chapter won't be a piece of cake! Careful reading is the solution.

Function completion

Before moving on to begin with recursions there are a couple of things to be aware, that will be part of recursions.

Functions only exit when all their statements are completely executed or when a return statement is encountered.. And by exit we mean completion.

So let's suppose you have a function logInUser() and two other functions with some code (shown by dots below).
function authenticate() {
    // .... many functions
}
function connectDatabase() {
    // .... many functions
}

function logInUser() {
    connectDatabase();
    authenticate();
}
The function logInUser() will exit when all its statements are completely executed. In this case when authenticate() and connectDatabase() functions are completed and exited only then can the logInUser() function exit. And authenticate() and connectDatabase() functions will exit when the functions in them complete and exit. Hence all statements in a functions definition have to be completed when to finish a functions execution.

And for the other way, functions can also exit if they encounter the return keyword.
function randomNum() {
    /* 
    ... some code ... 
    */
    if (x !== 0) { return 0.55; } 
    /* 
    ... some more code ... 
    */
}
Here if the specified condition is met and consequently the return statement is executed the function exits. This also means that the code beneath line 5 would not be executed since the function has returned.

Both these ideas will be used in explaining bits of this above code so make sure you understand all this.

First recursion

The following code recursively outputs 3 numbers starting from 0 to 2 just like a for loop.
var num = 0;
function counter() {
    console.log(num++);
    if (num > 2) { return; }
    counter();    
}
counter();
So when the function counter() is called in line 7 what happens? Let's split it up into pieces:

First counter function

  1. First of all the variable num is logged in the console and incremented afterwards. Therefore initially 0 is logged and then num becomes 1.
  2. Then we check if num is greater than 2 and that we have reached the base case. In this case the condition fails hence we move on to line 5 and counter is called again.

    Second counter function

    1. num is logged as 1 and then increments to 2.
    2. The condition is ran again and it again fails (2 < 2 is false). Therefore again counter is called.

      Third counter function

      1. num is logged as 2 and then increments to 3.
      2. Now since the condition is met the return statement is executed and this third counter function exits.
      3. We are done with the third counter.
    3. With the the third counter function complete we are done with the second counter function.
  3. With the the second counter function complete we are done with the first counter function and our recursion exits within finite number of steps.
Now this part of the chapter may be the most difficult to understand so to make it a bit more understandable we have employed indentation and bordering to help keep track of the function currently being executed.

As we said earlier in this chapter a function doesn't complete until all its commands are completed. Likewise the function counter() called at the start (first counter function) doesn't complete until all its subsequent functions complete and exit.

And all the functions start exiting, starting from the base case function (third counter function in this case). This means that when the base case is reached the lowest function exits and accordingly all the functions in the chain start completing up.

Without a base case a recursion will never stop and run continuosly calling itself again and again and in the end crashing the browser. If we rewrite the counter() function like this we have actually created an infinite recursion - the first counter function and all sub functions will never complete since on every occasion a further function gets called without any point of termination.
var num = 0;
function counter() {
    console.log(num++);
    // if (num > 2) { return; } condition removed
    counter();    
}
counter();
And this is the most important thing to plan when writing a recursion i.e at what point shall there be a stop applied to function calls..