/*
  Recursion
*/

public class recursion
{

    static int fib(int n)// worst example of recursion EVER
    {
	if (n<3) return 1; else return fib(n-1) + fib(n-2);
    }
    // fib(100) will take > 2000 years

    static int factorial(int n)// second worst example of recursion
    {
	if (n<2) return 1; else return n*factorial(n-1);
    }
    // factorial(100000) will overflow runtime stack

    // no problem since depth of recursion and time complexity both O(log n),
    // but recursive version still not better than non-recursive loop:
    static int f(int n)
    {
	if (n<=1) return 0;
	else return 1 + f(n/2);
	/* without recursion:
	   int ax;
	   for(ax=0;n>1;n=n/2) ax++;
	   return ax;
	 */
    }

    // non-recursive, O(n) Fibonacci, easiest to implement
    static long nthfib(int n)
    {
	int a =1, b=1;
	while (n-->2) 
	    { b = a+b;  a = b-a; } // a becomes b, b becomes a+b
	return b;
    }

    // find (non-negative) integer power of x  (x**n): this recursive program
    // also has O(log n) recursive call depth
    static long power(int x, int n)
    {   // if (n<0) return 1/power(x,-n);
	if (n<1) return 1;
	if (n==1) return x;
	long half = power(x,n/2);
	long full = half * half;
	if (n%2==1) full = full * x;
	return full;
    }
    static long ipower(int x, int n)  // can still do without recursion:
    {
	long ax = 1;
        long factor = x;
	while (n>0)
	    {
		int bit = n%2;
		if (bit==1) ax *= factor;
		factor = factor*factor;
		n = n/2;
	    }
	return ax;
    }


    // Fibonacci, loop version in O(n) steps
    static long fib2(int n)
    {
	int a = 1, b = 1;
	while (n-- > 2) { b= a+b;  a=b-a; } // a,b = b,a+b
	return b;
    }  //O(n) steps

    // closed form Fibonacci: has only 53 binary bits of precision:
    static long fib3(int n)
    {
	double s5 = Math.sqrt(5); // square root of 5
	double fibn = (Math.pow(1+s5,n) - Math.pow(1-s5,n))/(Math.pow(2,n)*s5);
	return (long)(fibn+0.5);  // round off
    }

    // Best Fibonacci using using O(log n) recursive steps, using 
    // binary factorization of matrix exponent.
    // The following matrix raised to the nth power gives
    //  (1 1)**n  = fib(n+1) fib(n)
    //  (1 0)       fib(n)   fib(n-1)

    // efficient Fibonacci using recursion: (log(n) steps)
    static long[] IDMatrix = {1,0,0,1};  // identity matrix: M*ID = M
    static long[] FMatrix = {1,1,1,0}; // Fibonacci matrix
    static long[] mmult(long[] A, long[] B) // multiply 2 2x2 matrices:
    {
	long[] C = new long[4]; // matrix to be returned
	C[0] = A[0]*B[0] + A[1]*B[2];
	C[1] = A[0]*B[1] + A[1]*B[3];
	C[2] = A[2]*B[0] + A[3]*B[2];
	C[3] = A[2]*B[1] + A[3]*B[3];
	return C;
    }
    // multiply FMatrix to the nth power  ** THIS METHOD USES RECURSION
    static long[] powerFM(int n)
    {
	if (n<1) return IDMatrix;
	if (n==1) return FMatrix;
	long[] Half = powerFM(n/2);
	long[] Full = mmult(Half,Half);
	if (n%2==1) Full = mmult(Full,FMatrix);
	return Full;
    }
    // another, slightly more efficient version, log(n) recursion depth
    static long[] powerF(int n, long[] ax, long[] factor)
    {
	if (n==0) return ax;
	if (n%2==1) ax = mmult(ax,factor);
	return powerF(n/2,ax,mmult(factor,factor));
    }// call with initial ax= IDMatrix, factor = FMatrix


    // non-recursive version of above function, log(n) loop iterations
    static long[] powerFi(int n)
    {
	long[] ax = IDMatrix;
	long[] factor = FMatrix;
	while (n>0)
	    {
		if (n%2==1) ax = mmult(ax,factor);
		factor = mmult(factor,factor);
		n = n/2; // shift-right
	    }
	return ax;
    }

    static long Fibonacci(int n)
    {
	if (n<3) return 1;
	else return powerFM(n-1)[0];
    }

    public static void main(String[] av)
    {
	int n = Integer.parseInt(av[0]);
	System.out.println(Fibonacci(n));
	//System.out.println(fib(n)); // uncomment at your own risk
    }
}//recursion examples


/*
These function show that some recursive programs behave better than others.
More importantly, they show that the time complexity of algorithms is not
necessarily tied to the use of recursion.  Unfortunately, none of them shows
why recursion would be a better choice compared to no recursion.  For that
we need to consider more difficult problems...
*/