1. Write the following two recursive methods (both are part of the class Print).

/**
 * Prints n stars.
 *
 * @param n the number of stars to be printed.
 * @pre. n >= 0
 */
public static void stars(int n)

/**
 * Prints n stars followed by n plusses.
 *
 * @param n the number of stars and plusses to be printed.
 * @pre. n >= 0
 */
public static void starsAndPlusses(int n)

2. Prove that both for each int n with n >= 0, the invocations Print.stars(n)
   and Print.starsAndPlusses(n) terminate.

3. Consider the following recursive method.

/**
 * Prints plusses.
 *
 * @param d a double.
 * @pre. d >= 0
 */
public static void plusses(double d)
{
   if (d == 0)
   {
      // do nothing
   }
   else
   {
      System.out.print("+");
      Print.plusses(d / 2);
   }
}

For each double d, with d >= 0, does the invocation Print.plusses(d)
terminate?  Motivate your answer.

4. Write the following four recursive methods (both are part of the class Lists).

/**
 * Tests if the given element is part of the given list.
 *
 * @param element An element.
 * @pre. element != null
 * @param list A list.
 * @pre. list != null
 * @return true if the given list contains the given element,
 * false otherwise.
 */
public static <T> boolean contains(T element, List<T> list)

/**
 * Tests if the given list is constant, that is, all elements in
 * the list are equal.
 *
 * @param list A list.
 * @pre. list != null
 * @return true if the given list is constant, false otherwise.
 */
public static <T> boolean isConstant(List<T> list)

/**
 * Returns a minimal element of the given list.
 *
 * @param list A list.
 * @pre. list != null && list.size() > 0
 * @return a minimal element of the given list.
 */
public static int min(List<Integer> list)

/**
 * Checks if the list is of the form [1, 2, 4, 8, ...].
 *
 * @param list A list.
 * @pre. list != null && list.size() > 0 && elements of list are powers of 2
 * @return true if the list is of the form [1, 2, 4, 8, ...],
 * false otherwise.
 */
public static boolean isPowersOfTwo(List<Integer> list)

5. Write the following recursive method (part of the class Math).

/**
 * Returns the given base raised to the given exponent.
 *
 * @param base The base.
 * @param exponent The exponent.
 * @pre. exponent >= 0
 * @return base<sup>exponent</sup>
 */
public static int pow(int base, int exponent)

6. Give an upperbound (in terms of e) for the number of multiplications
   performed by the invocation Math.pow(b, e).

7. Express the upperbound using the big-Oh notation.

8. Prove that your big-Oh "choice" is correct.