Finally, 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.

Check out the call tree on page 103 and draw a similar call tree for this method, given 4 as a parameter. 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?