lad os vende tilbage til funktioner og studere dem mere dybtgående.

vores første emne vil være rekursion.

Hvis du ikke er ny til programmering, er det sandsynligvis kendt, og du kan springe over dette kapitel.Recursion er et programmeringsmønster, der er nyttigt i situationer, hvor en opgave naturligt kan opdeles i flere opgaver af samme art, men enklere. Eller når en opgave kan forenkles til en nem handling plus en enklere variant af den samme opgave. Eller, som vi snart ser, at håndtere visse datastrukturer.,

når en funktion løser en opgave, kan den i processen kalde mange andre funktioner. Et delvist tilfælde af dette er, når en funktion kalder sig selv. Det kaldes rekursion.

To tankegange

For noget simpelt til at starte med – lad os skrive en funktion pow(x, n), der hæver x til en naturlig effekt af n. Med andre ord multiplicerer x i sig selv n gange.

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

Der er to måder at implementere det på.,

bemærk, hvordan den rekursive variant er fundamentalt anderledes.

Når pow(x, n) kaldes, udførelse deler sig i to grene:

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

1. Hvis n == 1, så alt er trivielle. Det kaldes rekursionsbasen, fordi det straks giver det indlysende resultat: pow(x, 1) er lig med x.
2. Andet, kan vi repræsentere pow(x, n) som x * pow(x, n - 1)., I matematik ville man skrive xn = x * xn-1. Dette kaldes en rekursiv trin: vi omdanne den opgave i en enklere handling (multiplikation med x) og en enklere opkald af samme opgave (pow med lavere n). Næste trin forenkler det yderligere Og videre, indtil n når 1.

Vi kan også sige, at pow rekursivt kalder sig selv til n == 1.,

For eksempel at beregne pow(2, 4) rekursive variant gør 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å, den rekursion reducerer en funktion for kald til en enklere, og så til endnu mere enkel, og så videre, indtil resultatet bliver indlysende.,

det maksimale antal indlejrede opkald (inklusive den første) kaldes rekursionsdybde. I vores tilfælde vil det være nøjagtigt n.

den maksimale rekursionsdybde er begrænset af JavaScript-motor. Vi kan stole på, at det er 10000, nogle motorer tillader mere, men 100000 er sandsynligvis uden for grænsen for de fleste af dem. Der er automatiske optimeringer, der hjælper med at afhjælpe dette (“tail calls optimi .ations”), men de understøttes endnu ikke overalt og fungerer kun i enkle tilfælde.

det begrænser anvendelsen af rekursion, men det er stadig meget bredt., Der er mange opgaver, hvor rekursiv tankegang giver enklere kode, lettere at vedligeholde.

eksekveringskonteksten og stakken

lad os nu undersøge, hvordan rekursive opkald fungerer. For at vi vil se under kølerhjelmen af funktioner.

oplysningerne om processen med udførelse af en kørende funktion gemmes i dens eksekveringskontekst.,

gennemførelsen sammenhæng er en intern datastruktur, der indeholder oplysninger om udførelse af en funktion: hvor kontrol flow er nu, den nuværende variable, hvis værdi this (vi bruger det ikke her) og få andre interne oplysninger.

et funktionsopkald har nøjagtigt en eksekveringskontekst forbundet med det.

når en funktion foretager et indlejret opkald, sker følgende:

• den aktuelle funktion er sat på pause.
• den eksekveringskontekst, der er forbundet med den, huskes i en speciel datastruktur kaldet e .ecution Conte .t stack.,
• det indlejrede opkald udføres.
• når den er afsluttet, hentes den gamle eksekveringskontekst fra stakken, og den ydre funktion genoptages, hvorfra den stoppede.

lad os se, hvad der sker under pow(2, 3) opkald.

pow(2, 3)

I begyndelsen af opkaldet pow(2, 3) gennemførelsen sammenhæng vil gemme variabler: x = 2, n = 3, udførelse flow er på linje 1 af funktion.,

Vi kan skitsere det som:

• kontekst: { 2: 2, n: 3, på linje 1 } Po. (2, 3)

det er når funktionen begynder at udføre., Betingelsen n == 1 er falsy, så strømmen fortsætter ind i 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) );

De variabler, er den samme, men den linje ændringer, så den kontekst er nu:

• Forbindelse: { x: 2, n: 3, på linje 5 } pow(2, 3)

for At beregne x * pow(x, n - 1), er vi nødt til at gøre en subcall af pow med nye argumenter pow(2, 2).,

Po. (2, 2)

for at foretage et indlejret opkald husker JavaScript den aktuelle eksekveringskontekst i eksekveringskontekststakken.

Her kalder vi den samme funktion pow, men det betyder absolut ikke noget. Processen er den samme for alle funktioner:

1. den aktuelle kontekst “huskes” oven på stakken.
2. den nye kontekst oprettes til underkaldet.
3. når subcall er færdig-den tidligere kontekst poppes fra stakken, og dens udførelse fortsætter.,

Her er den sammenhæng stack, når vi trådte ind i den subcall pow(2, 2):

• Forbindelse: { x: 2, n: 2, på linie 1 } pow(2, 2)
• Forbindelse: { x: 2, n: 3, på linje 5 } pow(2, 3)

De nye aktuelle udførelse sammenhæng er på toppen (og fed), og tidligere husket sammenhænge er nedenfor.

Når vi er færdige med subcall – er det let at genoptage den forrige kontekst, fordi den holder både variabler og det nøjagtige sted for koden, hvor den stoppede.,

pow(2, 1)

processen gentager: en ny subcall er lavet på linje 5, nu med argumenter x=2 n=1.,

En ny udførelse forbindelse er oprettet, den forrige er skubbet på toppen af stakken:

• Forbindelse: { x: 2, n: 1, på linie 1 } pow(2, 1)
• Forbindelse: { x: 2, n: 2, på linje 5 } pow(2, 2)
• Forbindelse: { x: 2, n: 3, i linje 5 } pow(2, 3)

Der er 2 gamle sammenhænge nu-og 1 øjeblikket kører for pow(2, 1).,

afslut

Under udførelsen af pow(2, 1), i modsætning til før, er det en betingelse n == 1 er truthy, så den første gren af if virker:

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

Der er ikke flere indlejrede opkald, så den funktion er færdig, vender tilbage 2.

Når funktionen er færdig, er dens eksekveringskontekst ikke længere nødvendig, så den fjernes fra hukommelsen., Den forrige er restaureret fra toppen af stakken:

• Forbindelse: { x: 2, n: 2, på linje 5 } pow(2, 2)
• Forbindelse: { x: 2, n: 3, på linje 5 } pow(2, 3)

Så den tidligere kontekst er blevet genoprettet:

• Forbindelse: { x: 2, n: 3, på linje 5 } pow(2, 3)

Når den er færdig, har vi et resultat af pow(2, 3) = 8.

rekursionsdybden i dette tilfælde var: 3.

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

Bemærk hukommelseskravene. Sammenhænge tager hukommelse., I vores tilfælde kræver hævning til kraften af n faktisk hukommelsen til n sammenhænge for alle lavere værdier af n.

En loop-baseret algoritme er mere hukommelse-besparelse:

function pow(x, n) { let result = 1; for (let i = 0; i < n; i++) { result *= x; } return result;}

Den iterative pow bruger en enkelt forbindelse skiftende i og result i processen. Dens hukommelseskrav er små, faste og afhænger ikke af n.,

enhver rekursion kan omskrives som en løkke. Loopvarianten kan normalt gøres mere effektiv.

…men nogle gange er omskrivningen ikke-triviel, især når funktionen bruger forskellige rekursive subcalls afhængigt af forholdene og fusionerer deres resultater, eller når forgreningen er mere indviklet. Og optimeringen kan være unødvendig og helt ikke værd at indsatsen.

rekursion kan give en kortere kode, lettere at forstå og støtte. Optimeringer er ikke påkrævet på alle steder, for det meste har vi brug for en god kode, derfor bruges den.,

rekursive traversals

en anden stor anvendelse af rekursionen er en rekursiv traversal.

Forestil dig, vi har et firma. Personalestrukturen kan præsenteres som et objekt:

med andre ord har et firma afdelinger.

• en afdeling kan have en række medarbejdere. For eksempel har sales afdelingen 2 ansatte: John og Alice.

• Eller en afdeling kan opdeles i subdepartments, f.eks. development har to grene: sites og internals. Hver af dem har deres eget personale.,

• det er også muligt, at når en underafdeling vokser, opdeles den i underafdeling (eller hold).

  For eksempel, sites afdelingen i fremtiden kan være opdelt i teams for siteA og siteB. Og de kan potentielt splitte endnu mere. Det er ikke på billedet, bare noget at have i tankerne.lad os nu sige, at vi ønsker en funktion for at få summen af alle lønninger. Hvordan kan vi gøre det?

  en iterativ tilgang er ikke let, fordi strukturen ikke er enkel., Den første idé kan være at lave en for loop over company med indlejrede subloop over 1. niveau-afdelinger. Men så har vi brug for flere indlejrede subloops for at gentage over personalet i afdelinger på 2. niveau som sites… og derefter en anden subloop inde i dem for afdelinger på 3. niveau, der muligvis vises i fremtiden? Hvis vi sætter 3-4 indlejrede subloops i koden for at krydse et enkelt objekt, bliver det ret grimt.

  lad os prøve rekursion.,

  som vi kan se, når vores funktion får en afdeling til at opsummere, er der to mulige tilfælde:

  1. enten er det en “simpel” afdeling med en række mennesker – så kan vi opsummere lønningerne i en simpel løkke.
  2. , Eller det er et objekt med N subdepartments – så kan vi lave N rekursive kald for at få den sum for hver af de subdeps og kombinere resultaterne.

  den 1. sag er bunden af rekursion, det trivielle tilfælde, når vi får et array.

  det 2.tilfælde, når vi får et objekt, er det rekursive trin., En kompleks opgave er opdelt i underopgaver for mindre afdelinger. De kan igen splitte igen, men før eller senere slutter splittelsen ved (1).

  algoritmen er sandsynligvis endnu lettere at læse fra koden:

  koden er kort og let at forstå (forhåbentlig?). Det er rekursionens kraft. Det virker også for ethvert niveau af underafdeling nesting.,

  Her er tegningen af opkald:

  

  Bemærk, at koden benytter smarte funktioner, som vi har dækket før:

  • Metode arr.reduce forklaret i kapitel Array metoder til at få summen af array.
  • Loop for(val of Object.values(obj)) for at gentage over objektværdier: Object.values returnerer en række af dem.,

  rekursive strukturer

  en rekursiv (rekursivt defineret) datastruktur er en struktur, der replikerer sig selv i dele.

  Vi har lige set det i eksemplet på en virksomhedsstruktur ovenfor.en virksomhedsafdeling er:

  • enten en række mennesker.
  • eller et objekt med afdelinger.

  for webebudviklere er der meget bedre kendte eksempler: HTML-og .ml-dokumenter.

  i HTML-dokumentet kan et HTML-tag indeholde en liste over:

  • tekststykker.
  • HTML-kommentarer.,
  • andre HTML-tags (som igen kan indeholde tekststykker/kommentarer eller andre tags osv.).

  det er igen en rekursiv definition.

  for bedre forståelse dækker vi en mere rekursiv struktur ved navn “Linked list”, som i nogle tilfælde kan være et bedre alternativ til arrays.

  Linked list

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

  Det naturlige valg ville være et array:

  let arr = ;

  …Men der er et problem med arrays., Operationerne” Slet element “og” indsæt element ” er dyre. For eksempel skal arr.unshift(obj) operation omdøbe alle elementer for at gøre plads til en ny obj, og hvis arrayet er stort, tager det tid. Samme med arr.shift().

  de eneste strukturelle ændringer, der ikke kræver masseomnummerering, er dem, der fungerer med slutningen af array: arr.push/pop. Så et array kan være ret langsomt for store køer, når vi skal arbejde med begyndelsen.,Alternativt, hvis vi virkelig har brug for hurtig indsættelse/sletning, kan vi vælge en anden datastruktur kaldet en linket liste.

  det linkede listeelement defineres rekursivt som et objekt med:

  • value.
  • next ejendom, der henviser til det næste linkede listeelement eller null hvis det er slutningen.,

  For instance:

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

  Graphical representation of the list:

  

  An alternative code for creation:

  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;

  Here we can even more clearly see that there are multiple objects, each one has the value and next pointing to the neighbour., Variablenlist er det første objekt i kæden, så efter next pointers fra det kan vi nå ethvert element.

  Den liste kan nemt deles op i flere dele og tilsluttede sig senere tilbage:

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

  

  for At deltage:

  list.next.next = secondList;

  Og sikkert at vi kan indsætte eller fjerne elementer i ethvert sted.,head of the list:

  

  To remove a value from the middle, change next of the previous one:

  list.next = list.next.next;

  

  We made list.next jump over 1 to value 2., Værdien 1 er nu udelukket fra kæden. Hvis det ikke er gemt andre steder, fjernes det automatisk fra hukommelsen.

  i modsætning til arrays er der ingen masse-omnummerering, vi kan nemt omarrangere elementer.

  lister er naturligvis ikke altid bedre end arrays. Ellers ville alle kun bruge lister.

  den største ulempe er, at vi ikke let kan få adgang til et element med dets nummer. I et array, der er let: arr er en direkte reference., Men på listen skal vi starte fra det første element og gå next N gange for at få det niende element.

  …men vi har ikke altid brug for sådanne operationer. For eksempel, når vi har brug for en kø eller endda en de .ue – den bestilte struktur, der skal tillade meget hurtig tilføjelse/fjernelse af elementer fra begge ender, men adgang til midten er ikke nødvendig.

  Lister kan blive styrket:

  • Vi kan tilføje ejendom prev udover next for at henvise til det forrige element, til at flytte tilbage nemt.,
  • Vi kan også tilføje en variabel med navnet tail henviser til det sidste element på listen (og opdaterer det, når du tilføjer / fjerner elementer fra slutningen).
  • …datastrukturen kan variere alt efter vores behov.

  Oversigt

  Vilkår:

  • Rekursion er et programmeringssprog begreb, der betyder, at kalde en funktion fra sig selv. Rekursive funktioner kan bruges til at løse opgaver på elegante måder.

    Når en funktion kalder sig selv, kaldes det et rekursionstrin., Grundlaget for rekursion er Funktionsargumenter, der gør opgaven så enkel, at funktionen ikke foretager yderligere opkald.

  • en rekursivt defineret datastruktur er en datastruktur, der kan defineres ved hjælp af sig selv.

    for eksempel kan den linkede liste defineres som en datastruktur, der består af et objekt, der refererer til en liste (eller null).

    list = { value, next -> list }

    Træer som HTML-elementer, træ eller afdelingen træ fra dette kapitel er naturligvis også rekursiv: de filial, og hver gren, kan have andre grene.,

    Rekursive funktioner kan bruges til at gå dem, som vi har set i sumSalary eksempel.

  enhver rekursiv funktion kan omskrives til en iterativ. Og det er nogle gange nødvendigt for at optimere ting. Men for mange opgaver er en rekursiv løsning hurtig nok og lettere at skrive og støtte.