Find the n-th Fibonacci number. The Fibonacci numbers are integers 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Wikipedia says:

*By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two. *

For example the 7-th Fibonacci number in the sequence is 8. Here are a few solutions. The first one is a trivial one and follows the definition - i.e. it uses recursion.

long fibonacciRecursive(int n) {
if (n == 0 || n == 1) {
return n;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

The second solution is iterative. A drawback here is that the size of the array which is used to store the Fibonacci numbers needs to be defined statically.

long fibonacciIterative(int n) {
int size = 100;
long[] fibonacciNumbers = new long[size + 1];
fibonacciNumbers[0] = 0;
fibonacciNumbers[1] = 1;
for (int i = 2; i <= n; i++) {
fibonacciNumbers[i] = fibonacciNumbers[i - 1]
+ fibonacciNumbers[i - 2];
}
return fibonacciNumbers[n];
}

The third solution is again iterative. The difference here is that it uses an array with size 3. This is a very elegant and optimized solution.

long fibonacciIterativeLowMem(int n) {
int[] fibonacciNumbers = new int[3];
fibonacciNumbers[0] = 0;
fibonacciNumbers[1] = 1;
for (int i = 2; i <= n; i++) {
fibonacciNumbers[i % 3] = fibonacciNumbers[(i - 1) % 3]
+ fibonacciNumbers[(i - 2) % 3];
}
return fibonacciNumbers[n % 3];
}

Here is one more solution that uses an optimization called

memoization. The idea here is that we avoid the calculation of the tasks we already had calculated.

long fibonacciMemoization(int n) {
int size = 100;
long[] fibonacciNumbers = new long[size+1];
fibonacciNumbers[0] = 0;
fibonacciNumbers[1] = 1;
for (int i = 2; i < size; i++) {
fibonacciNumbers[i] = -1;
}
if (fibonacciNumbers[n] != -1) {
return fibonacciNumbers[n];
} else {
fibonacciNumbers[n] = fibonacciMemoization(n - 1)
+ fibonacciMemoization(n - 2);
return fibonacciNumbers[n];
}
}