For some reason, it seem like writing a Java function that returns Fibonacci number is favorited by interviewers. I really find it difficult to understand why an interviewer would ask this kind of question, since it is not a question that implies on any practical knowledge or experience and can be easily memorized.

But, anyway, let’s see how it is done:

There are 2 ways of writing this function: recursive and none recursive. Interviewers may ask to write both versions.

Let’s start with the recursive version, which is surprisingly simple. well… simple if do not try to debug it in your head, but think of the process in a more mathematical way. In general, I believe that solving recursion problems is much simpler if you think of the solution in an abstract way, rather than trying to figure what exactly going on on each iteration.

Well, this is how the recursive function looks like:

Note, that both 2 first numbers in the series are handled separately. The output of the test program is of course: 144.package com.bashan.blog.interview;`/**`

* @author Bashan*/public class Fibonacci {public static int fibonacci1(int n){`if (n == 0)`

{`return 0;`

}else if (n == 1){`return 1;`

}`else`

{`return fibonacci1(n - 1) + fibonacci1(n - 2);`

}}

public static void main(String[] args){System.out.println(fibonacci1(12));}}

This function can be shorten to a single line of code:

The none recursive version should always save the current and the previous number in order to calculate the next number in the series. Let’s see how it looks in Java code:package com.bashan.blog.interview;`/**`

* @author Bashan*/public class Fibonacci {public static int fibonacci2(int n){`return n == 0 ? 0 : (n == 1 ? 1 : (fibonacci1(n - 1) + fibonacci1(n - 2)));`

}}

Note, that we return prevN rather than currentN. This saves us for writing a logic to handle the case of n = 0.package com.bashan.blog.interview;`/**`

* @author Bashan*/public class Fibonacci {public static int fibonacci3(int n){int prevN = 0, currentN = 1;`for (int i = 0; i < n; i++)`

{int saveCurrentN = currentN;currentN = prevN + currentN;prevN = saveCurrentN;}

`return prevN;`

}}

Here is a Java class that contains all 3 functions.

Check out this cool infographic to learn more about Fibonacci series.

hey can help me in fibanocci series to write a program to display set of 25 prime numbers?

ReplyDeleteHi, I am trying to be sure on what exactly you mean: Do you want to find the first 25 Fibonacci numbers which are ALSO prime numbers?

ReplyDelete