Fibonacci Series in Java Using Recursion

Fibonacci series in Java

Write a Java program to print the Fibonacci series up to a given number or create a simple Java program to calculate Fibonacci number is common Java questions on fresher interviews and homework. Fibonacci series is also a popular topic on various programming exercises in schools and colleges. Fibonacci series is a series of natural numbers where the next number is equivalent to the sum of the previous two numbers like fn = fn-1 + fn-2. The first two numbers of the Fibonacci series are always 1, 1. In this Java program example for the Fibonacci series, we create a function to calculate Fibonacci numbers and then print those numbers on the Java console.

Another twist in these questions is that sometimes the interviewer asks to write a Java program for Fibonacci numbers using recursion, so it’s better you prepare for both iterative and recursive versions of the Fibonacci number.

One more coding question which is quite popular is printing prime numbers in Java which I have discussed earlier. In this tutorial, we will see an example of both recursive and iterative algorithms for the Fibonacci series in Java.

For more coding questions you can always look into Cracking the Code Interviews, one of the finest collections of code-based questions from programming interviews. You will find data structure and algorithmic questions asked on companies like Amazon, Google, Microsoft, and Facebook in this book.

Printing Fibonacci numbers in Java: Sample Code Example

Here is a complete code example of the printing Fibonacci Series in Java. Fibonacci series is calculated using both the Iterative and recursive methods and written in Java programming language. We have two functions in this example, fibonacci(int number)  and  fibonacci2(int number). The first one prints the Fibonacci series using recursion and the second one uses for loop or iteration. 

You can test this code on your computer as well. Once you create your Java source file, just compile and run. It will ask you to enter the number till which you want to see the series. Once you enter then a number, it will print the Fibonacci series in the console.

Java Program to print Fibonacci Series

import java.util.Scanner;

/**
 * Java program to calculate and print Fibonacci number using both recursion
 * and Iteration.
 * Fibonacci number is sum of previous two Fibonacci numbers fn= fn-1+ fn-2
 * first 10 Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
 *
 * @author Javin
 */
public class FibonacciCalculator {

    public static void main(String args[]) {
    
       //input to print Fibonacci series upto how many numbers
        System.out.println("Enter number upto which Fibonacci
                      series to print: ");
        int number = new Scanner(System.in).nextInt();
      
        System.out.println("Fibonacci series upto " + number +" numbers : ");
        //printing Fibonacci series upto number
        for(int i=1; i<=number; i++){
            System.out.print(fibonacci2(i) +" ");
        }
  
    
    } 
  

    /*
     * Java program for Fibonacci number using recursion.
     * This program uses tail recursion to calculate Fibonacci number 
     * for a given number
     * @return Fibonacci number
     */
    public static int fibonacci(int number){
        if(number == 1 || number == 2){
            return 1;
        }
      
        return fibonacci(number-1) + fibonacci(number -2); //tail recursion
    }
  


    /*
     * Java program to calculate Fibonacci number using loop or Iteration.
     * @return Fibonacci number
     */
    public static int fibonacci2(int number){
        if(number == 1 || number == 2){
            return 1;
        }
        int fibo1=1, fibo2=1, fibonacci=1;
        for(int i= 3; i<= number; i++){
           
            //Fibonacci number is sum of previous two Fibonacci number
            fibonacci = fibo1 + fibo2;             
            fibo1 = fibo2;
            fibo2 = fibonacci;
          
        }
        return fibonacci; //Fibonacci number
      
    }   
  
}

Output:
Enter number upto which Fibonacci series to print:
12
Fibonacci series upto 12 numbers :
1 1 2 3 5 8 13 21 34 55 89 144

After asking to write a simple Java program to print the Fibonacci series and later asking for the Fibonacci series using recursion, another important question interviewer asks is how do you improve your Fibonacci function both iterative and recursive?

A technique called memoization can be used to drastically improve the performance of the method which calculates the Fibonacci number. if you look at the method it repetitively creates the same Fibonacci number.

In order to calculate the 10th Fibonacci number function first create the first 9 Fibonacci numbers, this could be very time-consuming if you just increase the upper limit from 10 to 10K.

In the memoization programming technique, the result of the earlier calculation is cached and reused. So you don’t need to create the same Fibonacci number if you already have calculated it. 

Fibonacci Number in Java with Memoization

Here is the code example of printing the Fibonacci number with the memoization technique. You can write code for the Fibonacci series with memoization by just using a HashMap and checking if the Fibonacci number for a corresponding number is already present or not and calculate only if it doesn’t exist.

   /*
     * Java Program to calculate Fibonacci numbers with memorization
     * This is quite fast as compared to previous Fibonacci function
     * especially for calculating factorial of large numbers.
     */
    public static int improvedFibo(int number){
        Integer fibonacci = cache.get(number);
        if(fibonacci != null){
            return fibonacci; //fibonacci number from cache
        }
        //fibonacci number not in cache, calculating it
        fibonacci = fibonacci2(number);
        
        //putting fibonacci number in cache for future request 
        cache.put(number, fibonacci); 
        return fibonacci;
    }

Here is a diagram of how Fibonacci series will look like when you draw :

Performance Comparison Fibonacci function with and without memoization

//comparison of performance of Fibonacci number with memoization

int number = 100000000;

long startTime = System.nanoTime();

int result = fibonacci2(number); //fibonacci number with memoization

long elapsedTime = System.nanoTime() – startTime;

System.out.println(“Time taken to calculate Fibonacci number upto 100M 

without memorization:” + elapsedTime);

startTime = System.nanoTime();

result = improvedFibo(number); //Fibonacci number with memoization

elapsedTime = System.nanoTime() – startTime;

System.out.println(“Time taken to calculate Fibonacci number upto 100M 

with memorization:” + elapsedTime);

Output:

Time taken to calculate Fibonacci number upto 100M without memoization:149479613

Time taken to calculate Fibonacci number upto 100M with memoization:118972384

An interesting point is that the improved method only shows better performance for large numbers like 100M otherwise iterative version of the Fibonacci method is faster. That could be explained by extra work done by the improved method in terms of storing value in cache and getting it from there or am I missing something?

For more such questions for interviews, you can refer to courses like Grokking the Coding Interview: Patterns for Coding Questions by Educative. It’s a great course to learn patterns that can be used to solve multiple coding problems.

That’s all about writing Java programs to calculate and print the Fibonacci series. The Fibonacci number is a good question for programming exercise but when asked a question in a Java interview you just need to be more detailed and precise about what you are doing.