class EffektivFib {
    // Dette er et eksempel på en  mer effektiv måte å regne ut fibbonacci-tall på. Dette er ikke ekesamensrelevant, men illusterer
    // hvordan man kan gjøre rekursive metoder litt mer effektive ved å lagre mellomregninger. Enten kan man gjøre det slik jeg har gjort her ved å ha en 
    // global variabel som lagrer mellomregninger, eller man kan sende memoet med i funksjonskallet.  

     private long [] memo; // For å ungå dobbelt arbeid lagrer vi tallene vi regner ut underveis. Dette lar oss effektivt regne ut mye høyere verdier av Fibbonaccitallene.

    public EffektivFib(int n) {
        memo = new long[n];
        memo[0] = 1;
    }

    public long nthFib() {
        return nthFib(memo.length);
    }

    private long nthFib(int n) {
        if (n == 0) return 0;
        
        else if (memo[n-1] != 0) return memo[n-1]; // Slår opp i memoet, og dersom tallet finnes i lista returnerer vi det.
        
        memo[n-1] = nthFib(n-1) + nthFib(n-2); // Hvis ikke regner vi ut det neste tallet, og returnerer det. 
        return memo[n-1];
        
    }

    public static void main(String[] args) {
        EffektivFib f = new EffektivFib(92); // Dette er det høyeste fibonaccitallet vi kan regne ut med long uten at tallet overløper (tallet er for stort til å lagte med 64 bit). 
        f.nthFib();
        for (long i : f.memo) System.out.println(i); // Skriver ut alle tallene.        
    }
}