Fibonacci series in Java without using Recursion

Fibonacci series is great example of Recursion and how use of recursion can result in 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, its 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 algorithm 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 other advantage in terms of 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 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 to 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 algorithm, data structure and others.

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) , 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 call 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 base case when you print Fibonacci series in Java using recursion.

For testing purpose, we have printed Fibonacci series of 10 numbers using this program as shown in 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 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 their 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 array contains a number in Java? [solution]
• How to find highest and lowest element in unsorted array? [solution]
• Write a program to find 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 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 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 array in place? [solution]
• How do you reverse 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 to check out following books, they will help you to prepare better :

• Cracking the Coding Interview: 150 Programming Questions and Solutions [check here]
• Programming Interviews Exposed: Secrets to Landing Your Next Job [check here]
• Coding Puzzles: Thinking in code By codingtmd [check here]