import java.util.Scanner;
//=================================================================================================
public class Fibonacci {
//-------------------------------------------------------------------------------------------------
    private static final Scanner keyboard = new Scanner(System.in);
//-------------------------------------------------------------------------------------------------
    public static void main(String[] args) {

        int number;
        long fibonacci;

        System.out.print("What is the number : ");
        number = keyboard.nextInt();

        fibonacci = computeFibonacciLinear(number);
        System.out.println("Linear Fibonacci(" + number + ")    = " + fibonacci);

        fibonacci = computeFibonacciRecursive(number);
        System.out.println("Recursive Fibonacci(" + number + ") = " + fibonacci);
    }
//-------------------------------------------------------------------------------------------------
    private static long computeFibonacciLinear(int number) {

        long previous,current,next;
        int index;

        previous = 1;
        current = 0;

        for (index = 0; index < number; index++) {
            next = current + previous;
            previous = current;
            current = next;
        }

        return(current);
    }
//-------------------------------------------------------------------------------------------------
    private static long computeFibonacciRecursive(int number) {

        if (number <= 1) {
            return(number);
        } else {
            return(computeFibonacciRecursive(number-1) + computeFibonacciRecursive(number - 2));
        }
    }
//-------------------------------------------------------------------------------------------------
}
//=================================================================================================