Due: Wednesday, April 23rd at the beginning of class (but not to hand in)

Read: Wu, Ch. 15

Solutions: here

Problem 1: Consider the following method

public static int bar(String s)
{
  if (s.length() < 2)
    return 0;
  else if (s.charAt(0) != s.charAt(1))
    return 1 + bar(s.substring(1));
  else
    return bar(s.substring(1));
}

• What does bar("a") return?
• What does bar("abc") return?
• What does bar("aaa") return?
• Describe what bar does. Your description should enable someone to easily determine what bar(s) returns without having to trace the code.

Problem 2: Write a recursive method that computes a_k, where a_k is defined as follows: a₀ = 2, a₁ = 1, and a_k = a_k-1 + 2 * a_k-2 for k > 1.

Problem 3: Consider the following recursive function.

public int w(int k)
{
  if (k == 0)
    return 2;
  else if (k <= 3)
    return 1;
  else if (w(k - 1) + w(k - 2) + w(k - 3) % 3 == 0)
    return 2;
  else
    return 1;
}