Opgaver
Rekursion

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.

Et palindrom er en tekststreng, som læses ens både forfra og bagfra. Eksempelvis er strengen "regninger" et palindrom. Vi kan også sige at et palindrom er en tekststreng som er lig med sin egen strengomvending.

Skriv først en iterativ funktion int is_palindrome_iter(char *str), der afgør om str er et palindrom. En iterativ funktion er en funktion, som programmeres ved brug af en while-løkke eller en for-løkke. Funktionen skal returnere 1 hvis str er et palindrom, og 0 hvis str ikke er et palindrom.

Skriv dernæst en tilsvarende rekursiv udgave int is_palindrome_rec(char *str).

Den rekursive funktion skal løse nøjagtig det samme problem som den iterative funktion; Altså om parameteren str er et palindrom. Den skal gøre dette ved at undersøge om en bestemt (lidt mindre) delstreng af strengen er et palindrom. Hvis det hjælper dig, kan du overveje at indføre en hjælpefunktion til is_palindrome_rec, for at gøre dette.

Målet med denne opgave er at opnå viden og færdigheder i at arbejde med såvel rekursive som iterativt programmerede funktioner. Målet er endvidere at opnå yderligere viden og færdigheder i simpel programmering med tekststrenge.

Programmer en funktion

  int quotient(int dividend, int divisor)

som beregner dividend / divisor ved brug af rekursion (ved gentagen subtraktion).

Skriv ligeledes en rekursiv funktion

  int modulus(int dividend, int divisor)

som beregner resten, dividend % divisor.

Dette er hints til opgave 1 side 587 i Problem Solving and Program Design in C, 8ed (svarende til opgave 1 side 583 i 7ed).

Der findes en video som giver et oplæg til problemløsningen. Jeg anbefaler at I ser denne video forud for løsningen af opgaven.

  int grid[5][5] = {
                     {1, 1, 0, 0, 0},
                     {0, 1, 1, 0, 0},
                     {0, 0, 1, 0, 1},
                     {1, 0, 0, 0, 1},
                     {0, 1, 0, 1, 1},
                    };

I denne opgave vil vi programmere iterative beregninger med brug af rekursion. Funktionerne, som skal programmeres i denne opgave, skal altså følge det mønster vi har set i funktionen iterative_factorial (et program i lektionen om rekursion).

Vi har set iterative udgaver af Euclids algoritme i lektionen om gentagelse og løkker og vi har set en gcd funktion i lektionen om funktioner.

Programmer først en rekursiv udgave af den version af Euclids algoritme, der er baseret på gentagen restberegning.

Programmer dernæst en rekursiv udgave af den version af Euclids algoritme, der er baseret på gentagen subtraktion.