Java Program for Fibonacci Series [Loop, Recursion]

Problem: Write a java program to print the Fibonacci series up to n terms using loop or recursion.

Fibonacci series is the series that start from 0 as the first element and 1 as the second element and the rest of the nth term is equal to (n-1)^th + (n-2)^th terms.

Example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

Method 1: Using Loop

1. Input the value of n which denotes the number of terms in the Fibonacci series.
2. Assign the first element as a=0 and second element as b=1 and the third element as c=0.
3. Output the first two elements and loop to generate the next elements of the series.
4. Update the variable as follows c=a+b, a=b and b=c and output the value of c.
5. Repeat step 4 until all the terms are generated.

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
 
    int n,a=0, b=1, c=0;
 
    System.out.println("Enter the value of n");
    n = in.nextInt();
 
    //Output the first and second element
    System.out.print(a+" "+b+" ");
 
    for(int i=3; i<=n; i++){
      //Always update c first, second a and last b
      c = a+b;
      a = b;
      b = c;
      System.out.print(c+" ");
    }
  }
}

Output:

Enter the value of n
12
0 1 1 2 3 5 8 13 21 34 55 89

Method 2: Using Recursion

In this method, we compute each term of the series using a recursive function.

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    
    System.out.println("Enter the value of n");
    int n = in.nextInt();
 
    for(int i=1; i<=n; i++){
      //call recursive function for the ith term
      System.out.print(fibonacci(i)+" ");
    }
  }
 
  //recursive function that returns the nth term
  private static int fibonacci(int n){
    if(n==1){
      return 0;
    }
    else if(n == 2){
      return 1;
    } else {
      return fibonacci(n-2)+fibonacci(n-1);
    }
 
  }
}

Output:

Enter the value of n
10
0 1 1 2 3 5 8 13 21 34

If we observe the recursive function used in this method, we will find that for each term we have been recalculating the series from the beginning.

Because if the recalculation overhead, the time complexity of the program increases to O(n²).

We can make this recursive algorithm more efficient by using dynamic programming.

If you have any suggestions or doubts then please comment below.