Fibonacci Sequence

• Fibonacci sequence is a sequence of numbers defined by
  f₁ = 1
  f₂ = 1
  f_n = f_n-1 + f_n-2
• First ten terms:
  1, 1, 2, 3, 5, 8, 13, 21, 34, 55

The Efficiency of Recursion

• Recursive implementation of fib is straightforward
• Watch the output closely as you run the test program
• First few calls to fib are quite fast
• For larger values, the program pauses an amazingly long time between outputs
• To find out the problem, insert trace messages (you will do this in the lab)

Call Tree for Computing fib(6)

The Efficiency of Recursion

• Method takes so long because it computes the same values over and over
• The computation of fib(6) calls fib(3) three times
• Imitate the pencil-and-paper process to avoid computing the values more than once

• f1 = 1;
  f2 = 1;
  fnew = f1 +f2;
  f2 = f1;
  f1 = fnew; 
   ...

The Efficiency of Recursion

• Occasionally, a recursive solution runs much slower than its iterative counterpart
• In most cases, the recursive solution is only slightly slower
• The iterative isPalindrome performs only slightly better than recursive solution
  • Each recursive method call takes a certain amount of processor time
• Smart compilers can avoid recursive method calls if they follow simple patterns
• Most Java compilers don't do that
• In many cases, a recursive solution is easier to understand and implement correctly than an iterative solution

Iterative isPalindrome Method

public boolean isPalindrome() 
{ 
   int start = 0; 
   int end = text.length() - 1; 
   while (start < end) 
   { 
      char first = Character.toLowerCase(text.charAt(start)); 
      char last = Character.toLowerCase(text.charAt(end); 
      if (Character.isLetter(first) && Character.isLetter(last)) 
      { 
         // Both are letters. 
         if (first == last) 
         { 
            start++; 
            end--; 
         } 
         else 
         { 
            return false; 
         } 
      } 
      if (!Character.isLetter(last)) { end--; } 
      if (!Character.isLetter(first)) { start++; } 
   } 
   return true; 
}

Lecture 8 Clicker Question 1

Consider the triangle number computation in the Triangle.getArea method.

• The recursive method is faster than a loop that computes 1 + 2 + 3 + . . . + width
• A loop is a little bit faster than the recursive method
• A loop is a lot faster than the recursive method
• Who cares? It is much faster to compute width * (width + 1) / 2.

Permutations

• Design a class that will list all permutations of a string
• A permutation is a rearrangement of the letters
• The string "eat" has six permutations:

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

To Generate All Permutations

You will define a class with a recursive method. Here is the start of the class

public class PermutationGenerator
{
   private String word;

   /**
      Constructs a permutation generator.
      @param aWord the word to permute
   */
   public PermutationGenerator(String aWord)
   {
      word = aWord;
   }
   

For the recursive method

You will need an array list to hold all the permutations

   public ArrayList getPermutations()
   {
      ArrayList permutations = new ArrayList();
      

Base case

      // The empty string has a single permutation: itself
      if (word.length() == 0) 
      { 
         permutations.add(word); 
         return permutations; 
      }

To Generate All Permutations

• Generate all permutations that start with 'e' , then 'a', then 't'
• To generate permutations starting with 'e', we need to find all permutations of "at"
• This is the same problem with simpler inputs
• Use recursion

To Generate All Permutations

• getPermutations method: loop through all positions in the word to be permuted
• For each position, compute the shorter word obtained by removing i-th letter:

  String shorterWord = word.substring(0, i) + word.substring(i + 1);

• Construct a new permutation generator to get permutations of the shorter word:
• Call the getPermutations method on the shorterPermutationGenerator
• Store the permutations of the shorter word in a new ArrayLilst

  PermutationGenerator shorterPermutationGenerator
        = new PermutationGenerator(shorterWord);
  ArrayList<String> shorterWordPermutations
        = shorterPermutationGenerator.getPermutations();

To Generate All Permutations

• Finally, add the removed letter to the front of each permutation of the shorter word (in the array list shorterWordPermutations):
• Add the that permutaions to the permutations array list

  for (String s : shorterWordPermutations)
  {
     permutations.add(word.charAt(i) + s);
  }

• Special case: Simplest possible string is the empty string; single permutation, itself

Lecture 8 Clicker Question 2

What are all permutations of the four-letter word beat?

1. beat, eatb, atbe, tbea
2. beat, beta, baet, bate, btea, btae
3. beat, beta, baet, bate, btea, btae, eatb, etab, aetb, ateb, teab, taeb
4. b followed by the six permutations of eat, e followed by the six permutations of bat, a followed by the six permutations of bet, and t followed by the six permutations of bea