Print Fibonacci Series in Java Using Recursion and For Loop

Printing Fibonacci Series In Java or writing a program to generate Fibonacci number is one of the interesting coding problem, 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 Fibonacci series, next number is equal to sum of 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 e.g. linked list and binary tree, where part behaves like whole. For example, when you remove a node from linked list, its another list, similarly if you take a part of tree, is another tree, which means same algorithm can be applied to them. Any way, If you get this question on interview, you are more likely to come up with recursive version first, as it's natural. Interviewer will now ask you to generate Fibonacci series without recursion. Which means you have to come up with Iterative solution using loops. You can also clarify whether additional data structure is allowed or not, as many recursive solution can be converted into iterative one by using Stack data structure. In this case, probably you don't need it.

Fibonacci Series using Recursion

In a recursive algorithm there are two parts, one in which function calls itself and on other where it return something, this is called 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 case of Fibonacci series, the best case if 1st two numbers.  Here is the recursive solution of generating Fibonacci number, which can be used to print 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 return 1, otherwise it call itself to generate a new Fibonacci number which is sum of previous two.

Fibonacci Series using For Loop

Now, let's see how we can print 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 recursive version, but this time we have used for loop. Here is the geometric image you get, when you draw Fibonacci series.

Fibonacci Series in Java using for loop and Recursion

Here is the complete sample code of printing Fibonacci series in Java by using recursion or for loop. As an exercise, can you write some JUnit test case for this program and it's 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 number in a cache in order to avoid calculating them again. This saves lot of processing time in cost of small memory, and particularly useful while calculating large Fibonacci number. I would suggest to try yourself first to come up a Fibonacci Series with memoization, but you can always refer to my solution.



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

1. How to check if two String are Anagram of each other? (Solution)


2. Recursive algorithm to calculate Sum of Digits of a number in Java? (Solution)


3. How to prevent Deadlock in Java? (Click here for solution)


4. Swap Two Numbers without using Temp Variable in Java? (Trick)


5. How to calculate factorial using recursion in Java? (Click here for solution)


6. Java program to check if a number is Armstrong number or not? (Solution)


7. Java program to remove duplicates from ArrayList? (Solution)


8. Program to find occurrences of  a character in String? (Solution)


9. How to find middle element of LinkedList in one pass without recursion? (See here for Solution)


10. Algorithm to check if a number is Prime or not? (Solution)


11. Give Algorithm to find if LinkedList contains Cycle? (Solution)


12. How to solve Producer Consumer Problem in Java. (Solution)


13. Give Algorithm to find if Array contains duplicates? (Solution)


14. Program to get first non repeated characters from String in Java? (See here for solution)


15. Algorithm to check if number is Power of Two? (Answer)


16. Algorithm to remove duplicates from array without using Collection API? (Solution)


17. Program to String in Java using recursion? (Solution)


18. Algorithm to check if a number is Palindrome? (Solution)


19. How to check if a number is binary in Java? (Solution)

Source:http://javarevisited.blogspot.com/2015/01/print-fibonacci-series-in-java-using.html