Thursday, July 12, 2012
Java program - Fibonacci series with recursion example
Write a Java program to print Fibonacci series up to a given number or create simple Java program to calculate Fibonacci number is common Java questions on fresher interview and homework. Fibonacci series is also a popular topic on various programming exercises in school and colleges. Fibonacci series is series of natural number where next number is equivalent to sum of previous two number e.g. fn = fn-1 + fn-2. First two numbers of Fibonacci series is always 1, 1. In this Java program example for Fibonacci series we create function to calculate Fibonacci number and then print those numbers on Java console. Another twist in this questions is that some time interviewer ask to write Java program for Fibonacci numbers using recursion, so its better you prepare for both iterative and recursive version of Fibonacci number. One more coding question which is quite popular is printing prime numbers in Java which I have discussed earlier. In this tutorial we will see example of both recursive and iterative algorithm for Fibonacci numbers:
Code Example to calculate and print Fibonacci numbers in Java
Here is complete code example of printing Fibonacci Series in Java. Fibonacci series is printed using both Iterative method and recursive method implemented using Java programming language.
After asking to write simple Java program to print Fibonacci series and later asking for Fibonacci series using recursion, another important question interviewer ask is how do you improve your Fibonacci function both iterative and recursive one? A technique called memorization can be used to drastically improve performance of method which calculates Fibonacci number. if you look at the method it repetitive creates same Fibonacci number e.g. In order to calculate 10th Fibonacci number function first create first 9 Fibonacci number, this could be very time consuming if you just increase the upper limit from 10 to 10K. In memorization programming technique result of earlier calculation is cached and reused. So you don't need to create same Fibonacci number if you already have calculated it. You can write code for Fibonacci series with memorization by just using a HashMap and checking if Fibonacci number for a corresponding number is already exits or not and calculate only if it doesn't exist.
Here is the code example of printing Fibonacci number with memorization technique :
Interesting point is that improved method only shows better performance for large numbers like 100M otherwise iterative version of Fibonacci method is faster. That could be explained by extra work done by improved method in terms of storing value in cache and getting it from there or am I missing something?
That's all on writing Java program to calculate and print Fibonacci number. Fibonacci number is good question for programming exercise but when asked as question in Java interview you just need to be more detailed and precise about what you are doing.