/****************************************************
 * A very simple test program to explore efficient  *
 * iterative and inefficient recursive computations *
 * of Fibonacci numbers ((c)G.Gimel'farb 2002)      *
 ****************************************************
 * Because of using long integers, the computation  *
 * up to about n = 92 is possible in the iterative  *
 * scheme before the number exceeds the maximum     *
 * long value of 9,223,372,036,854,775,807 (this    *
 * test program does not check such possibility)    *
 *                                                  *
 * If you use only iterativeFibonacci(), you may    *
 * try all the values of n up to 92 (of course, you *
 * may try even larger values, but the result will  *
 * be wrong due to undetected integer overflows...  *
 *                                                  *
 * But when using recursiveFibonacci() you are able *
 * to check only small values up to n = 40 (surely  *
 * if you have free time, try to wait until you can *
 * compute the desired number for n >= 40...50)     *
 ****************************************************
 * Question 1: what can you say about the numbers of*
 *       the individual recursive calls?            *
 * Question 2: explain yourself why the recursive   *
 *       program increases so fast the computation  *
 *       time? Can you find a formula for the time  *
 *       dependency from n? And for the stack size? *
 * Question 3: compare your theoretical estimates to*
 *       actual computing times for n=20 and n=30   *
 ****************************************************
 * Comment: the additional array call[] is used to  *
 *    only collect the numbers of recursive calls   *
 *    and the recursiveFibonacci() itself must be,  *
 *    of course, without the line call[n-1]++;      *
 ****************************************************
 */


import java.io.*;

public class TestFibonacciNum {
  
  static long[] call; // to collect information about 
                      // the number of recursive calls

  public static long iterativeFibonacci( int n ){ 
    if ( n <= 2 ) return 1;
    else {
      long fibM2 = 1;  // fibonacci(k-2)
      long fibM1 = 1;  // fibonacci(k-1)
      long fib   = 2;  // fibonacci(k)
      int  k     = 3;
      while ( k <= n ) {
        fib   = fibM1 + fibM2; 
        fibM2 = fibM1;
        fibM1 = fib;
        k++;
      }
      return fib;
    }
  } 

  public static long recursiveFibonacci( int n ) {
    call[ n - 1 ]++; // this is a counter collecting
	                 // the number of recursive calls
    if ( n <= 2 ) return 1;
    else return recursiveFibonacci( n - 1 ) +
                recursiveFibonacci( n - 2 );   
  }

  public static void main( String[] args ){
    while ( true ) {
      System.out.println("To end session - enter 0 ");
      System.out.print("Enter number: ");
      BufferedReader getData = new BufferedReader (
                                 new InputStreamReader( System.in ) );
      try{
        // input number n to compute fibonacci(n)
        String stringN = getData.readLine();
        int intN = ( Integer.valueOf( stringN ) ).intValue();
        if ( intN <= 0 ) break;
        // iterative computation
        long startTime   = System.currentTimeMillis();
        long fibonacciN  = iterativeFibonacci( intN );
        long runTime     = System.currentTimeMillis() - startTime;
        System.out.println(
          "iterativeFibonacci(" + intN + ") = " +
           fibonacciN + "; running time (ms) = " + runTime );
           // end of the iterative block

           // recursive computation (exclude this block to test
           //                    only the iterative computation)
        call = new long[ intN ];
        startTime   = System.currentTimeMillis();
        fibonacciN = recursiveFibonacci( intN );
        runTime     = System.currentTimeMillis() - startTime;
        System.out.println(
          "recursiveFibonacci(" + intN + ") = " +
          fibonacciN + "; running time (ms) = " + runTime );
        // analysis of the numbers of recursive calls
        long sum = 0;
        for( int k = 0; k < intN; k++ )
          sum += call[ k ];
        System.out.println( "Total number of recursive calls = " + sum );
        System.out.println( "Individual calls for n = 1 ... " + intN );
        for( int k = 0; k < intN; k++ ) {
          if ( k % 10 == 0 ) System.out.println(" ");
          System.out.print( call[ k ] + "; " );
        }
        System.out.println(" ");
        // end of the recursive block

      } catch ( Exception exc ) {
        System.out.println(
           exc.getClass() + " : " + exc.getMessage() );
      } finally {
          System.out.println("OK -- continue");
      }
    }
    System.out.println("OK -- bye");
    System.exit(0);
  }
}