Something useful

Consider the following algorithm for calculating Fibonacci numbers:

  public static int fibonacci (int n) {
    if (n == 0 || n == 1) {
      return 1;
    } else {
      return fibonacci (n-1) + fibonacci (n-2);
    }
  }

1. In a sentence or two, sketch a proof that this program terminates for all values of n. If necessary, explain any preconditions that are required to guarantee termination.
2. Draw a call tree that shows the sequence of recursive calls that happens when fibonacci is invoked with parameter 4. How many times do the base cases get evaluated? As the parameter gets bigger, how does this number behave? Does this seem like an efficient way to evaluate Fibonacci numbers?
3. Design a better algorithm to do the same thing. How long does it take, as a function of the parameter? How much space does it require? Implement your algorithm. Was it easier or harder to write than the recursive version. If you had to prove its correctness, could you?