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.        
    }
}