Post
Ask Question

Recursion Core Concepts

Introduction

 
In data structure and algorithms, recursion plays an important role. In this article, we will look at a brief introduction to Recursion.
Recursion is a technique involving the use of procedure, subroutine, functions, or algorithms that calls itself in a step with some termination condition.
 
Properties
  1. The same operation is performed multiple times with a different input
  2. In each step, we try to make the problem smaller
  3. We need to have a base condition which tells the system to stop the recursion
Here's a small example:
 
(Here I will write the algorithm and will later implement it with Javascript, however, you can choose your own language.)
 
Let’s take an 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 
Now let’s check whether this Algorithm satisfied the Recursion properties or not.
 
The DisplayArray method is called with different parameters, as in each call the index is reduced, hence satisfying the first property.
 
We are reducing the index every time, hence the second property is also satisfied.
 
If the index becomes less than 0, then the algorithm will break. Therefore, we can say that this is the Base condition, hence the third property is also proved.
 
Format of Recursion Function
 
1) Recursive Case: Case where the algorithm recurs (i.e method will call itself)
 
2) Base Case: Case where the method will not call itself. (i.e terminating condition)
 
e.g
  1. SampleRecursion(parameter1, parameter2 ,…):  
  2.     If(base case is satisfied):  
  3.           Return some value  
  4.     Else :  
  5.           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 needs to be executed later on, the method gets saved in the stack memory and a program counter(PC) will hold the memory location so that it will later be referenced.
 
Let’s discuss 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 parameter 3, and the controls go to method Tst, hence the Main method is not finished yet, so it gets saved into stack memory.
 
Since at first, Tst(3) is called (n<1) is not satisfied so it will go to Else part where it will call itself again with n-1. Hence here, also Tst(3) is a function that is not completed since it does not go to the next line, Print(“Hi”+n). Therefore, Tst(3) will be stored into stack memory to be executed later.
 
Next in a similar fashion, Tst(2) and Tst(1) are called and stored into the stack
 
When Tst(0) is called, (n<1) it is the base condition that meets the criteria and hence it’s going to terminate the algorithm. Here the program counter takes control and finds in the stack where the function was called at last time and with what parameter (if there is any).
 
Since as discussed, methods get stored in the stack memory in a LIFO pattern, Tst(1) will be executed first.
 
Tst(1) gets executed, meaning the remaining part of the method, “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)  
Now I think you all have a brief idea of how a recursive method works. Let's check one of the common problems, the factorial of a number.
 
Algorithm
 
 
  1. Factorial(n):  
  2.             Start  
  3.                   If(n == 0):  
  4.                         Return 1  
  5.                   Return (n * Factorial(n-1))  
  6.             End  
When n = 0, it returns 1 and the control goes to stack at the top. Thus 1 x ? will now become 1 x 1, which will return 1.
 
Now the PC will go to the next block and 2 x ? will replace 1. It will then return 2*1  = 2, and this goes on until all the blocks have been completed. 
 
 
 
Advantages
  • The main advantage of a a recursive approach to an algorithm is that it allows programmers to take advantage of the repetitive structure present in many problems.
  • Complex case analysis and nested loops can be avoided in a simple way.
  • Recursion can lead to more readable and efficient algorithm descriptions.
Disadvantages
  • Slowing down of execution time on the run-time
  • If the recursion is too deep, then there is a the danger of running out of space on the stack and ultimately the program crashes.
  • If Base condition is not satisfied, it could lead to stack overflow