Head Recursion

Now, let us understand Head Recursion. Following is the structure of head recursion. If there is a function that is calling itself, then it is a recursive function. As you can see in the below example, the function fun calling itself, so it is a recursive function. Then, if you further notice, the first statement inside the function is the recursive call. That means, what all the processing it has to do, it is doing at returning time, i.e. after the recursive call. There is no statement that is no operation before the function call.

Void fun( int n ) { 

if( n > 0) {
 fun(n-1); // head recursion 

 statement1

 statement2

 ……….. 
 }
 }

Note: If there is something before the recursive call then it is not a head recursion. If something is there before the function call, it is just a recursion. We don’t have to give any special name for it. The following is not head recursion.

Void fun( int n ) { 

if( n > 0) {

statement;

 ……….. 
 fun(n-1); //call function itself

 statement1;

 statement2;

 ……….. 
 }
 }

• Here the first statement inside the function is recursive call and all the processing of this function will be done after that.

• In head recursion the function doesn't have to process any operation at the time of function calling it has to do everything at the time of returning such functions are head recursion.

Head Recursion to Loop 

• Although it is possible but It is difficult to convert head recursion into a loop function.

Example-:

public class Test{

public static void fun(int x){

   if(x>0){

     fun(n-1);

     System.out.print(n);

   }

}

public static void main(String... args){

 fun(5);

}

}

output-: 1 2 3 4 5

Note: The point that you need to remember is if a recursive function does some operation at returning, then it is not easy to convert that recursive function to a loop. We need to convert by writing some logic.

Time Complexity: The time complexity of Head Recursion is O(n).