Rekursion og stak

Lad os vende tilbage til funktioner og studere dem mere grundigt.

Vores frste emne vil vre rekursion.

Hvis du ikke er ny i programmering, s er det sandsynligvis kendt og du kan springe dette kapitel over.

Rekursion er et programmeringsmnster, som er nyttigt i situationer hvor en opgave kan opdeles i flere opgaver af samme type, men mere simple. Eller nr en opgave kan formindskes til en enkel handling plus en mere simpel variant af samme opgave. Eller, som vi vil se snart, for at hndtere bestemte datastrukturer.

Nr en funktion lser en opgave, kan den i processen kalde mange andre funktioner. En delmngde heraf er nr en funktion kalder sig selv. Det kaldes rekursion.

To mder at tnke p

For noget simpelt at starte med lad os skrive en funktion pow(x, n) som hver x til en naturlig potens af n. Med andre ord, multiplicerer x med sig selv n gange.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Der er to mder at implementere det.

1. Iterativ tankegang: for-loopet:

   function pow(x, n) {
     let result = 1;
   
     // Gang resultatet med x n gange i loopet
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert( pow(2, 3) ); // 8

2. Rekursiv tnkning: Simplificer opgaven og kald dig selv:

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

Bemrk hvordan den rekursive variant er grundiglggende anderledes.

Nr pow(x, n) kaldes splittes udfrelsen til to forgreninger:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. Hvis n == 1, s er alt trivielt. Dette kaldes basen for rekursion, fordi den fordi den umiddelbart producerer det obviouse resultat: pow(x, 1) er lig med x.
2. Ellers kan vi reprsentere pow(x, n) som x * pow(x, n - 1). I matematik ville man skrive xn = x * xn-1. Dette kaldes et rekursivt trin: vi transformerer opgaven til en enkel handling (multiplication med x) og et mere simpelt kald af samme opgave (pow med lavere n). Nste trin forenkler det yderligere og yderligere indtil n nr 1.

Vi kan ogs sige at pow kalder sig selv rekursivt indtil n == 1.

[]

For eksempel, for at udregne pow(2, 4) vil den rekursive variant gre disse trin:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

s rekursionen reducerer et funktionskald til et mere simpelt, og s videre, indtil resultatet bliver benlyst.

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

Det maksimalt antal indlejrede kald (inklusive det frste) kaldes rekursionsdybde. I vores tilflde vil det vre prcis n.

Den maksimale rekursionsdybde er begrnset af JavaScript-motoren. Vi kan stole p, at den er 10.000, nogle motorer tillader mere, men 100.000 er sandsynligvis uden for grnsen for de fleste af dem. Der er automatiske optimeringer, der hjlper med at optimere antallet af kald (tail calls optimizations), men de er ikke endnu understttet overalt og virker kun i simple tilflde.

Det begrnser anvendelsen af rekursion, men den forbliver stadig meget bred. Der er mange opgaver hvor den rekursive mde at tnke giver enklere kode der er nemmere at vedligeholde.

Eksekveringens kontekst og stak

Lad os undersge hvordan rekursive kald fungerer. For det vil vi kigge under huden p funktioner.

Informationen om processen for eksekvering af en krende funktion er gemt i dens eksekveringskontekst.

Eksekveringskonteksten er en intern datastruktur, der indeholder detaljer om eksekveringen af en funktion: hvor kontrollbet er nu, de aktuelle variabler, vrdien af this (vi bruger det ikke her) og andre interne detaljer.

Et funktionskald har prcis n eksekveringskontekst forbundet med det.

Nr en funktion udfrer et indlejret kald, sker flgende:

• Den nuvrende funktion pauses.
• Den eksekveringskontekst, der er forbundet med den, huskes i en speciel datastruktur kaldet execution context stack.
• Det indlejrede kald udfres.
• Nr det er frdigt, hentes den gamle eksekveringskontekst fra stakken og den ydre funktion genoptages fra hvor den stoppede.

Lad os se hvad der sker under kaldet pow(2, 3).

pow(2, 3)

I begyndelsen af kaldet pow(2, 3) vil eksekveringskonteksten gemme variablerne: x = 2, n = 3, og kontrollbet er p linje 1 i funktionen.

Vi kan skitsere det som:

• Context: { x: 2, n: 3, at line 1 } pow(2, 3)

Det er her funktionen begynder at eksekvere. Betingelsen n == 1 er falsk, s flowet fortstter til den anden gren af if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

Variablene er de samme, men linjen ndres, s konteksten er nu:

• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

For at udregne x * pow(x, n - 1), vi skal lave et indlejret kald af pow med nye argumenter pow(2, 2).

pow(2, 2)

For at udfre et indlejret kald, husker JavaScript den nuvrende eksekveringskontekst i execution context stack.

Her kalder vi den samme funktion pow, men det spiller ingen rolle. Processen er den samme for alle funktioner:

1. Den nuvrende kontekst huskes verst p stakken.
2. En ny kontekst oprettes for underkaldet.
3. Nr underkaldet er frdigt bliver den gamle kontekst fjernet fra stakken, og dens eksekvering genoptages.

Her er kontekststakken efter vi er get ind i underkaldet pow(2, 2):

• Kontekst: { x: 2, n: 2, at line 1 } pow(2, 2)
• Kontekst: { x: 2, n: 3, at line 5 } pow(2, 3)

Den nye nuvrende eksekveringskontekst er verst (og fed), og de tidligere huskede kontekster er nedenfor.

Nr underkaldet er frdigt er det nemt at genoptage den gamle kontekst, fordi den beholder bde variablerne og den prcise sted i koden hvor den stoppede.

pow(2, 1)

Processen gentages: et nyt underkald oprettes p linje 5, nu med argumenterne x=2, n=1.

En ny eksekveringskontekst oprettes, den gamle kontekst bliver pushed verst p stakken:

• Kontekst: { x: 2, n: 1, at line 1 } pow(2, 1)
• Kontekst: { x: 2, n: 2, at line 5 } pow(2, 2)
• Kontekst: { x: 2, n: 3, at line 5 } pow(2, 3)

Der er 2 gamle kontekster og 1 nuvrende kontekst for pow(2, 1).

Udgangen

Med udfrelsen af pow(2, 1) vil betingelsen n == 1, i modstning til fr, vre sand. Derfor udfres den frste gren af if:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

Der er ikke flere indlejrede kald, s funktionen afslutter og returnerer 2.

Nr funktionen afslutter, er dens eksekveringskontekst ikke lngere ndvendig, s den fjernes fra hukommelsen. Den tidligere kontekst genoprettes fra toppen af stakken:

• Context: { x: 2, n: 2, at line 5 } pow(2, 2)
• Context: { x: 2, n: 3, at line 5 } pow(2, 3)

Udfrelsen af pow(2, 2) genoptages. Den har resultatet af underkaldet pow(2, 1), s den ogs kan frdiggre evalueringen af x * pow(x, n - 1), og returnere 4.

S den tidligere kontekst genoprettes:

• Kontekst: { x: 2, n: 3, at line 5 } pow(2, 3)

Nr den afslutter, har vi et resultat p pow(2, 3) = 8.

Dybden af rekursionen i dette tilflde var: 3.

Som vi kan se fra illustrationerne ovenfor, er rekursionsdybden lig med det maksimale antal kontekster i stakken.

Bemrk hukommelseskravene. Kontekster tager plads. I vores tilflde krver en udregning til potens af n faktisk hukommelse for n kontekster, for alle lavere vrdier af n.

En algoritme baseret p lkker er mere hukommelsesvenlig:

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Denne udgave af pow bruger kun en enkelt kontekst der ndrer i og result i processen. Dens hukommelseskrav er sm, faste og afhnger ikke af n.

Enhver rekursion kan omskrives som en lkke. Versionen baseret p lkker er ofte mere effektiv.

men nogle gange er omskrivningen ikke-triviel, isr nr en funktion bruger forskellige rekursive underkald afhngigt af betingelser og fletter deres resultater eller nr forgreningen er mere kompleks. Endelig kan optimeringen vre undvendig til en grad hvor det ikke er vrd vrd at investere i.

Rekursion kan give en kortere kode der nemmere at forst og understtte. Optimeringer er ikke ndvendige overalt. Det vigtigste vi har brug for er god kode, og her kan rekursion vre at foretrkke (nr man har knkket koden il at forst den).

Rekursive traversals

Et anden god brug af rekursion er rekursive traversal. Jeg tror ikke der er et godt direkte dansk ord, men det betyder noget i stil med gennemlb af alle elementer i en struktur.

Forestil dig et firma. I det kan medarbejdernes struktureres i et objekt i stil med dette:

let company = {
  sales: [{
    name: 'John',
    salary: 1000
  }, {
    name: 'Alice',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Peter',
      salary: 2000
    }, {
      name: 'Alex',
      salary: 1800
    }],

    internals: [{
      name: 'Jack',
      salary: 1300
    }]
  }
};

Med andre ord et firma har afdelinger.

• En afdeling kan have et array af medarbejdere. For eksempel har salgsafdelingen (sales) 2 medarbejdere: John og Alice.

• Eller en afdeling kan opdeles i underafdelinger, som development har to grene: sites og internals. Hver af dem har deres egen medarbejderliste.

• Det er ogs muligt at en underafdeling vokser og opdeles i underunderafdelinger (eller hold).

  For eksempel kan sites-afdelingen i fremtiden opdeles i hold for siteA og siteB. Og de, potentielt, kan opdeles end mere. Det er ikke p billedet, bare noget at have i tankerne.

Lad os nu forestille os at vi vil have en funktion der lgger alle lnninger (salaries) sammen. Hvordan gr vi det?

En iterativ tilgang er ikke nem da strukturen ikke er simpel. En frste id kunne vre at gennemlbe company med en nested subloop over 1. niveau afdelinger. Men s skal vi have flere nested subloops for at gennemlbe medarbejderne i 2. niveau afdelinger som sites Og s en subloop inden i dem for 3. niveau afdelinger som mske vil opst i fremtiden? Hvis vi stter 3-4 nested subloops i koden for at gennemlbe et enkelt objekt, bliver det ret hurtigt svrt at hndtere.

Lad os prve rekursion.

Som vi kan se, nr vores funktion fr en afdeling den skal sammentlle, er der to mulige tilflde:

1. Enten er den en simpel afdeling med et array af medarbejdere da kan vi summe lnningerne i en simpel loop.
2. Eller den er et objekt med N underafdelinger da kan vi lave N rekursive kald for at f summen for hver af de underafdelinger og kombinere resultaterne.

Det frste tilflde er basen for rekursionen, det trivielle tilflde, nr vi fr et array.

Det andet tilflde nr vi fr et objekt er det rekursive trin. En kompleks opgave opdeles i underopgaver for mindre afdelinger. De kan i sin tur opdeles igen, men snarest eller senest vil opdeltningen slutte ved (1).

Algoritmen er sandsynligvis endnu lettere at lse fra koden:

let company = { // det samme objekt, komprimeret
  sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
  development: {
    sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
    internals: [{name: 'Jack', salary: 1300}]
  }
};

// Funktionen der udfrer jobbet
function sumSalaries(department) {
  if (Array.isArray(department)) { // Tilflde (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
  } else { // Tilflde (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // rekursivt kald til underafdelinger. Sammentl alle deres returnerede resultater
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

Koden er kort og (forhbentlig) nem at forst. Det er kraften i rekursionen. Den virker ogs for ethvert niveau af underafdelingsindlejring.

Her er et diagram over kaldene:

[]

Her kan vi mske nemmere se principperne: for et objekt {...} udfres subkald, mens arrays [...] er blade i rekursions-tret og giver umiddelbare resultater.

Bemrk at koden bruger et par af de smarte muligheder som vi har gennemget tidligere:

• Metoden arr.reduce forklaret i kapitlet Array-metoder returnerer summen af et array.
• Lkken for(val of Object.values(obj)) itererer over et objekt og Object.values returnerer et array af dens vrdier.

Rekursive strukturer

En rekursiv (recursivt defineret) datastruktur er en struktur der replikerer sig selv i dele.

Vi har lige set det i eksemplet med en virksomhedsstruktur ovenfor.

En virksomheds afdeling er:

• Enten et array af medarbejdere.
• Eller et objekt med underafdelinger.

For webudviklere er der et meget mere velkendt eksempel: HTML og XML dokumenter.

I et HTML dokument kan et HTML-tag indeholde en liste af:

• Tekststykker.
• HTML-kommentarer.
• Andre HTML-tags (der i sig selv kan indeholde tekststykker/kommentarer eller andre tags etc).

Det er igen en rekursiv definition.

For bedre at forst dette vil vi gennemg en mere kompleks rekursiv struktur kaldet Linked list som kan vre en bedre alternativ til arrays i nogle tilflde.

Linked list

Forestil dig, vi vil gemme en ordnet liste af objekter.

Den naturlige valg er et array:

let arr = [obj1, obj2, obj3];

Men der er et problem med arrays. Operationerne slet element og indst element er dyre. For eksempel vil arr.unshift(obj) vre ndt til at renummerere alle elementer for at skabe plads for det nye element obj. Hvis det er et stort array, s tager det tid; det samme vil ske med arr.shift().

Den eneste modifikation der ikke krver masser af renummerering er de operationer der arbejder med slutningen af arrayet: arr.push/pop. S et array kan vre ret langsomt for store ker, nr vi skal arbejde med starten.

Alternativt, hvis vi virkelig har brug for hurtig indsttelse/sletning, kan vi vlge en anden datastruktur kaldet en linked list.

Et linked list element er rekursivt defineret som et objekt med:

• value vrdien af elementet.
• next en reference til det nste linked list element eller null hvis det er slutningen.

For eksempel er her en linked list med 4 elementer:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

Her er en grafisk reprsentation af listen:

[]

En alternativ kode for oprettelse af den samme linked list kunne vre:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

Her kan vi tydeligere se at der er flere objekter, hvor hvert objekt har value og next som peger p naboen. Variablen list er det frste objekt i kden, s ved at flge next-pegerne fra det kan vi n ethvert element.

Listen kan nemt opdeles i flere dele og senere genoprettes:

let secondList = list.next.next;
list.next.next = null;

[]

For at genoprette den oprindelige liste, skal vi bare forbinde den frste del med den anden:

list.next.next = secondList;

Og vi kan indstte eller fjerne elementer hvor som helst.

For eksempel, for at indstte et nyt element i starten af listen, skal vi opdatere hovedet af listen:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// indst et nyt element i starten af listen
list = { value: "new item", next: list };

[]

For at fjerne et element fra midten, ndre next af det forrige element:

list.next = list.next.next;

[]

Her fr vi list.next til at hoppe over 1 til vrdien 2. Vrdien 1 er nu fjernet fra kden. Hvis den ikke er gemt et andet sted, vil den automatisk blive fjernet fra hukommelsen.

I modstning til arrays sker der ingen massiv omnummerering, vi kan nemt rearrangere elementer.

Naturligvis er denne slags lister ikke altid bedre end arrays. Ellers ville alle bruge kun lister.

Den store ulempe er at vi ikke nemt kan tilg et element ved dets nummer. I et array er det nemt: arr[n] er en direkte reference. Men i listen skal vi starte fra det frste element og g next N gange for at n det Nte element.

Men vi har ikke altid brug for sdanne operationer. For eksempel, nr vi har brug for en k eller endda en deque den ordnede struktur der skal tillade meget hurtigt tilfjelse/fjernelse af elementer fra begge ender, men adgang til midten ikke er ndvendig.

Lister kan forbedres:

• Vi kan tilfje en egenskab prev i tilfjelse til next for at referere til det forrige element, s man nemt kan g baglns.
• Vi kan ogs tilfje en variabel kaldet tail som refererer til det sidste element i listen (og opdatere den nr man tilfjer/fjerner elementer fra slutningen).
• Datastrukturen kan justeres i forhold til specifikke behov.

Opsummering

Terms:

• Rekursion er et begreb i programmering der henviser til at en funktion kalder sig selv. Rekursive funktioner kan bruges til at lse opgaver p en elegant mde.

  Nr en funktion kalder sig selv, kaldes det et rekursions-trin. Basis for rekursion er funktionsargumenter, der gr opgaven s simpel, at funktionen ikke laver yderligere kald til sig selv.

• En recursivt defineret datastruktur er en datastruktur der kan defineres ved hjlp af sig selv.

  For eksempel kan en linked list defineres som en datastruktur bestende af et objekt der refererer til en liste (eller null).

  list = { value, next -> list }

  Trer (hierarkier) som HTML element-trer eller trer der viser afdelinger i en virksomhed er ogs rekursivt definerede. De har grene og hver gren kan have andre grene.

  Rekursive funktioner kan bruges til at gennemlbe dem, som vi har set i eksemplet med sumSalary.

Enhver rekursiv funktion kan omskrives til en iterativ funktion. Og det er nogle gange ndvendigt for at optimere ydeevnen. Men for mange opgaver er en rekursiv lsning hurtig nok og nemmere at skrive og vedligeholde.