Tuesday, August 11, 2020

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 another advantage over recursion e.g. 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 you can also 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.

If you are looking at coding problems for interviews, then I also 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.





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

Fibonacci Series in Java without Recursion



Java Program to Print Fibonacci Series without Recursion

For testing purposes, we have printed the 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 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 :

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Cracking the Coding Interview: 189 Problems and Solutions
Grokking the Coding Interview: Patterns for Coding Questions


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.

7 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.

Unknown 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?

Unknown said...

Thanks :)

suman said...

for(int i=0; i <= number; i++)

what is that syntax "i <= number"
it shows error
do compile your code before posting

Post a Comment