/**
 * This class should calculate Fibonacci numbers in linear time
 * using recursion.
 */
public class LinearRecursive implements Fibonacci {

  @Override
  public long fib(int n) {


    return fibzz(n, 1, 0);
    return -1; // Your code here.
  }


  int fibzz(int term, int val, int prev)
  {
    if(term == 0) return prev;
    return fib(term - 1, val+prev, val);
  }

}