**Question:** Write a function that computes the list of the first 100 Fibonacci numbers.

Related Tags:

Java's `int`

type is a 32-bit sized primitive type that has a maximum of 2,147,483,647. Since our fibonacci sequence values will be bigger than this, we have to use a `BigInteger`

class. `BigInteger`

is implemented using an `int[]`

, so the maximum is `2 ^{32Integer.MAX_VALUE}`.

We could naively use a recursion method, but for each call that would branch out another 2 recursive calls. Effectively, this would have a `O(2 ^{n})` runtime.

```
static BigInteger fibSlow(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
```

Thus, we need to store the already-calculated elements into a list, then retrieve it when needed. The process of storing and retrieving already-calculated values is termed memoization.

```
import java.util.ArrayList;
import java.math.BigInteger;
public class Fibonacci100 {
static ArrayList<BigInteger> fib100 = new ArrayList<>();
public static void main(String[] args) {
fib100.add(BigInteger.ZERO);
fib100.add(BigInteger.ONE);
fib(100);
for (BigInteger n : fib100) {
System.out.println(n);
}
}
static BigInteger fib(int n) {
if (n >= fib100.size()) {
fib100.add(n, fib(n-1).add(fib(n-2)));
}
return fib100.get(n);
}
}
```

Came up with a better solution or have a question? Comment below!

Next Challenge: Rotate a 2d array in place