Fibonacci series in Java without using Recursion

Fibonacci series is a great example of Recursion and how the use of recursion can result in a clear and concise solution. That's why whenever asked about writing a Java program to get a Fibonacci numbers or print the Fibonacci series of certain numbers, it's quite natural for programmers to resort to recursion. Interviewer often challenged this practice by asking candidates to implement Fibonacci series without using recursion. Yes, you read it right, you can't use recursion and this is what you will learn in this article. If you have attended your programming classes regularly then you may know that many recursive algorithms also has their iterative counterpart which uses loops instead of recursion or calling itself . We will take advantage of that concept to devise a solution of this problem.

Iteration also has another advantage over recursion e.g. iterative algorithms are often bounded while recursive algorithm keeps building their stack which could result in StackOverFlowError. That's why iterative algorithms or solutions are mostly preferred over their recursive counterpart in production, even though the code is not as succinct and expressive as recursive one.

Some languages like Scala solves this problem by doing tail recursion optimization, which means your recursive algorithm is converted into iterative one at compile time. This is like best of both world, your code is simpler and robust also as your solution will run without recursion in production.

BTW, if you are looking coding problems for interviews, then I suggest you take a look at Cracking the Coding Interview, one of the better books to prepare programming job interviews. It contains 150 programming questions and their solutions from the algorithm, data structure, and others.

How to print Fibonacci series in Java using recursion



Java Program to Print Fibonacci Series without Recursion

Here is our sample code example of printing Fibonacci series in Java without using recursion. Instead of recursion, I have used for loop to do the job. In this solution, I have two methods fibonacci(int number) and getFibonacci(int n) ,  the first method is used to print Fibonacci series up to certain numbers e.g. you can print Fibonacci series of first n numbers using this method.


This method internally calls getFibonacci(int n) to get the nth Fibonacci number. The logic of calculating nth Fibonacci number is implemented in this method and it does that without using recursion. It uses a simple for loop to iterate until the nth number and calculate Fibonacci number using following formula :

f(n) = f(n-1) + f(n-2);

Since we know that f(0) and f(1) is always 1 we can directly return them if asked to calculate 1st and 2nd Fibonacci number of series. If you remember those are served as the base case when you print Fibonacci series in Java using recursion.

Fibonacci Series in Java without Recursion

For testing purpose, we have printed Fibonacci series of 10 numbers using this program as shown in the output section.


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;


/**
 * Java Program to print Fibonacci series without using recursion.
 * input : 10
 * output : 0 1 1 2 3 5 8 13 21 34 55 
 *
 * @author WINDOWS 8
 */

public class FibonacciSeriesWithoutRecursion {

    public static void main(String args[]) {
     
        // printing first 10 numbers of Fibonacci series
        fibonacci(10);
     
    }
     
 
    public static void fibonacci(int number){
        for(int i=0; i <= number; i++){
            System.out.print(getFibonacci(i) + " ");
        }
    }
  
    /**
     * This function return nth Fibonacci number in Java
     * @param n
     * @return nth number in Fibonacci series
     */
    public static int getFibonacci(int n){
      
        if (n == 0) {
            return 0;
        }
        
        if (n == 1){
            return 1;
        }

        int first = 0;
        int second = 1;
        int nth = 1;

        for (int i = 2; i <= n; i++) {
            nth = first + second;
            first = second;
            second = nth;
        }
        return nth;
    }
  
}

Output : 0 1 1 2 3 5 8 13 21 34 55 

That's all about how to print Fibonacci series in Java without recursion. I love this problem and you have might have already seen some discussion around this in my earlier blog posts and will see more when I talk about how to generate Fibonacci number in Java 8 soon.

This is also my go-to example to explain recursion to beginners and how the use of recursion can result in more readable code. Though, always keep in mind that iterative algorithm is better than recursive one when it comes to production. They are more robust as there is no risk of StackOverFlowError.


If you like this coding exercise and hunger to solve more problem to boost your Java coding skill, you may like to solve following ones as well :
  • How to implement Quicksort algorithm in Java? [solution]
  • Write a program to find top two numbers from an integer array? [solution]
  • How to check if an array contains a number in Java? [solution]
  • How to find highest and lowest element in the unsorted array? [solution]
  • Write a program to find the missing number in integer array of 1 to 100? [solution]
  • How to check if a given String is Palindrome in Java? [solution]
  • How to remove duplicates from an array in Java? [solution]
  • Write a program to reverse words of String in Java? [solution]
  • How to find all pairs on integer array whose sum is equal to a given number? [solution]
  • How to check duplicate elements from Array in Java? [solution]
  • Write a program to check if two String are Anagram or not? [solution]
  • How do you remove duplicates from an array in place? [solution]
  • How do you reverse an array in place in Java? [solution]

If you are preparing coding questions for programming interviews e.g. Java or C++ developer position, I suggest you check out following books, they will help you to prepare better :
  • Programming Interviews Exposed: Secrets to Landing Your Next Job [check here]
  • Coding Puzzles: Thinking in code By codingtmd [check here]

5 comments :

Anonymous said...

The output is incorrect.
The Fibonacci series is:: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

n : 0 1 2 3 4 5 6 7 8 9 10 ...
f(n): 0 1 1 2 3 5 8 13 21 34 55 ...

allan said...

int second = 1 (not 2)
Otherwise good post as alwasys.

Javin Paul said...

Thanks @Anonymous and @allan, the logic and output was indeed incorrect, corrected it now. Looks like I had created my own Fibonacci series for this post :) Thank you guys for pointing it out.

dhinesh raja said...

hi
how to print odd fibonacci number betwwen 10 to 1000

Javin Paul said...

@dhinesh, how about calculating Fibonacci number till 1000, put them an array and then only print the odd ones?

Post a Comment