<< Chapter 12 | HomeworkTrailIndex | Chapter 14 >>

Recursion

Demo 1: Triangle Numbers

We begin this chapter with a very simple example that demonstrates the power of thinking recursively. In this example, we will look at triangle shapes such as the ones from Section 6.3. We'd like to compute the area of a triangle of width n, assuming that each [] square has area 1. This value is sometimes called the nth triangle number. For example, as you can tell from looking at

[]
[][]
[][][]

the third triangle number is 6.

public class Triangle
{
   public Triangle(int aWidth)
   {
      width = awidth;
   }

   public int getArea()
   {
      //your code here
   }

   private int width;
}

Demo 2:Permutations

We will now turn to a more complex example of recursion that would be difficult to program with a simple loop. We will design a class that lists all permutations of a string. A permutation is simply a rearrangement of the letters. For example, the string “eat” has six permutations (including the original string itself):

"eat"
"eta"
"aet"
"ate"
"tea"
"tae"

As in the preceding section, we will define a class that is in charge of computing the answer. In this case, the answer is not a single number but a collection of permuted strings. Here is our class:

PermutationGenerator.java

public class PermutationGenerator
{
   public PermutationGenerator(String aWord) { . . . }
   ArrayList<String> getPermutations() { . . . }
}

Here is the test program that prints out all permutations of the string “eat”:

PermutationGeneratorDemo.java

 import java.util.ArrayList;
 /**
    This program demonstrates the permutation generator.
 */
 public class PermutationGeneratorDemo
 {
    public static void main(String[] args)
    {
       PermutationGenerator generator
             = new PermutationGenerator(“eat”);
       ArrayList<String> permutations = generator.getPermutations();
       for (String s : permutations)
       {
          System.out.println(s);
       }
    }
 }

Demo3: Palindromes

Consider the palindrome "MOM" or "Do geese see God" -- they are the same if you spell them backwards. It is a bit inefficient to construct new Sentence objects in every step. Now consider the following change in the problem. Rather than testing whether the entire sentence is a palindrome, let's check whether a substring is a palindrome:

public class Sentence
{
   private String text;
   /**
      Constructs a sentence.
      @param aText a string containing all characters of the sentence
   */
   public Sentence(String aText)
   {
       text = aText;
   }

   /**
      Tests whether this sentence is a palindrome.
      @return true if this sentence is a palindrome, false otherwise
   */
  public boolean isPalindrome()
  {
   return isPalindrome(0, text.length() - 1);
  }





  /**
   Tests whether a substring of the sentence is a palindrome.
   @param start the index of the first character of the substring
   @param end the index of the last character of the substring
   @return true if the substring is a palindrome
  */


  public boolean isPalindrome(int start, int end)
  {
   // Separate case for substrings of length 0 and 1.
   if (start >= end) return true;

   // Get first and last characters, converted to lowercase.
   char first = Character.toLowerCase(text.charAt(start));
   char last = Character.toLowerCase(text.charAt(end));

   if (Character.isLetter(first) && Character.isLetter(last))
   {
      if (first == last)
      {
         // Test substring that doesn't contain the matching letters.
         return isPalindrome(start + 1, end - 1);
      }
      else
         return false;
   }
   else if (!Character.isLetter(last))
   {
      // Test substring that doesn't contain the last character.
      return isPalindrome(start, end - 1);
   }
   else
   {
      // Test substring that doesn't contain the first character.
      return isPalindrome(start + 1, end);
   }
  }
}

You should still supply a method to solve the whole problem—the user of your method shouldn't have to know about the trick with the substring positions. Simply call the helper method with positions that test the entire string:

public boolean isPalindrome()
{
   return isPalindrome(0, text.length() - 1);
}

Note that this call is not a recursive method. The isPalindrome() method calls the helper method isPalindrome(int, int). In this example, we use overloading to define two methods with the same name. The isPalindrome method without parameters is the method that we expect the public to use. The second method, with two int parameters, is the recursive helper method. If you prefer, you can avoid overloaded methods by choosing a different name for the helper method, such as substringIsPalindrome.

Use the technique of recursive helper methods whenever it is easier to solve a recursive problem that is slightly different from the original problem.

Demo4: Fibonacci Sequence

Consider the Fibonacci sequence introduced in Exercise P6.4: a sequence of numbers defined by the equation f_1=1 f_2=1 f_n=f_{n-2}+f_{n-1}

That is, each value of the sequence is the sum of the two preceding values. The first ten terms of the sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 It is easy to extend this sequence indefinitely. Just keep appending the sum of the last two values of the sequence. For example, the next entry is 34 + 55 = 89.

We would like to write a function that computes f_n for any value of n. Let us translate the definition directly into a recursive method:

RecursiveFib.java

 import java.util.Scanner;
 /**
    This program computes Fibonacci numbers using a recursive
    method.
 */
 public class RecursiveFib
 {
    public static void main(String[] args)
    {
       Scanner in = new Scanner(System.in);
       System.out.print(“Enter n: ”);
       int n = in.nextInt();

       for (int i = 1; i <= n; i++)
       {
          long f = fib(i);
          System.out.println(“fib(“ + i + ”) = ” + f);
       }
    }

    /**
       Computes a Fibonacci number.
       @param n an integer
       @return the nth Fibonacci number
    */
    public static long fib(int n)
    {
       if (n <= 2) return 1;
       else return fib(n - 1) + fib(n - 2);
    }
 }

This shows the call tree for computing fib(6):

Now it is becoming apparent why the method takes so long. It is computing the same values over and over. For example, the computation of fib(6) calls fib(4) twice and fib(3) three times. That is very different from the computation we would do with pencil and paper. There we would just write down the values as they were computed and add up the last two to get the next one until we reached the desired entry; no sequence value would ever be computed twice. This is much more efficient:

LoopFib.java

 import java.util.Scanner;
 /**
    This program computes Fibonacci numbers using an iterative method.
 */
 public class LoopFib
 {
    public static void main(String[] args)
    {
       Scanner in = new Scanner(System.in);
       System.out.print(“Enter n: ”);
       int n = in.nextInt();

       for (int i = 1; i <= n; i++)
       {
          long f = fib(i);
          System.out.println(“fib(“ + i + ”) = ” + f);
       }
    }

    /**
       Computes a Fibonacci number.
       @param n an integer
       @return the nth Fibonacci number
    */
    public static long fib(int n)
    {
       if (n <= 2) return 1;
       long fold = 1;
       long fold2 = 1;
       long fnew = 1;
       for (int i = 3; i <= n; i++)
       {
          fnew = fold + fold2;
          fold2 = fold;
          fold = fnew;
       }
       return fnew;
    }
 }

Review Exercises

R13.8 Write a recursive definition of n! = 1 \times 2 \times … × n, similar to the recursive definition of the Fibonacci numbers

Programming Exercises

For 8 points do one of these four. For 9 points do two. For 10 do three. For 11 out of 10 do all four:

P13.1. Write a recursive method void reverse() that reverses a sentence. For example:

public class SentanceTesterCh13
{
    public static void main(String[] args)
    {
        Sentence greeting = new Sentence("Hello!");
        greeting.reverse();
        System.out.println(greeting.getText());
    }
}

prints the string “!olleH”. Implement a recursive solution by removing the first character, reversing a sentence consisting of the remaining text, and combining the two.

P13.4 Use recursion to implement a method boolean find(String t) that tests whether a string is contained in a sentence:

Sentence s = new Sentence("Mississippi!");
boolean b = s.find("sip"); // Returns true

Hint: If the text starts with the string you want to match, then you are done. If not, consider the sentence that you obtain by removing the first character.

P13.7. Using recursion, compute the sum of all values in an array.

public class DataSet
{
   public DataSet(int[] values, int first, int last) { . . . }
   public int getSum() { . . . }
   . . .
}

P13.16 The recursive computation of Fibonacci numbers can be speeded up significantly by keeping track of the values that have already been computed. Provide an implementation of the fib method that uses this strategy. Whenever you return a new value, also store it in an auxiliary array. However, before embarking on a computation, consult the array to find whether the result has already been computed. Compare the running time of your improved implementation with that of the original recursive implementation and the loop implementation.

Use the following class as your tester class:

public class FastFibComputerTester
{
   public static void main(String[] args)
   {
      FastFibComputer ffc = new FastFibComputer();
      System.out.println(ffc.fib(50));
      System.out.println("Expected: 12586269025");
      System.out.println(ffc.fib(90));
      System.out.println("Expected: 2880067194370816120");
   }
}