How to Create Recursion in Java – Recursive Function

Recursion is the process of defining something in terms of itself. As it relates to Java programming, recursion is the attribute that allows a method to call itself. A method that calls itself is said to be recursive and Java supports recursion.

At first this may seem like a never ending loop, and it seems our method will never finish. This might be true is some cases, but in practice we can check to see if a certain condition is true and in that case exit (return from) our method. The case in which we end our recursion is called a base case. Additionally, just as in a loop, we must change some value and incrementally advance closer to our base case.

Every recursion should have the following characteristics:

1. A simple base case which we have a solution for and a return value.
2. A way of getting our problem closer to the base case. i.e. a way to chop out part of the problem to get somewhat simpler problem.
3. A recursive call which passes the simpler problem back into the method.

Advantages

The main to recursive methods is that they can be used to create clearer and simpler versions of several algorithms than can their iterative relatives. For example, the QuickSort sorting algorithm is quite difficult to implement in an iterative way.

Disadvantages

Recursive versions of many routines may execute a bit more slowly than the iterative equivalent because of the added overhead of the additional function calls. Many recursive calls to a method could cause a stack overrun. Because storage for parameters and local variables, it is possible that the stack could be exhausted. If this occurs, the java run-time system will cause an exception. However, you probably will not have to worry about this unless a recursive routine runs wild.

For example:

int myFactorial(int integer) {
  if( integer == 1) {
    return 1;
  }
  else  {
    return(integer*(myFactorial(integer-1);
  }
}

Tail recursion is defined as occurring when the recursive call is at the end of the recursive instruction. This is not the case with my factorial solution above. It is useful to notice when ones algorithm uses tail recursion because in such a case, the algorithm can usually be rewritten to use iteration instead. In fact, the compiler will (or at least should) convert the recursive program into an iterative one. This eliminates the potential problem of stack overflow.

This is not the case with head recursion, or when the function calls itself recursively in different places like in the Towers of Hanoi solution. Of course, even in these cases we could also remove recursion by using our own stack and essentially simulating how recursion would work.

In my example of factorial above the compiler will have to call the recursive function before doing the multiplication because it has to resolve the (return) value of the function before it can complete the multiplication. So the order of execution will be “head” recursion, i.e. recursion occurs before other operations.

To convert this to tail recursion we need to get all the multiplication finished and resolved before recursively calling the function. We need to force the order of operation so that we are not waiting on multiplication before returning. If we do this the stack frame can be freed up.

Previously you have seen our Java program to calculate factorial of an integer.

The proper way to do a tail-recursive factorial is this:

int factorial(int number) {
    if(number == 0) {
    return 1;
  }
  factorial_i(number, 1);
}

int factorial_i(int currentNumber, int sum) {
  if(currentNumber == 1) {
    return sum;
  } else {
    return factorial_i(currentNumber - 1, sum*currentNumber);
  }
}

Notice that in the call return factorial_i(currentNumber – 1, sum*currentNumber); both parameters are immediately resolvable. We can compute what each parameter is without waiting for a recursive function call to return. This is not the case with the previous version of factorial. This streamlining enables the compiler to minimize stack use as explained above.

You can also take the number from the user as a command line argument.

Java Recursion Program

class Factorial{
  int fact(int n){
    int result;
    if ( n ==1)
      return 1;
    result = fact (n-1) * n;
    return result;
  }
}

class Recursion{
  public static void main (String args[]){
    Factorial f =new Factorial();
    System.out.println("Factorial of 3 is " + f.fact(3));
    System.out.println("Factorial of 4 is " + f.fact(4));
    System.out.println("Factorial of 5 is " + f.fact(5));
  }
}

Output

Explanation of the Java Code & Output

If you are unfamiliar with recursive methods, then the operation of fact() may seem a bit confusing. Here is how it works. When fact()  is called with an argument of 1, the function returns 1; otherwise it returns the product of fact(n-1)*n. to evaluate this expression, fact() is called with n-1. This process repeats until n equals 1 and the calls to the method begin returning.

To better understand how the fact() method works, let’s go through a short example. When you compute the factorial of 3, the first call to fact() will cause a second call to be made with an argument of 2. This invocation will cause fact() to be called a third time with an argument of 2. This call will return 1, which is then be called a third time with an argument of 1. This call will return 1, which is then multiplied by 2 (the value of n in the second invocation). This result (which is 2) is then returned to the original invocation of fact() and multiply by 3 ( the original value of n). This yields the answer, 6. You might find it interesting to insert println() statements into fact() which will show at what level each call is and what the intermediate answers are.

When a method calls itself, new local variables and parameters are allocated storage on the stack, and the method code is executed with these new variables from the start. A recursive call does not make a new copy of the method. Only the arguments are new. As each recursive call returns, the old local variables and parameters are removed from the stack, and execution resumes at the point of the call inside the method.

Next we will learn how to deal with Array in Java.

Checkout more useful tutorials and definitive guidelines on Java programming here.