Recursion

Recursion is a strategy that algorithms use to solve specific problems. A recursive algorithm is an algorithm that solves the main problem by using the solution of a simpler sub-problem of the same type. Recursion is a particular way of solving a problem by having a function calling itself repeatedly. It is always applied to a function only. By using recursion, we can reduce the size of the program or source code. In recursion, a function invokes itself. And the function that invokes itself is referred to as a recursive function.

Suppose we have a user-defined function named ‘recursion’, and it will be written in the main function. The compiler will execute the recursion function automatically, and it will search for a particular function definition. This function definition will be executed, and control will go back to the main function. If we call the same function inside the function definition, then the compiler will move on to function definition first. When the compiler executes the recursion function, we will be calling the same function.

function main(){
   function recursion() {
    // function code
    recursion();
    // function code
   }
   recursion();
}

main();

This recursion process will be executed infinitely until we apply the exit condition. A recursion should have two things:

1. ‘Base’ or ‘Exit’ condition.

2. Recursive function call.

Without base condition, the program will not stop. The base condition helps us to prevent infinite recursions of a function. We can call a function directly or indirectly in recursion.

Working

In recursion, the main problem can be solved by using a simpler subproblem of the same type. This can be done until the problem becomes so simple that a declarative answer can be provided. Once a definite answer is provided through step-by-step substitution, the main problem can be solved. This how recursion works.

Suppose we need to compute the factorial of 5. So, we will call the function factorial of 5.Factorial of 5 is equal to :

We can also write a factorial of 5 as:

It is easy to ascertain that for any value of ‘n’ , its factorial will be n into n minus 1 factorial.

For calculating the factorial of 5, if we break it down into a simpler subproblem and use that solution. Then we can say that factorial of 5 is equal to:

We call the function factorial and ask it to find the factorial of 5. That called function will say OK, and it will calculate the factorial of 5, but it will need a factorial of 4.Because the factorial of 5 is equal to 5 into factorial of 4. At this point, the function will make a call to itself. And we are calling the same function within the function. Now, the function will run again to find the factorial of 4, which will be equal to 4, into a factorial of 3.

Within the function, the function will call itself again. Now function for factorial of 3 will be run. Factorial of 3 will be equal to 3 into factorial of 2.

It can be seen that problem size is going to be reduced. Similarly, we will have functions of factorial of 2 and 1.

So the problem size given to the function will keep on reducing at a point the problem will become so simple that we don’t need computations to solve it. So we have reduced the above function until the point where we have to find the factorial of zero. So, we have reduced the problem to such a state where it has become so simple that we have a defined answer. And there is no computation for that particular case.

As the factorial of 0 is equal to 1, we can put it previous function where the factorial of 1 will become 1.Using this, we can arrive at the factorial of 2 and substitute 1 in it. Similarly, we will keep on substituting the factorial function in its previous function. It can be seen that we have solved the main problem by using the solution of simpler sub-problems. At each time, we are finding the solution to the problem by using the subproblem solution.

Types of Recursion

A recursion has the following major categories:

1. Direct Recursion

2. Indirect Recursion

3. Tail Recursion

4. Non-Tail Recursion

Direct Recursion

In a direct function, we call the same function directly in its main body. It can be seen below that we have the function ‘recursion’, and it is called with the same name in its main body. So, this is direct recursion.

function recursion() {
    // function code
    recursion();
    // function code
   }
}

Indirect Recursion

In an indirect recursion, a function indirectly calls the original function through some other function. It can be seen below, there is a function ‘recursion1’, and we call another function ‘recursion2’ in its main body. Then we call the ‘recursion1’ in the definition of ‘recursion2’. So, the recursion occurs here indirectly.

recursion1(){
    recursion2();
}
recursion2(){
    recursion1();  
}

Tail Recursion

In a tail-recursion, a recursive call is a final thing done by the function. Thus, there is no need to keep a record of the previous state.

If we see the following code, there is a function defined with the name ‘recursion’. So it can be seen that the last operation performed in this is ‘recursion’. So recursive statement is executing at the end, and no function will be performed after that. And there is no need to keep the record in the stack because there will be no record use in the stack, and it will be useless.

function recursion(n){
 if(n == 0){
   return;
 }else{
   console.log(n);
   return recursion(n - 1);
 }
}

Now we write the main program as shown below and pass 3 in it.

function main(){
  recursion(3);
  return 0;
}

Let us comprehend this along with the help of a stack. Suppose we make a stack. The program will start from the main in this stack, and an activation record will be formed of the main function. Activation record tells that for how much time the record will remain active. Then recursion(3) will be called. In the main function, as 3 is not equal to 0 so it will print 3 and will return recursion(2). Now, 2 is also not equal to 0, so it will print 2 and return recursion(1). And activation record recursion(1) will be created in the stack. Then 1 is not equal to 0, so 1 will be printed. Now 0 will be returned.

Non-Tail Recursion

A recursion function is called non-tail recursive if recursion is the not last thing done by the function. There is a need to keep a record of the previous state.

Let us take the previous example in which we have defined the function ‘recursion’. As compare to tail recursion, now operation will not end after function ‘recursion’, and some other operation will also be performed after the recursion function call. We will remove the print statement after if condition and write ‘recursion(n-1)’.And we write the print statement. Recursive function ‘fun’ is not calling at the last but the is print statement after that.

function recursion(n){
 if(n == 0){
   return;
   recursion(n - 1);
   console.log(n);
   return recursion(n - 1);
  }
}

Its main program will be similar to the tail recursion main program and pass 3 in it.

function main(){
  recursion(3);
  return 0;
}

Now let us see it's working in the activation record. The program will start from the main, and an activation record will be formed of the main function. Then recursion(3) will be called. As 3 is not equal to 0, so again recursive will be called, and control will not go to print statement. After calling recursive, 2 will be created in the activation record. Condition ‘if’ will be failed, and recursive will be called again. And 1 will be created in the activation record. And finally, it will be returned for 0.

Pseudo Code of Recursion

To understand the pseudo for recursion, let us take an example of a factorial number. We have named a factorial function as ‘fa’ and take some input as input parameter for which we want to find factorial. An integer will be returned because we want to find the factorial of a number. The factorial of any number in the solution will be n into the factorial of n minus 1. We will keep on returning the solution until this problem becomes so simple that we directly answer without making another function call. The condition will be that if the n is equivalent to zero, then the solution will be 1. So when we have to calculate 0 factorial, we said that solution was 1. So off course, we want to return the solution.

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

Fibonacci Series Implementation Using Recursion

The Fibonacci series is usually denoted by:

In this series, the next value is the total of the previous two values. We can represent this series in the form of the array as:

There are a total of 7 indexes from 0 to 6. In this array, Fibonacci at index 3 is equal to the Fibonacci of index 2 plus Fibonacci of index 1. Similarly, Fibonacci at index 2 is equal to Fibonacci of index 1 plus Fibonacci of index 0.

In a generalized form, it will be:

Now in case of its recursive function,if the value of ‘n’ is greater than 1 then Fibonacci sequence will be equal to ‘fib (n-1)’ plus ‘fib (n-2)’. And if the ‘n’ is less than or equal to 1 then Fibonacci sequence will be equal to ‘n’.

In recursion, firstly, we will call the Fibonacci function ‘f(n)’.Lets assume that the n is 5. As the n is greater than 1, so fib(5) will be equal to fib(4) and fib(3). Now we will completely solve fib(4) and then fib(3). When we call fib(4), then it will call fib(3) and fib(2). Then fib(3) will call fib (2) and fib(1). Now fib(2) will call fib(1) and fib(0).

function fib(n){
    if(n < 2) {
        return n;
    }
    else {
        return fib(n - 1) + fib(n - 2);
    }
}

Advantages and Disadvantages of Recursion

Advantages

It has the following benefits:

1. It is easy to write. It means that we have to write small code for a recursive function.

2. It reduces time complexity.

3. We have to write a lesser number of lines as an iterative technique, so the size of code decreases in it.

4. It adds clearness and decreases the time required to write and debug code.

Disadvantages

It has the following disadvantages:

1. It consumes more storage space due to the use of the stack. To solve the recursive function, the stack is used, so it requires more storage space than the iterative technique.

2. A computer may run out of memory if the terminating condition is written wrong.

3. It is not efficient in terms of speed and time.

Applications of Recursion

It has the following applications:

1. Recursion is used in different types of data structures like linked lists and trees.

2. It is used to implement sorting techniques such as merge sort and quick sort because their implementation becomes different with iterative approaches.

3. Recursion is used to find all files in a folder and subfolder in the hierarchy.

4. It is also used in elevator programming.