Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

fibonacci
java
sequence
patterns

How to implement the Fibonacci sequence in Java

Educative Answers Team

In 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;   

        }

    }
}

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.

A fibonacci recursive tree for total = 5
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) + " ");}
  }
    
}

RELATED TAGS

fibonacci
java
sequence
patterns
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring