Previous achievement | Next achievement

( F. Imperativ programmering )

F14

Svansrekursion

Level Assessment
4 L

(Eng. "tail recursion")

Använd svansrekursion för rekursiva funktioner med potentiellt stort djup.

Svansrekursion är rekusion där varje rekursivt anrop kommer som det sista funktionen gör. Beakta följande, icke-svansrekursiva funktion:

int sum(int *numbers[], int num_siz)
{
  if (num_siz > 0)
  {
    int rest = sum(numbers+1, num_siz-1);
    return *numbers + rest;
  }
  else
  {
    return 0;
  }
}

I detta fall används stacken som en temporär lagringsplats för alla temporära resultat. Vi kan skriva om funktionen på detta svansrekursiva vis:

int sum(int *numbers[], int num_siz, int acc)
{
  if (num_siz > 0)
  {
    return sum(numbers+1, num_siz-1, acc + *numbers);
  }
  else
  {
    return acc;
  }
}

I detta fall behövs ingen stack för att lagra tempoära värden (varför?) och som en konsekvens av detta kan en bra kompilator skriva om funktionen så att den kan köra i konstant minnesutrymme (mer eller mindre tranformera koden till en loop).

Kan en/din C-kompilator göra så-kallad "tail call-optimisation"? Under vilka omständigheter? Hur kan du pröva det?

Om din kompilator inte garanterar att svansrekursion transformeras till loopar -- kan det vara problematiskt? Hur?

För att bli godkänd på detta mål måste du även visa hur du skriver om en rekursiv funktion på svansrekursivt vis.

Ge gärna kommentarer och rapportera buggar (klicka på den senaste commiten)

Edit | Back