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 c

*ode example of printing Fibonacci Series in Java*. Fibonacci series is printed using both Iterative method and recursive method implemented using Java programming language.**import**java.util.Scanner;

*/***

* Java program to calculate and print Fibonacci number using both recursion and Iteration.

* Fibonacci number is sum of previous two Fibonacci numbers fn= fn-1+ fn-2

* first 10 Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

* @author

*/* Java program to calculate and print Fibonacci number using both recursion and Iteration.

* Fibonacci number is sum of previous two Fibonacci numbers fn= fn-1+ fn-2

* first 10 Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

* @author

*/

**public**

**class**FibonacciCalculator {

**public**

**static**

**void**main(

**String**args[]) {

*//input to print Fibonacci series upto how many numbers*

**System**.out.println("Enter number upto which Fibonacci series to print: ");

**int**number =

**new**

**Scanner**(

**System**.in).nextInt();

**System**.out.println("Fibonacci series upto " + number +" numbers : ");

*//printing Fibonacci series upto number*

for(

**int**i=1; i<=number; i++){

**System**.out.print(fibonacci2(i) +" ");

}

}

*/**

* Java program for Fibonacci number using recursion.

* This program uses tail recursion to calculate Fibonacci number for a given number

* @return Fibonacci number

*/

* Java program for Fibonacci number using recursion.

* This program uses tail recursion to calculate Fibonacci number for a given number

* @return Fibonacci number

*/

**public**

**static**

**int**fibonacci(

**int**number){

if(number == 1 || number == 2){

**return**1;

}

**return**fibonacci(number-1) + fibonacci(number -2);

*//tail recursion*

}

*/**

* Java program to calculate Fibonacci number using loop or Iteration.

* @return Fibonacci number

*/

* Java program to calculate Fibonacci number using loop or Iteration.

* @return Fibonacci number

*/

**public**

**static**

**int**fibonacci2(

**int**number){

if(number == 1 || number == 2){

**return**1;

}

**int**fibo1=1, fibo2=1, fibonacci=1;

for(

**int**i= 3; i<= number; i++){

fibonacci = fibo1 + fibo2;

*//Fibonacci number is sum of previous two Fibonacci number*

fibo1 = fibo2;

fibo2 = fibonacci;

}

**return**fibonacci;

*//Fibonacci number*

}

}

**Output:**

Enter number upto which Fibonacci series to print:

12

Fibonacci series upto 12 numbers :

1 1 2 3 5 8 13 21 34 55 89 144

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.##
__Fibonacci number in Java with memorization__

Here is the code example of printing Fibonacci number with memorization technique :

*/**

* Java Program to calculate Fibonacci numbers with memorization

* This is quite fast as compared to previous Fibonacci function especially for

* Java Program to calculate Fibonacci numbers with memorization

* This is quite fast as compared to previous Fibonacci function especially for

** calculating factorial of large numbers.*

*/

*/

**public**

**static**

**int**improvedFibo(

**int**number){

**Integer**fibonacci = cache.get(number);

if(fibonacci !=

**null**){

**return**fibonacci;

*//fibonacci number from cache*

}

fibonacci = fibonacci2(number);

*//fibonacci number not in cache, calculating it*

cache.put(number, fibonacci);

*//putting fibonacci number in cache for future request*

**return**fibonacci;

}

Comparison

*//comparison of performance of Fibonacci number with memorization*

**int**number = 100000000;

**long**startTime =

**System**.nanoTime();

**int**result = fibonacci2(number);

*//fibonacci number with memorization*

**long**elapsedTime =

**System**.nanoTime() - startTime;

**System**.out.println("Time taken to calculate Fibonacci number upto 100M without memorization:" + elapsedTime);

startTime =

**System**.nanoTime();

result = improvedFibo(number);

*//Fibonacci number with memorization*

elapsedTime =

**System**.nanoTime() - startTime;

**System**.out.println("Time taken to calculate Fibonacci number upto 100M with memorization:" + elapsedTime);

Output:

**Time**taken to calculate Fibonacci number upto 100M without memorization:149479613

**Time**taken to calculate Fibonacci number upto 100M with memorization:118972384

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.
I had a homework exercise to write a Java program to print Fibonacci series up-to 100. Can I use your Java program to print Fibonacci series, is using recursion in a homework or programming exercise is valid ?

ReplyDeleteShouldn't that be called "memoization" ?

ReplyDeleteThe comments in your code are wrong : you are indeed using recursion, but not tail-recursion.

ReplyDeleteTail recursion means that the last action performed by the method is directly returning the value from the recursive call, without modifying it.

In your example, your function calls itself recursively twice, before adding the two return values and returning the result. Hence, you aren't performing tail recursion.

A correct tail recursion implementation would be :

public static int tailRecursiveFibonacci(long number) {

// Bootstrap

return tailRecursiveFibonacci(3, 1, 1, number - 3);

}

private static int tailRecursiveFibonacci(long currentRank, int antePreviousResult, int previousResult, long howManyMoreRanks) {

final int resultForCurrentRank = antePreviousResult + previousResult;

if (howManyMoreRanks == 0) return resultForCurrentRank;

return tailRecursiveFibonacci(currentRank + 1, previousResult, resultForCurrentRank, howManyMoreRanks - 1);

}

Actually, you don't need the HowManyMoreRanks parameter:

Deletepublic int fib2 (n){

return fib (n,1,1)

}

public int fib_internal2 (int n, int acc1, int acc2) {

if (n == 0 || n == 1)

return acc2

else

return fib_internal2 (n-1, acc2, acc1 + acc2)

}

There is overflow for 48th fibonacci number for int return type.

ReplyDeleteSee other comment about recursion vs tail recursion. The tail recursive solution carries everything it needs with it rather than leaving it behind to be recombined when the stack is unwound, thus does not need multiple stack frames and won't cause a stack overflow.

DeleteAnonymous is correct.. this program will overflow the moment it crosses integer bounds.. i think we should use double as the datatype to initialize the variables.

ReplyDeleteTwo words as string values are provided as input. The program should find and print the positions having matching alphabets as output.

ReplyDeleteExample input and output:

If the input is "engine angry", the output should be "2 3" (As n in second position and g in third position match)

If the input is "male level", the output should be "4" (As e in fourth position matches)

i need answer.......

import java.io.BufferedReader;

ReplyDeleteimport java.io.IOException;

import java.io.InputStreamReader;

public class buddyq {

public static void main(String[] args) throws NumberFormatException, IOException {

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

System.out.println("enter the number::::::::::");

int a=Integer.parseInt(br.readLine());

System.out.println("fibinocii numbers are:::::");

int f1, f2=0, f3=1;

for(int i=1;i<=a;i++){

System.out.print(" \n"+f3+"\n ");

f1 = f2;

f2 = f3;

f3 = f1 + f2;

}

}

}

"A technique called memorization can be used to drastically improve performance..." because formula F3=F2+F1 is very slow for large numbers (exponential complexity). Enjoy performance http://slorents.blogspot.com.au/2013/11/climb-ladder-with-n-step.html

ReplyDeleteThe caching pattern is called "Memoization", not memorize.

ReplyDeletehttp://en.wikipedia.org/wiki/Memoization

Here is a smart-alec implementation:

ReplyDeletepublic class Fib

{

static final double a1 = (Math.sqrt(5) + 1)/2;

static final double a2 = (Math.sqrt(5) - 1)/2;

static final double sq5 = Math.sqrt(5);

public static double fib(int n)

{

double term2 = (n % 2 == 1) ? Math.pow(a2,n) : -Math.pow(a2,n);

return (Math.pow(a1,n) + term2)/sq5;

}

public static void main(String[] args)

{

if (args.length < 1)

{

System.err.println("Missing argument");

System.exit(1);

}

int n = 0;

try

{

n = Integer.parseInt(args[0]);

}

catch (Exception e)

{

System.err.println("Bad argument");

System.exit(1);

}

System.out.println("fib(" + n + ") = " + fib(n));

}

}

The reason I called it smart-alec is that it defeats the likely purpose of the interview challenge - demonstrate your understanding of recursion. Fibonacci sequence can be computed using a formula which you can derive by solving a characteristic equation, and the computation will outperform the recursive or iterative method for sufficiently large values of N.

Hi,

ReplyDeleteThere is faults in your code examples shown here.

The Fibonacci numbers starts with a 0.

The first 21 Fibonacci numbers Fn for n = 0, 1, 2, ..., 20 are:[16]

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Please see Wiki page:

http://en.wikipedia.org/wiki/Fibonacci_numbers