Fibonacci Series in Java using Recursion and Iteration - Example Tutorial

Printing Fibonacci Series In Java or writing a program to generate Fibonacci number is one of the interesting coding problems, used to teach college kids recursion, an important concept where function calls itself. It is also used a lot as coding problems while interviewing graduate programmers, as it presents lots of interesting follow-up questions as well. In the Fibonacci series, the next number is equal to the sum of the previous two numbers. First two numbers of series are always 1 and 1, third number becomes 1 + 1 = 2, subsequently fourth number becomes 2 + 1 = 3. So a Fibonacci series looks like 1, 1, 2, 3, 5, 8, 11, 19, and so on, as shown in the image as well.

This problem is quite easy to solve by using recursion and a greater example that how recursion can simply solution in some cases like linked list and binary tree, where part behaves like the whole. For example, when you remove a node from the linked list, it's another list, similarly, if you take a part of the tree, is another tree, which means the same algorithm can be applied to them.

Anyway, If you get this question on an interview, you are more likely to come up with a recursive version first, as it's natural. The interviewer will now ask you to generate the Fibonacci series without recursion. This means you have to come up with an Iterative solution using loops.

You can also clarify whether the additional data structure is allowed or not, as many recursive solutions can be converted into iterative ones by using the Stack data structure. In this case, probably you don't need it.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

Fibonacci Series in Java using Recursion

In a recursive algorithm, there are two parts, one in which the function calls itself and on the other where it returns something, this is called the base case, without this, your program will never terminate and die with StackOverflow error. When you solve a problem with recursion, you must first think about the base case.

In the case of the Fibonacci series, the best case is 1st the two numbers.  Here is the recursive solution of generating Nth Fibonacci number, which can be used to print the Fibonacci series.

public static int getFibonacci(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return getFibonacci(n - 1) + getFibonacci(n - 2);
}

You can see that if n = 1 or n = 2 then our function returns 1, otherwise it call itself to generate a new Fibonacci number which is the sum of the previous two. This is also one of the simplest Dynamic Programming problems for practice. 

Fibonacci Series in Java using Iteration and For Loop

Now, let's see how we can print the Fibonacci series without using recursion.

public static void fibonacci(int number) {
        int fibo1 = 1;
        int fibo2 = 1;

        System.out.printf("%nFibonacci series of %d numbers are : ", number);
        System.out.printf("%s ", fibo1);
        System.out.printf("%s ", fibo2);

        for (int i = 2; i < number; i++) {
            int fibonacci = fibo1 + fibo2;
            System.out.printf("%s ", fibonacci);
            fibo2 = fibo1;
            fibo1 = fibonacci;
        }
}

You can see that the logic is not very different than what we have used in the recursive version, but this time we have used it for loop. Here is the geometric image you get, when you draw the Fibonacci series.

Fibonacci Series in Java using for loop and Recursion

Here is the complete sample code of printing the Fibonacci series in Java by using recursion or for a loop. As an exercise, can you write some JUnit test cases for this program and its methods?

import java.util.Arrays;
import java.util.Scanner;

/**
 * Java program to find Fibonacci series of a given number and print them in
 * console. For example, if input is 9 then your program should print 1 1 2 3 5
 * 8 13 21 34 55 89
 *
 * @author WINDOWS 8
 *
 */
public class HelloAndroid {

    public static void main(String args[]) {
        fibonacci(8);
        fibonacci(9);
        fibonacci(10);

        fibonacciSeries(11);
        fibonacciSeries(12);

    }

    /*
     * Printing Fibonacci series of a given number using for loop
     */
    public static void fibonacci(int number) {
        int fibo1 = 1;
        int fibo2 = 1;

        System.out.printf("%nFibonacci series of %d numbers are : ", number);
        System.out.printf("%s ", fibo1);
        System.out.printf("%s ", fibo2);

        for (int i = 2; i < number; i++) {
            int fibonacci = fibo1 + fibo2;
            System.out.printf("%s ", fibonacci);
            fibo2 = fibo1;
            fibo1 = fibonacci;
        }
    }

    public static void fibonacciSeries(int number) {
        System.out.printf("\nFibonacci series in Java of number %s 
                                 using recursion %n", number);
        for (int i = 1; i <= number; i++) {
            System.out.printf("%s ", getFibonacci(i));
        }

    }

    /*
     * Fibonacci series in Java of a given number Recursion.
     */
    public static int getFibonacci(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return getFibonacci(n - 1) + getFibonacci(n - 2);
    }

}


Output
Fibonacci series of 8 numbers are : 1 1 2 3 5 8 13 21
Fibonacci series of 9 numbers are : 1 1 2 3 5 8 13 21 34
Fibonacci series of 10 numbers are : 1 1 2 3 5 8 13 21 34 55
Fibonacci series in Java of number 11 using recursion
1 1 2 3 5 8 13 21 34 55 89
Fibonacci series in Java of number 12 using recursion
1 1 2 3 5 8 13 21 34 55 89 144

That's all about how to print Fibonacci Series in Java with and without using recursion. You can further improve this solution by using a technique called memoization, which stores already calculated numbers in a cache in order to avoid calculating them again. 

This saves a lot of processing time in the cost of small memory and particularly useful while calculating the large Fibonacci numbers. I would suggest trying yourself first to come up with a Fibonacci Series with memorization, but you can always refer to my solution.

Other Java Coding Questions for Practice

If you like this tutorial and looking for some more challenging algorithm questions then check out my list of algorithm-based coding questions :

• How to check if two String are Anagram of each other? (Solution)
• Recursive algorithm to calculate Sum of Digits of a number in Java? (Solution)
• How to prevent Deadlock in Java? (Click here for solution)
• Swap Two Numbers without using Temp Variable in Java? (Trick)
• How to find the middle element of LinkedList in one pass without recursion? ( here)
• Algorithm to check if a number is Prime or not? (Solution)
• Give Algorithm to find if LinkedList contains Cycle? (Solution)
• How to solve Producer-Consumer Problem in Java. (Solution)
• Give Algorithm to find if Array contains duplicates? (Solution)
• Program to get first non-repeated characters from String in Java? (See here)
• Algorithm to check if a number is Power of Two? (Answer)
• How to calculate factorial using recursion in Java? (Click here for solution)
• Java program to check if a number is Armstrong's number or not? (Solution)
• Java program to remove duplicates from ArrayList? (Solution)
• Program to find occurrences of a character in String? (Solution)
• Algorithm to remove duplicates from an array without using Collection API? (Solution)
• Program to String in Java using recursion? (Solution)
• Algorithm to check if a number is a Palindrome? (Solution)
• How to check if a number is binary in Java? (Solution)

Thanks for reading this article so far. If you like this Fibonacci Series in Java then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you are looking for best Free Data Structure and Algorithms courses to improve your understanding of Data Structure and Algorithms in Java, then you should also check out the Data Structures in Java for Beginners course on Udemy.

And lastly one question for you, which one is your favorite Java coding exercise? Factorial, prime number, palindrome, Armstrong number or this one? Do let me know in comments