Monday, January 19, 2015
Print Fibonacci Series in Java Using Recursion and For Loop
Printing Fibonacci Series In Java or writing a program to generate Fibonacci number is one of the interesting coding problem, used to teach college kids recursion, an important concept where function calls itself. It is also used a lot as coding problems while interviewing graduate programmers, as it presents lots of interesting follow-up questions as well. In Fibonacci series, next number is equal to sum of previous two numbers. First two numbers of series are always 1 and 1, third number becomes 1 + 1 = 2, subsequently fourth number becomes 2 + 1 = 3. So a Fibonacci series looks like 1, 1, 2, 3, 5, 8, 11, 19 and so on, as shown in the image as well. This problem is quite easy to solve by using recursion and a greater example that how recursion can simply solution in some cases e.g. linked list and binary tree, where part behaves like whole. For example, when you remove a node from linked list, its another list, similarly if you take a part of tree, is another tree, which means same algorithm can be applied to them. Any way, If you get this question on interview, you are more likely to come up with recursive version first, as it's natural. Interviewer will now ask you to generate Fibonacci series without recursion. Which means you have to come up with Iterative solution using loops. You can also clarify whether additional data structure is allowed or not, as many recursive solution can be converted into iterative one by using Stack data structure. In this case, probably you don't need it.
Fibonacci Series using Recursion
In a recursive algorithm there are two parts, one in which function calls itself and on other where it return something, this is called base case, without this your program will never terminate and die with stackoverflow error. When you solve a problem with recursion, you must first think about the base case. In case of Fibonacci series, the best case if 1st two numbers. Here is the recursive solution of generating Fibonacci number. which can be used to print Fibonacci series .
You can see that if n = 1 or n = 2 then our function
return 1, otherwise it call itself to generate a new Fibonacci number which is sum of previous two.
Fibonacci Series using For Loop
Now, let's see how we can print Fibonacci series without using recursion.
You can see that the logic is not very different than what we have used in recursive version, but this time we have used for loop. Here is the geometric image you get, when you draw Fibonacci series.
Fibonacci Series in Java using for loop and Recursion
Here is the complete sample code of printing Fibonacci series in Java by using recursion or for loop. As an exercise, can you write some JUnit test case for this program and it's methods.
If you like this tutorial and looking for some more challenging algorithm questions then checkout my list of algorithm based coding questions :
- How to check if two String are Anagram of each other? (Solution )
- Recursive algorithm to calculate Sum of Digits of a number in Java? (Solution )
- How to prevent Deadlock in Java? (Click here for solution)
- Swap Two Numbers without using Temp Variable in Java? (Trick )
- How to calculate factorial using recursion in Java? (Click here for solution)
- Java program to check if a number is Armstrong number or not? (Solution )
- Java program to remove duplicates from ArrayList? (Solution )
- Program to find occurrences of a character in String? (Solution )
- How to find middle element of LinkedList in one pass without recursion? (See here for Solution)
- Algorithm to check if a number is Prime or not? (Solution )
- Give Algorithm to find if LinkedList contains Cycle? (Solution )
- How to solve Producer Consumer Problem in Java. (Solution )
- Give Algorithm to find if Array contains duplicates? (Solution )
- Program to get first non repeated characters from String in Java? (See here for solution)
- Algorithm to check if number is Power of Two? (Answer )
- Algorithm to remove duplicates from array without using Collection API? (Solution )
- Program to String in Java using recursion? (Solution )
- Algorithm to check if a number is Palindrome? (Solution )
- How to check if a number is binary in Java? (Solution )