How to Print Fibonacci Series in Java without Recursion - Coding Problem for Beginners

Fibonacci series is a great example of Dynamic Programming, 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 Fibonacci numbers or print the Fibonacci series of certain numbers, it's quite natural for programmers to resort to recursion. The interviewer often challenged this practice by asking candidates to implement the 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 have their iterative counterpart which uses loops instead of recursion or calling itself. We will take advantage of that concept to devise a solution to this problem.

Iteration also has one more advantage over recursion, For example, iterative algorithms are often bounded while the 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 the best of both worlds, your code is simpler and robust also as your solution will run without recursion in production.

It's also important for every programmer to know about basic data structures like an array, linked list, binary tree, hash table, and others. It helps you to write better code and also crack interviews, if you want to brush up your algorithms skills then I recommend you to join a Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

If you are looking at coding problems for interviews, then I also suggest you take a look at Cracking the Coding Interview book, 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.

Java Program to Print Fibonacci Series without Recursion

Here is our sample code example of the 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 like 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 the 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 the Fibonacci series in Java using recursion.

By the way, we are not using memorization yet, which is the technique to save the result of the earlier calculation and because of that our program will fail if you try to calculate the Fibonacci series for large numbers.

I will explain the concept of memorization into a separate article but if you are eager to learn more about memorization and dynamic programming then you can also check out Master the Art of Dynamic Programming course on  Udemy. This is a great course to build and level up your Dynamic programming skills

Java Program to Print Fibonacci Series without Recursion

For testing purposes, I have printed the Fibonacci series of 10 numbers using this program as shown in the output section but you can print Nth Fibonacci number from this program, you just need to call the Fibonacci() function with that number. 

You can also modify the program to take input from user to calculate the Fibonacci number at that place. 

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 the 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 a 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 the 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 are preparing coding questions for programming interviews like Java or C++ developer position, I suggest you check out the following courses, they will help you to prepare better :


Other Coding Interview Questions and Articles you may like
If you like this coding exercise and hunger to solve more problem to boost your Java coding skill, you may like to solve the following ones as well :

• How to implement the Quicksort algorithm in Java? [solution]
• 7 Best courses to learn Data Structure and Algorithms (courses)
• Write a program to find the top two numbers from an integer array? [solution]
• 10+ Algorithms and Programming Courses to Crack Interviews (courses)
• How to check if an array contains a number in Java? [solution]
• 10 Free Data Structure and Algorithms Courses for beginners (free courses)
• How to find the highest and lowest element in the unsorted array? [solution]
• 10 Books to learn Data Structure and Algorithms (books)
• Write a program to find the missing number in an integer array of 1 to 100? [solution]
• Top 10 Courses to learn Data Structure in Java (courses)
• 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 the 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]

Thanks for reading this article so far. If you like these dynamic programming coding problems 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 preparing for Programming Job Interview and you need more such dynamic programming questions, you can check the Master the Art of Dynamic Programming course on  Udemy. This is a great course to build and level up your Dynamic programming skills to become a better programmer.

Lastly one question for you,  what is the time and space complexity of this solution? how can you improve the performance of this program?