What a Java Programmer Should Know About Fibonacci Numbers

Often during interviews, especially at foreign companies, people may be asked about algorithms, and in a stressful situation, frantically remembering something is not always easy. Therefore, you need to prepare. To begin with, at least refresh your memory of the basic algorithms. Today we will analyze such a phenomenon as Fibonacci numbers and the most common variants of problems related to them. Fibonacci numbers are a sequence of natural numbers that begins with the numbers zero and one, and each subsequent number is equal to the sum of the previous two: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0, n ∈ Z

It is worth noting that sometimes 0 is omitted, and the series begins with 1 1 2 3... As a rule, in the conditions of the problem it is immediately specified which first two numbers the series begins with (0.1 or 1.1), so further we will consider solutions for both cases.

Getting first n Fibonacci numbers in Java

Suppose we have a task to obtain the first n Fibonacci numbers.

case 0.1:

A certain number n comes to us:
```
int[] arr = new int[n];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < arr.length; ++i) {
  arr[i] = arr[i - 1] + arr[i - 2];
}
```
We create an array of size n. The first two elements will be equal to zero and one, and the remaining elements are obtained by going through this loop and using the previous numbers from the array.

And we display:
```
for (int i = 0; i < arr.length; ++i) {
  System.out.println(arr[i]);
}
```
Set int n = 10;

And we get:
```
0
1
1
2
3
5
8
13
21
34
```

for case 1.1 the solution is actually no different:

int[] arr = new int[n];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < arr.length; ++i) {
  arr[i] = arr[i - 1] + arr[i - 2];
}

All we needed to change was the first element of the array arr[0]: from 0 to 1. Accordingly, the first 10 elements will be:

First n Fibonacci numbers via stream

But we want to show our level. So let's see what this solution would look like using stream .

for 0.1:
```
Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
   .limit(n)
   .map(y -> y[0])
   .forEach(x -> System.out.println(x));
```
The static iterate method of the Stream class returns an infinite ordered stream created by applying the function to the initial array arr. In our case, the function is to set the rule for composing each new array, based on the previous one. As a result, we will get a stream of arrays:
```
{0,1}
{1,1}
{1, 2}
{2, 3}
{3, 5}
{5, 8}
{8, 13}
{13, 21}
{21, 34}
{34, 55}
…..
```
But there will be an infinite number of them, and therefore using .limit(n) we reduce the number of elements to the first n (in our case to 10).

However, we don’t need a stream of arrays, so using .map(y -> y[0]) we select the first element of each array and get a stream with the numbers we need and print it to the console using forEach.

Looks cooler, doesn't it?
with the first elements being 1,1 this code will also be almost the same:
```
Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));
```
Again, the differences are in the initial element: instead of {0, 1} we set {1, 1}

Actually, the results will be the same as in the previous example.

Sum of Fibonacci numbers

What if we were asked to get the sum of the Fibonacci numbers up to the nth element inclusive? This should not cause us any difficulties. Let's take a solution with a stream and replace forEach with a couple of other methods:

for 0.1:

int n = 10;
int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(t -> t[0])
     .mapToInt(Integer::intValue)
     .sum();
System.out.println(result);

Using .mapToInt(Integer::intValue) we convert our stream to a numeric IntStream and use its .sum() method to get the sum of all elements.

for the case with 1,1 initial elements, instead of {0, 1} we set {1, 1}.

Getting the nth number in the Fibonacci series

Sometimes you are asked to print not a series of numbers, but specifically the nth number in the Fibonacci series. As a rule, this only makes the task easier, because you can easily adapt previous solutions for this. Well, what about solving the problem through recursion?

for 0.1:

public int getFibonacciValue(int n) {
  if (n <= 1) {
     return 0;
  } else if (n == 2) {
     return 1;
  } else  {
     return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
  }
}

To run the algorithm with 0,1, it is necessary to specify that when we try to get the first element, we get 0, and the second - 1. In fact, we, as in previous solutions, need to set the first two elements.

the implementation for 1.1 will be slightly different:
```
public int getFibonacciValue(int n) {
  if (n == 0) {
     return 0;
  } else if (n == 1) {
     return 1;
  } else  {
     return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
  }
}
```
In this case, we only need to set the first element as 1, since the second element will be the same, and the method's response will be the same.

At the same time, we set the method’s reaction to 0, because if we don’t set it, then when 2 comes as an argument, the same method is called recursively, but with argument 0. Next, the same method will be launched, but with negative numbers, and so on until negative infinity. As a result, we will receive a StackOverflowError .

However, the recursive method is not recommended because unlike the previous methods, which run in O(n) linear time, the recursive method can take significantly longer to complete. Why? What a Java programmer should know about Fibonacci numbers - 3

What a Java programmer should know about Fibonacci numbers - 3

The recursive method can take a long time, since during the calculation process the function will be called many times from the same argument. For example, when evaluating getFibonacciValue(7), the function will make recursive calls to getFibonacciValue(5) and getFibonacciValue(6), both recursive calls will call getFibonacciValue(4)), which will result in calling the same operations multiple times. At the interview, you can show this method as a solution, but at the same time talk about its shortcomings and offer another method in return. It is also worth noting that the int type in Java allows you to store from -2147483648 to 2147483647, so you will only be able to calculate the first 46 Fibonacci numbers: if we try to get the next 47th, there will be an overflow and we will get a negative number. If we use the long data type instead of int, we will be able to correctly calculate the first 91 Fibonacci numbers. To calculate subsequent Fibonacci numbers, you need to use the BigInteger class, which implements the logic for storing and arithmetic operations of really BIG numbers.