La oss gå tilbake til funksjoner og studere dem mer i dybden.

Vår første emnet vil være recursion.

Hvis du er ikke nytt for programmering, så er det nok kjent, og du kan hoppe over dette kapittelet.

Recursion er en programmerer mønster som er nyttig i situasjoner når en oppgave kan være naturlig delt inn i flere oppgaver av samme type, men enklere. Eller når en oppgave kan forenkles til en enkelt handling pluss en enklere variant av samme oppgave. Eller, som vi vil se snart, for å håndtere visse data strukturer.,

Når en funksjon løser en oppgave, i den prosessen det kan ringe mange andre funksjoner. En delvis tilfellet av dette er når en funksjon kaller seg. Det kalles recursion.

To måter å tenke på

For noe enkelt til å begynne med – la oss skrive en funksjon pow(x, n) som øker x til en naturlig strøm av n. Med andre ord, multipliserer x av seg selv n ganger.

– >

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

Det er to måter å gjennomføre det.,

Vennligst legg merke til hvordan rekursiv variant er fundamentalt forskjellige.

Ved pow(x, n) er kalt, gjennomføring deler seg i to grener:

– >

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

– >

1. Hvis n == 1, så alt er trivielt. Det kalles base av recursion, fordi det umiddelbart produserer den åpenbare resultat: pow(x, 1) tilsvarer x.
2. hvis ikke, kan vi representere pow(x, n) som x * pow(x, n - 1)., I matematikk, ville man skrive xn = x * xn-1. Dette kalles en rekursiv trinn: vi transformere oppgaven til en enklere handling (multiplikasjon med x) og en enklere ringer av samme oppgave (pow med lavere n). Neste trinn forenkle det videre og videre helt til n kommer 1.

Vi kan også si at pow undermapper kaller seg selv til n == 1.,

For eksempel, for å beregne pow(2, 4) rekursive variant gjør du disse trinnene:

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 recursion reduserer en funksjon ringe til en enklere, og deretter – til enda mer enklere, og så videre, før resultatet blir åpenbare.,

Den maksimale antall nestede anrop (inkludert den første) er kalt recursion dybde. I vårt tilfelle, vil det være nøyaktig n.

Den maksimale recursion dybde er begrenset av JavaScript-motoren. Vi kan stole på at den blir 10000, noen motorer tillate mer, men 100000 er sannsynligvis ut av grensen for de fleste av dem. Det er automatisk optimaliseringer som hjelper lindre dette («halen samtaler optimaliseringer»), men de er ennå ikke støttes overalt og fungerer bare i enkle tilfeller.

Som begrenser anvendelsen av recursion, men det er fortsatt svært bredt., Det er mange oppgaver hvor rekursiv måte å tenke på gir enklere koden, enklere å vedlikeholde.

gjennomføring sammenheng og stable

la oss Nå undersøke hvordan rekursiv samtaler arbeid. For at vi vil ta en titt under panseret av funksjoner.

informasjon om prosessen med gjennomføring av en kjører funksjonen som er lagret i gjennomføringen sammenheng.,

gjennomføring sammenheng er en intern datastruktur som inneholder informasjon om gjennomføring av en funksjon: der kontroll flow, er nå den aktuelle variabler, verdien av this (vi bruker det ikke her) og noen andre interne detaljer.

En funksjon samtalen har nøyaktig ett gjennomføring sammenheng forbundet med det.

Når en funksjon som gjør en nestet samtale, skjer følgende:

• Den gjeldende funksjonen er satt på pause.
• gjennomføring sammenheng knyttet til den blir husket i en spesiell datastruktur kalt gjennomføring sammenheng stabelen.,
• Den nestede samtale utfører.
• Etter det ender, den gamle gjennomføring sammenheng er hentet fra bunken, og den ytre funksjonen fortsette fra der den stoppet.

La oss se hva som skjer under pow(2, 3) anrop.

pow(2, 3)

I begynnelsen av samtalen pow(2, 3) gjennomføring sammenheng vil lagre variabler: x = 2, n = 3 gjennomføring flyt er på linje 1 av-funksjonen.,

Vi kan tegne det slik:

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

Det er når funksjonen begynner å kjøre., Tilstanden n == 1 er falsy, så flyten fortsetter inn i den andre grenen av 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 endringer, slik sammenheng er nå:

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

for Å beregne x * pow(x, n - 1), må vi gjøre en subcall av pow med nye argumenter pow(2, 2).,

pow(2, 2)

for Å gjøre en nestet samtale, JavaScript husker dagens kjøring av konteksten i utøvelsen sammenheng stabelen.

Her har vi kalle samme funksjon pow, men det absolutt ikke noe å si. Prosessen er den samme for alle funksjoner:

1. Den aktuelle konteksten er «husket» på toppen av bunken.
2. Den nye konteksten er opprettet for subcall.
3. Når subcall er ferdig – den forrige konteksten er spratt fra bunken, og kjøringen fortsetter.,

Her er sammenheng bunken når vi kom inn i subcall pow(2, 2):

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

Den nye gjeldende gjennomføring kontekst er på topp (og fet), og tidligere husket sammenhenger er nedenfor.

Når vi er ferdig med den subcall – det er lett å gjenoppta tidligere sammenheng, fordi den holder både variabler og nøyaktig sted for koden der den stoppet.,

pow(2, 1)

prosessen gjentar: en ny subcall er gjort på linje 5, nå med argumenter x=2, n=1.,

En ny kjøring sammenheng er opprettet, vil den forrige er presset på toppen av stakken:

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

Det er 2 gamle sammenhenger nå og 1 kjører for pow(2, 1).,

avslutt

Under utførelsen av pow(2, 1), i motsetning til før, tilstanden n == 1 er truthy, så den første grenen av if fungerer:

– >

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

Det er ingen flere nestede samtaler, slik at funksjonen er ferdig, returnerer 2.

når funksjonen er ferdig, gjennomføring sammenheng er ikke nødvendig lenger, slik at det er fjernet fra minnet., Den forrige er restaurert av toppen av stakken:

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

Da den forrige konteksten er gjenopprettet:

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

Når den er ferdig, vi har en følge av pow(2, 3) = 8.

recursion dybde i dette tilfellet var: 3.

Som vi ser av eksemplene ovenfor, recursion dybden er lik det maksimale antall sammenheng i stabel.

Merk krav til minne. Sammenhenger tar minne., I vårt tilfelle, heve til kraften av n faktisk krever minne for n sammenhenger, for alle lavere verdier av n.

Et loop-basert algoritme er mer minne-lagring:

– >

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

iterativ pow bruker en enkel sammenheng endre i og result i prosessen. Minnet kravene er små, faste og ikke stole på n.,

Noen recursion kan bli omskrevet som en sløyfe. Loop-varianten vanligvis kan gjøres mer effektiv.

…Men noen ganger omskrive er ikke-trivielt, spesielt når funksjonen bruker forskjellige rekursiv subcalls avhengig av forholdene og integrerer sine resultater, eller når forgrening er mer intrikat. Og optimalisering kan være unødvendige og helt ikke verdt innsatsen.

Recursion kan gi en kortere kode, lettere å forstå og støtte. Optimaliseringer er ikke nødvendig i hvert enkelt sted, det meste vi trenger en god kode, som er hvorfor det er brukt.,

Rekursiv traversals

en Annen god anvendelse av recursion er en rekursiv traversal.

Tenk, vi har et selskap. De ansatte struktur kan presenteres som et objekt:

med andre ord, et selskap som har avdelinger.

• En avdeling kan ha en rekke ansatte. For eksempel sales avdeling har 2 ansatte: John og Alice.

• Eller en avdeling kan deles i subdepartments, som development har to grener: sites og internals. Hver av dem har sine egne ansatte.,

• Det er også mulig at når en subdepartment vokser, deler seg i subsubdepartments (eller lag).

  For eksempel, sites avdeling i fremtiden kan bli delt inn i grupper for siteA og siteB. Og de potensielt kan dele enda mer. Det er ikke på bildet, bare noe å ha i bakhodet.

la oss Nå si at vi vil ha en funksjon for å få summen av all lønn. Hvordan kan vi gjøre det?

En iterativ tilnærming er ikke lett, fordi strukturen er ikke enkelt., Den første idé kan være å lage en for loop over company med nestede subloop over 1. nivå avdelinger. Men da trenger vi flere nestede subloops å iterere over ansatte i 2. nivå avdelinger som sites… Og så en annen subloop i de for 3. nivå avdelinger som kan dukke opp i fremtiden? Hvis vi setter 3-4 nestede subloops i koden for å kjøre et enkelt objekt, det blir ganske stygg.

La oss prøve recursion.,

Som vi kan se, når du vår funksjon blir en avdeling for å oppsummere, det er to mulige scenarier:

1. Enten det er en «enkel» avdeling med en rekke personer – da kan vi summen av lønn i en enkel sløyfe.
2. Eller det er et motiv med N subdepartments – da kan vi få N rekursiv samtaler for å få summen for hver av de subdeps og kombinere resultatene.

1. tilfellet er i bunnen av recursion, det trivielle tilfelle, når vi får en matrise.

Den 2. tilfelle når vi får et objekt er den rekursive trinn., En kompleks oppgave er delt inn i deloppgavene for mindre avdelinger. De kan i sin tur delt igjen, men før eller senere splittet vil bli ferdig til (1).

algoritmen er sannsynligvis enda lettere å lese fra koden:

– koden er kort og lett å forstå (forhåpentligvis?). Det er kraften av recursion. Det fungerer også for alle nivå av subdepartment hekkende.,

Her er bildet av samtaler:

Merk at koden bruker smarte funksjoner som vi har dekket før:

• Metode arr.reduce forklart i kapittel Utvalg metoder for å få summen av tabellen.
• Loop for(val of Object.values(obj)) for å iterere over objektet verdier: Object.values returnerer en matrise av dem.,

Rekursive konstruksjoner

En rekursiv (med undermapper-definert) datastruktur er en struktur som reproduserer seg selv i deler.

Vi har bare sett det i et eksempel på et selskap struktur over.

En bedrift-avdelingen er:

• Enten en rekke mennesker.
• Eller et objekt med avdelinger.

For web-utviklere det er mye bedre kjente eksempler: HTML-og XML-dokumenter.

I HTML-dokumentet, en HTML-koden kan inneholde en liste over:

• Tekst stykker.
• HTML-kommentarer.,
• Andre HTML-koder (som i sin tur kan inneholde tekst stykker/kommentarer eller andre koder etc.).

Det er igjen en rekursiv definisjon.

For bedre forståelse, vi kommer tilbake med en mer rekursiv struktur som heter «Lenket liste» som kan være et bedre alternativ for matriser i noen tilfeller.

Lenket liste

Tenk, vi ønsker å lagre en ordnet liste av objekter.

Det naturlige valget ville være en matrise:

– >

let arr = ;

…Men det er et problem med matriser., Slett element» og «sett inn element» – operasjoner, er dyrt. For eksempel arr.unshift(obj) drift har til å endre skuffnummer alle elementer for å gjøre plass til en ny obj, og hvis matrisen er stor, det tar tid. Samme med arr.shift().

Den eneste strukturelle endringer som ikke krever masse-renumbering er de som driver med slutten av utvalg: arr.push/pop. Så en matrise kan være ganske treg for store køer, når vi har å jobbe med begynnelsen.,

Alternativt, hvis vi virkelig trenger rask innsetting/sletting, kan vi velge en annen datastruktur kalt en lenket liste.

lenket liste-element er undermapper definert som et objekt med:

• value.
• next eiendom referanse neste lenket liste-element eller null hvis dette er slutten.,

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., list variabel er det første objektet i kjeden, slik følgende next tips fra det vi kan nå ethvert element.

listen kan lett bli delt inn i flere deler og senere sluttet seg tilbake:

– >

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

for Å bli med:

– >

list.next.next = secondList;

Og sikkert vi kan sette inn 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., Verdien 1 er nå ekskludert fra kjeden. Hvis det ikke er lagret noe annet sted, vil den automatisk bli fjernet fra minnet.

i Motsetning til matriser, det er ikke masse-renumbering, kan vi enkelt omorganisere elementer.

Naturlig, lister er ikke alltid bedre enn matriser. Ellers alle ville bare bruke lister.

Den viktigste ulempen er at vi ikke kan enkelt få tilgang til et element av sitt antall. I en matrise som er enkel: arr er en direkte referanse., Men i den listen vi trenger å starte fra det første elementet og gå next N ganger for å få det n-te elementet.

…Men vi er ikke alltid nødvendig med slike operasjoner. For eksempel, når vi trenger en kø eller en deque – de bestilte struktur som må tillate svært rask med å legge til/fjerne elementer fra begge ender, men tilgang til sine midten er ikke nødvendig.

Lister kan være forbedret:

• kan Vi legge til eiendommen prev i tillegg til next referanse til forrige element, til å flytte tilbake lett.,
• kan Vi også legge inn en variabel som heter tail referere til det siste elementet på listen (og oppdatere den når du skal legge til/fjerne elementer fra slutten).
• …dataene struktur kan variere i henhold til våre behov.

Oppsummering

Vilkår:

• Recursion er et nyttig begrep som betyr å kalle en funksjon fra seg selv. Rekursive funksjoner kan brukes til å løse oppgaver i elegante måter.

  Når en funksjon kaller seg selv, som er kalt en recursion trinn., På grunnlag av recursion er funksjon argumenter som gjør oppgaven så enkel at den funksjonen ikke gjøre ytterligere samtaler.

• En undermapper-definert datastruktur er en datastruktur som kan defineres ved hjelp av seg selv.

  For eksempel, den lenkede listen kan bli definert som en datastruktur som består av et objekt refererer til en liste (eller null).

  – >

  list = { value, next -> list }

  Trær som HTML-elementer treet eller avdeling treet i dette kapitlet er også naturlig rekursive: de hver gren og gren kan ha andre grener.,

  Rekursive funksjoner kan brukes til å gange dem som vi har sett i sumSalary eksempel.

Noen rekursiv funksjon kan være skrevet inn i en iterativ en. Og det er noen ganger nødvendig for å optimalisere ting. Men for mange oppgaver på en rekursiv løsning som er rask nok og enklere å skrive og støtte.