/*
  Fibonacci2 (second version)
  written by Keith Fenske
  Wednesday, 1 May 2002
  Copyright (c) 2002 by Keith Fenske.  All rights reserved.

  This Java program computes the Fibonacci sequence 1, 1, 2, 3, 5, 8, ...
  using the recursive function f(1) = f(2) = 1, f(n) = f(n-1) + f(n-2) as
  explained on page 95 of "Discrete Mathematical Structures".

  This second version is the same as the first version, except it counts the
  number of calls to the Fibonacci function.  Since the calls are counted in
  the f() method and the total is used in the main() method, the number of
  calls must be in a class variable.  Only class variables are shared by all
  methods in the same class.  f(46) = 1,836,311,903 makes 3,672,623,805
  calls to the Fibonacci function.
*/

import cs1.Keyboard;              // import Lewis/Loftus keyboard class
//                           http://duke.csc.villanova.edu/jss/keyboard.html

public class Fibonacci2
{
  static long calls;              // number of calls to f() method

  public static void main(String[] args)
  {
    int n;                        // function parameter from user

    System.out.println("\nThis Java program computes the Fibonacci sequence");
    System.out.println("1, 1, 2, 3, 5, 8, 13, 21, ... using the recursive");
    System.out.println("function f(1) = f(2) = 1, f(n) = f(n-1) + f(n-2).");

    do
    {
      System.out.print("\nWhat is the parameter n?  (Type 0 to quit.)  ");
      n = Keyboard.readInt();
      if (n > 0)
      {
        calls = 0;                // reset the number of calls to zero
        System.out.println("f(" + n + ") = " + f(n) + " with " + calls
          + " calls to the Fibonacci function");
      }
    }
    while (n > 0);

  } // end of main()

/*
  f() method

  This method does the work of calculating the recursive function.  The
  parameter n is a regular "int" number (32 bits).  The function result is
  a "long" integer (64 bits).  This method calls itself.  Note that the
  parameter n in this function and the variable n in main() are *not* the
  same number!
*/
  static long f(int n)
  {
    long result;                  // the result of this function

    calls ++;                     // increment number of calls to f()
    if (n < 1)
    {
      System.out.println("domain error in f(), n = " + n);
      result = -1;
    }
    else if (n <= 2)
      result = 1;
    else
      result = f(n-1) + f(n-2);   // call ourself!

    return result;
    
  } // end of f()

} // end of class