Recursion in Java with Example

Recursion occurs when a function calls itself in its own body. That is, in the body of the function definition there is a call to itself. When the function calls itself in its body, it results in an infinite loop. So, there has to be an exit condition in every recursive program.

The case in which the recursion ends is called a base case. In every recursive program, the problem is broken into small pieces so as to bring it closer to the base case.

Methods/Functions have locally defined variables (or objects) which have no existence outside the function. Each time a function is invoked recursively, a new set of variables (or objects) are created. Although they have the same names, their values are preserved till the end of the recursion. So, to implement recursion, the language has to take the help of stack to keep track of objects and statements of each recursive call.

Demonstrating the Concept of Recursion

class ConceptofRecursion 
 { 
             void display(int x,int y) 
             { 
                         if(x<1) return; 
                         System.out.println("Value of x : "+ x ); 
                         display(x-1,y+1); 
                         System.out.println("Value of y :"+y); 
             } 
             public static void main(String args[]) 
             { 
                         ConceptofRecursion Recursion = new ConceptofRecursion(); 
                         Recursion.display(5,1); 
             } 
 } 
 

As, we can see in the above program, that the method display () is invoked with two arguments 5 and 1 which will be assigned to parameters x and y respectively. In display ()  method, value of x is displayed which prints following message on the screen : Value of x: 5

Then again display ()  is invoked with values 4 and 2 (because value of x is decremented and value of y is incremented by 1 while invoking the display (). But because of the recursive call, one statement of the program couldn’t execute, that statement is:

System.out.println(“Value of y :”+y);

So, the message: Value of y : 1 is pushed on to the stack.

By the recursive call, the values 4 and 2 will be assigned to parameters x and y respectively. Here, value of x is displayed which prints following message on the screen:

Value of x: 4

Again, display ()   is invoked with values 3 and 3 (because value of x is decremented and value of y is incremented by 1 while invoking the display () . But again, because of the recursive call, the following statement couldn’t execute:

System.out.println(“Value of y :”+y);

So, the message: Value of y: 2 is pushed on to the stack (above the message Value of y : 1) and so on. Hence, 5 messages will be pushed onto the stack which couldn’t execute as shown:

Disadvantages of Recursion

1. The problem of stack overflow occurs in case of infinite recursion

2. Recursion can be slower to run than simple iteration.

3. The recursive version is usually less efficient because of having to push and pop values on and off the run-time stack, so iteration is quicker.

Advantages of Recursion

1. It is easier to code a recursive solution.

2. The recursive code is usually smaller, more concise, and more elegant.

3. There are some real time problems that are very difficult to solve without recursion.