/*
* The Fibonacci sequence is 1, 1, 2, 3, ...
* 
* (Here is more on the subject:
* http://mathworld.wolfram.com/FibonacciNumber.html )
*
* In this program, the first element of the above sequence is fib(0)
* following the commonly accepted convention in computer science and 
* mathematical logic that the he smallest natural number is 0.
*
* Should one assert, like it is common in math, that the smallest 
* natural number is 1, instead, then the first element of the above
* sequence becomes fib(1) and the argument of fib needs to be 
* shifted by 1.
*/



package fibonacci;

/**
 *
 * @author suchenek
 */
public class Fibonacci_plain
{
    
	public static void main (String [] args)
 	{
            for (int n = 0; n < 20; n++)
            {
                cnt.clr();
  		int m = fib(n);
                int count = cnt.get();
 		System.out.print("F(" + n + ") = " +  m);
 		System.out.print("   2*F(" + n + ") - 1 = " +  (2*m-1));
                cnt.out("   cnt = ");
 		System.out.println("   T(" + n + ") = " +  T(n));
            }
	 }
 
 	public static int fib(int n)
	 {
                cnt.incr();
	 	if (n < 0) return 0;
                if (n <= 1) return 1;
 		return (fib(n-1) + fib(n-2)); 
 	}

 	public static int T(int n)
	 {
                cnt.incr();
	 	if (n < 0) return 0;
                if (n <= 1) return 1;
 		return (T(n-1) + T(n-2) + 1); 
 	}
}