/*
  Fibonacci1 (first 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".

  The user is repeatedly asked for the parameter "n" until the user's input
  is zero or negative.  Large values of "n" are slow to calculate because
  the number of recursive function calls is exponential.  The largest 32-bit
  "int" value that can be calculated is f(46) = 1,836,311,903 and takes 150
  seconds of CPU time on a 500 MHz Pentium processor running Borland
  JBuilder 3.
*/

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

public class Fibonacci1
{
  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)
        System.out.println("f(" + n + ") = " + f(n));
    }
    while (n > 0);

  } // end of main()

/*
  f() method

  This method does the work of calculating the recursive function.  The
  parameter n and the result are both integers.  This method calls itself.
  Note that the parameter n in this function and the variable n in main()
  are *not* the same value!
*/
  static int f(int n)
  {
    int result;                   // the result of this function

    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