Fibonacci sequence is a sequence of integers where every number after the first two is the sum of the two preceding ones.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
Very often on software development positions job interview you might be asked to write a a method that receives an index of specific number in Fibonacci sequence and returns this number.
There are two approaches to solve this problem – Iterative and Recursive. Today you’ll see the both versions solved in Java.
Fibonacci Iterative Approach
static private int FibonacciIterative(int n){
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
Fibonacci Recursive Approach
static private int FibonacciRecursive(int n){
if (n == 0) return 0;
if (n == 1) return 1;
return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}
Let’s test our code
public static void main(String[] args) {
System.out.println("Recursive approach: " + String.valueOf(FibonacciRecursive(6)));
System.out.println("Iterative approach: " + String.valueOf(FibonacciIterative(7)));
}
Output:
Recursive approach: 8
Iterative approach: 13
