In the [Fibonacci sequence](https://www.educative.io/answers/what-is-the-fibonacci-sequence), each number of the series is the sum of the previous two values. Given a starting number of 0 and 1, the sequence goes on to print; `0, 1, 1, 2, 3, 5 ...`. 

# Implementing the Fibonacci Sequence

In Java, we can implement the Fibonacci sequence using loops and recursion. We will be going through both implementations in detail. 

For both snippets, try changing the value of `total` to print out more numbers in the sequence. 

## 1. Using loops

To implement the Fibonacci sequence in Java using loops we can use either the `for` or the `while` loop. For each implementation, the time complexity is simply ***O(total)*** i.e. the number of times the loop is run. The code snippet below shows both ways to write the code

class for_Fibonacci {
    public static void main( String args[] ) {
        int number1 = 0;
        int number2 = 1;
        int sum;
        int total = 15;

        System.out.print(number1);

        for(int i=1;i<total;++i){
          
          sum = number1 + number2;
          System.out.print(", " + number2);
          number1 = number2;
          number2= sum;   

        }

    }
}

class while_Fibonacci {
    public static void main( String args[] ) {
        int number1 = 0;
        int number2 = 1;
        int sum;
        int total = 15;
        int i = 1;
        System.out.print(number1);
        
        while(i<total){
          
          sum = number1 + number2;
          System.out.print(", "+number2);
          number1 = number2;
          number2 = sum;
          i = i+1;   

        }

    }
}

While

## 2. Using recursion

Another method of implementing the Fibonacci sequence in Java is to use recursion. In this way, we first create a method that calls itself recursively to print the sequence, until a base case is reached. The time complexity of this code is ***O(2^total)***. The code snippet below shows how to do this. 

class recurse_Fibonacci {

    static int fib(int total){
      //Base Case
      if (total <= 1){
        return total;
      }

      return fib(total-1) + fib(total-2);
    }
    public static void main( String args[] ) {
        int total = 15;
         for (int i= 0; i < total; i++)
            {System.out.print(fib(i) + " ");}
  }
    
}

How to implement the Fibonacci sequence in Java

Using loops and recursion, Fibonacci sequence implementation in Java demonstrates time complexity variations (O(total) vs. O(2^total)).