Opgave 11.1
En Fibonacci funktion med huskeværk

Den rekursive fib funktion, som kan programmeres således

long fib(int n){
  long result;

  if (n == 0)
    result = 0;
  else if (n == 1)
    result = 1;
  else
    result = fib(n-1) + fib(n-2);

  return result;
}

lider af et alvorligt effektivitetsproblem. Hvert kald af fib(n) for n > 1 leder til to andre kald af fib. Mange af disse kald har allerede været udført en eller flere gange tidligere. Prøv f.eks. at danne dig et overblik over hvor mange gange fib(2) bliver kaldt når vi beregner fib(5).

Ideen i denne opgave er at huske på (lagre) værdien af fib(n), når den er beregnet første gang. Hvis vi efterfølgende kalder fib(n) igen, trækker vi værdien ud af lageret snarere end at genberegne fib(n) rekursivt. Denne teknik kaldes for memoisering. Her er det pseudoprogram vi har studeret:

long fib(long n){     /* working program: fib-memo.c - an exercise*/
  long result;
  
  Erklaer huskevaerk;

  if (n == 0)
    result = 0;
  else if (n == 1)
    result = 1;
  else if (Vi allerede har beregnet vaerdien en gang)
    result = den huskede vaerdi;
  else {
    result = fib(n-1) + fib(n-2);
    Husk paa vaerdien;
  }

  return result;
}

int main(void) {
  long i;

  for(i = 0; i < 100; i++)
    printf("Fib(%li) = %li\n", i, fib(i));
  
  return 0;
}

Modificer ovenstående versioner af fib, således at den lagrer værdien af fib(n) når udtrykket er beregnet. Og således at den udtrækker og returnerer en lagret værdi, i stedet for at gå i gang med en genberegning. Det er oplagt at allokere et array af element-typen long int til formålet. Overvej en anvendelse af en statisk lokal variabel!

Kald den oprindelige af fib og din nye variant af fib funktionen med alle heltal mellem n og 45, og vurder dermed effekten af memoiseringen.