Introduction To Recursion

In data structure and algorithms, Recursion plays an important role. In this article, we will look at a brief introduction to Recursion.

Introduction 
 
In data structure and algorithms, the concept of Recursion plays an important role. In this article, we will go over a brief introduction to Recursion.
 
Recursion is a technique involving the use of a procedure, subroutine, function or algorithm that calls itself in a step along with some termination condition.
 

Properties

  1. The same operation is performed multiple times with different input
  2. In every step, we try to make the problem smaller
  3. We need to have a base condition which tells the system to stop the recursion
Let's take a small example:
 
(Here I will write the algorithm and later will implement it with Javascript, but you can choose your own language).
 
We will use the example of the summation of 10 numbers in an array with Recursion
 

Algorithm

  1. DisplayArray(arr, index) :  
  2. start  
  3.       If(index< 0) :  
  4.                    return false  
  5.      DisplayArray(arr, index-1)  
  6.      Print(arr[index])  
  7. End  
Let’s check whether or not this Algorithm satisfies the Recursion properties:
  1. The DisplayArray method is called with different parameters. In each call, the index is reduced, hence satisfying the first property
  2. We are reducing the index every time, hence the second property is also satisfied
  3. If the index becomes less than 0 then the algorithm will break, hence we can say this is the Base condition. Therefore, the third property is also satisfied.

Format of a Recursion Function

  1. Recursive Case: the case where the algorithm recurs (i.e method will call itself)
  2. Base Case: the case where method will not call itself, (i.e terminating condition)
Therefore...
 
SampleRecursion(parameter1, parameter2 ,…):
If(base case is satisfied):
    Return some value
Else :
    SampleRecursion(modified parameter)
 

Recursion Working Principle

 
In a programming language, a method is stored in a stack which follows Last In First Out (LIFO). Whenever a method is called but, due to some condition, it must be executed down the road, the method is saved in stack memory. A program counter (PC) will hold the memory location so that it will be referenced later on.
 
Let's discuss the subject with an example:
 
 
  1. Tst(n):  
  2. start  
  3.     If(n < 1):  
  4.         Return  
  5.     Else:  
  6.         Tst(n-1)  
  7.    Print(“Hi” + n)  
  8. End  
  9.   
  10. Main():  
  11.  start  
  12.    Tst(3)  
  13.  end  
 
 
Now let's see what’s happening
  • Main calls Tst with the parameter 3 and the controls go to method Tst, hence the Main method is not finished yet, so it gets saved into the stack memory
  • Since at first, Tst(3) is called (n<1) is not satisfied so it will go to the Else. Here, it will call itself again with n-1. Hence, the Tst(3) is function is not completed since it does not go to the next line, Print(“Hi”+n). Tst(3) will be stored into the stack memory to be executed later.
  • Next, in a similar fashion Tst(2) and Tst(1) are called and get stored into the stack
  • When Tst(0) is called, (n<1) which is the base condition meets the criteria. Hence, it’s going to terminate the algorithm. Here the program counter takes control and finds in the stack when the function was called at last time and with what parameter (if there is any).
  • Since as discussed, methods get stored in stack memory in a LIFO pattern, Tst(1) will be executed first.
  • Tst(1) is executed, which means the remaining part of the method to print, “Hi 1”, will be printed. Now that Tst(1) is completed, it will be popped out of memory and the PC will execute Tst(2), and then Tst(3).
 
 
Here is the code snippet of the following:
  1. function Tst(n){    
  2.   if(n<1)    
  3.     return    
  4.   else{    
  5.     Tst(n-1)    
  6.   }    
  7.   console.log("Hi"+n)    
  8. }    
  9.     
  10. Tst(3)