# First 100 of Fibonacci

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

## Use BigInteger

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 232Integer.MAX_VALUE.

## A naive approach

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(2n) runtime.

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

## Memoization

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) {

fib(100);

for (BigInteger n : fib100) {
System.out.println(n);
}
}

static BigInteger fib(int n) {

if (n >= fib100.size()) {
}