Recursion

Java Chapter 11 - Recursion

11.1 Divide and Conquer

Recursion is a way to solve a problem by dividing it into subproblems of the same type (divide and conquer). It is typically implemented by creating a method that solves a portion of the problem, then calls itself with the remainder of the problem. For example, to calculate 8 factorial, you could solve it by multiplying 8 by 7 factorial. More precisely, x! = x * (x-1)!

Therefore, you could write a method to calculate x! by returning x * Factorial(x - 1). You could begin writing the method like this:

int Factorial (int x)
{
   return x * Factorial(x - 1);
}

The problem with the preceding code is that it would be an infinite loop/recursion. Loops (and recursive methods) need a way to eventually terminate. You can terminate the recursion by returning 1 when x gets to 1:

int Factorial (int x)
{
   if (x == 1)
      return 1;   // Terminate the recursion when x gets to 1
   else
      return x * Factorial(x - 1);
}

The following is a complete recursive factorial program:

thatsthefact.java

public class thatsthefact
{
   public static void main (String[] args)
   {
      System.out.println("8! = " + Factorial(8));
   }

   public static int Factorial (int x)
   {
      if (x == 1)
         return 1;   // Terminate the recursion when x gets to 1
      else
         return x * Factorial(x - 1);
   }
}

Output

8! = 40320

Below is another example of recursion. The method counts the number of dollar signs ( $ ) in a string. This can be done with a for loop by stepping through each character in the string. It can also be done recursively by looking at the first letter of the string and calling the method again with the remainder of the string.

int DollarSigns (String w)
{
   if (w.length()==0) return 0;   // Terminate the recursion when the length of w is 0

   if (w.charAt(0)=='$')
      return 1 + DollarSigns(w.substring(1));
   else
      return DollarSigns(w.substring(1));
}

11.2 Evaluating the Efficiency of Recursion

Recursion is a unique and sometimes simpler method to solve problems. However, it can sometimes lead to a substantial number of method calls and a significant amount of CPU time. Therefore, it is often not the most efficient algorithm to solve a problem. Two ways to evaluate the efficiency of a recursive program are to count the number of method calls and the amount of CPU time.

thatsthefact.java

import java.util.*;

public class thatsthefact
{
   static int methodCount=0; // define global variable to count method calls

   public static void main (String[] args)
   {
      long startTime = System.nanoTime();
      System.out.println("20! = " + Factorial(20));

      long endTime = System.nanoTime();
      System.out.println("Elapsed Seconds = " + (double)((endTime - startTime)/1000000000.0));
      System.out.println("Method calls = " + methodCount);
   }

   public static long Factorial (int x)
   {
      methodCount++;
      if (x == 1)
         return 1;   // Terminate the recursion when x gets to 1
      else
         return x * Factorial(x - 1);
   }
}

Output

20! = 2432902008176640000
Elapsed Seconds = 0.000545525
Method calls = 20