låt oss återgå till funktioner och studera dem mer djupgående.

vårt första ämne kommer att vara rekursion.

om du inte är ny på programmering är det förmodligen bekant och du kan hoppa över det här kapitlet.

rekursion är ett programmeringsmönster som är användbart i situationer där en uppgift naturligt kan delas upp i flera uppgifter av samma slag, men enklare. Eller när en uppgift kan förenklas till en enkel åtgärd plus en enklare variant av samma uppgift. Eller, som vi ser snart, för att hantera vissa datastrukturer.,

När en funktion löser en uppgift kan den i processen kalla många andra funktioner. Ett partiellt fall av detta är när en funktion kallar sig själv. Det kallas rekursion.

två sätt att tänka

för något enkelt att börja med-låt oss skriva en funktion pow(x, n) som höjer x till en naturlig kraft på n. Med andra ord multiplicerar x I sig n gånger.

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

det finns två sätt att implementera det.,

Observera hur den rekursiva varianten är fundamentalt annorlunda.

Närpow(x, n) anropas delas utförandet upp i två grenar:

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

1. Omn == 1 är allt trivialt. Det kallas basen för rekursion, eftersom det omedelbart ger det uppenbara resultatet:pow(x, 1) motsvararx.
2. annars kan vi representera pow(x, n) som x * pow(x, n - 1)., I matematik skulle man skriva xn = x * xn-1. Detta kallas ett rekursivt steg: vi omvandlar uppgiften till en enklare åtgärd (multiplikation med x) och ett enklare samtal med samma uppgift (pow med lägre n). Nästa steg förenklar det längre och längre tills n når 1.

vi kan också säga attpow rekursivt kallar sig tilln == 1.,

till exempel, för att beräkna pow(2, 4) rekursiv variant gör dessa steg:

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 minskar en rekursiv variant av rekursiv variant.funktion ring till en enklare, och sedan – till ännu enklare, och så vidare tills resultatet blir uppenbart.,

det maximala antalet kapslade samtal (inklusive den första) kallas rekursionsdjup. I vårt fall kommer det att vara exakt n.

det maximala rekursionsdjupet är begränsat av JavaScript-motor. Vi kan lita på att det är 10000, vissa motorer tillåter mer, men 100000 är förmodligen Out of limit för majoriteten av dem. Det finns automatiska optimeringar som hjälper till att lindra detta (”tail calls optimizations”), men de stöds ännu inte överallt och fungerar bara i enkla fall.

det begränsar tillämpningen av rekursion, men det är fortfarande väldigt brett., Det finns många uppgifter där rekursivt sätt att tänka ger enklare kod, lättare att underhålla.

exekveringskontexten och stacken

låt oss nu undersöka hur rekursiva samtal fungerar. För att vi ska titta under huven av funktioner.

informationen om processen för utförande av en löpande funktion lagras i sitt exekverings sammanhang.,

exekveringskontexten är en intern datastruktur som innehåller detaljer om utförandet av en funktion: där kontrollflödet är nu, de aktuella variablerna, värdet på this (vi använder det inte här) och några andra interna detaljer.

ett funktionssamtal har exakt ett exekveringskontext associerat med det.

När en funktion gör ett kapslat samtal sker följande:

• den aktuella funktionen pausas.
• exekveringskontexten som är associerad med den kommer ihåg i en särskild datastruktur som kallas exekveringskontextstack.,
• det kapslade samtalet körs.
• efter det att det är slut hämtas det gamla exekveringskontexten från stapeln och den yttre funktionen återupptas från var den stoppades.

låt oss se vad som händer underpow(2, 3) – samtalet.

pow(2, 3)

i början av samtaletpow(2, 3) exekverings sammanhang kommer att lagra variabler:x = 2, n = 3, exekveringsflödet är på linje1 av funktionen.,

vi kan skissa det som:

• sammanhang: { x: 2, n: 3, på rad 1 } pow(2, 3)

det är då funktionen börjar exekvera., Villkoret n == 1 är falsy, så flödet fortsätter till den andra grenen av if:

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

variablerna är desamma, men raden ändras, men det är samma.så sammanhanget är nu:

• sammanhang: { x: 2, N: 3, på rad 5 } Pow(2, 3)

för att beräkna x * pow(x, n - 1), måste vi göra ett subcall av pow med nya argument pow(2, 2).,

pow(2, 2)

För att göra ett kapslat samtal kommer JavaScript ihåg det aktuella körningskontextet i körningskontextstacken.

här kallar vi samma funktion pow, men det spelar ingen roll. Processen är densamma för alla funktioner:

1. det aktuella sammanhanget är ”ihågkommen” ovanpå stapeln.
2. Det nya sammanhanget skapas för underkallet.
3. när subcall är klar – det tidigare sammanhanget poppas från stapeln, och dess utförande fortsätter.,

här är kontextstacken när vi gick in i subcall pow(2, 2):

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

det nya aktuella exekveringskontextet är överst (och fet), och tidigare ihågkommen sammanhang är nedan.

När vi avslutar subcall – det är lätt att återuppta föregående sammanhang, eftersom det håller både variabler och den exakta platsen för koden där den slutade.,

pow(2, 1)

processen upprepas: ett nytt subcall görs på rad5, nu med argumentx=2,n=1.,

en ny exekveringskontext skapas, den föregående trycks ovanpå stapeln:

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

det finns 2 gamla sammanhang nu och 1 körs förpow(2, 1).,

utgången

under utförandet avpow(2, 1), till skillnad från tidigare, villkoretn == 1 är sanningsenlig, så den första grenen avif fungerar:

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

det finns inga fler kapslade samtal, så funktionen är klar och returnerar 2.

När funktionen är klar behövs inte dess exekveringskontext längre, så den tas bort från minnet., Den föregående återställs från toppen av stapeln:

• sammanhang: { x: 2, n: 2, på rad 5 } pow(2, 2)
• sammanhang: { x: 2, n: 3, på rad 5 } pow(2, 3)

då återställs det föregående sammanhanget:

• sammanhang: { x: 2, n: 3, på rad 5 } pow(2, 3)

När den är klar har vi ett resultat av pow(2, 3) = 8.

rekursionsdjupet i detta fall var: 3.

som vi kan se från illustrationerna ovan är rekursionsdjupet lika med det maximala antalet sammanhang i stapeln.

notera minneskraven. Sammanhang tar minne., I vårt fall kräver höjning till kraften in faktiskt minnet förn sammanhang, för alla lägre värden pån.

en loop-baserad algoritm är mer minnessparande:

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

den iterativapow använder ett enda sammanhang som ändrari ochresult I process. Dess minneskrav är små, fasta och beror inte på n.,

eventuell rekursion kan skrivas om som en slinga. Slingvarianten kan vanligtvis göras effektivare.

…men ibland är omskrivningen icke-trivial, speciellt när funktionen använder olika rekursiva subkaller beroende på förhållanden och sammanfogar deras resultat eller när förgreningen är mer invecklad. Och optimeringen kan vara onödiga och helt inte värt ansträngningarna.

rekursion kan ge en kortare kod, lättare att förstå och stödja. Optimeringar krävs inte på alla ställen, för det mesta behöver vi en bra kod, det är därför det används.,

rekursiva traversaler

en annan bra tillämpning av rekursionen är en rekursiv traversal.

Tänk dig att vi har ett företag. Personalstrukturen kan presenteras som ett objekt:

med andra ord har ett företag avdelningar.

• en avdelning kan ha en uppsättning personal. Till exempel harsales avdelningen 2 anställda: John och Alice.

• eller en avdelning kan delas upp i delområden, somdevelopment har två grenar:sites ochinternals. Varje av dem har sin egen personal.,

• det är också möjligt att när en underavdelning växer delas den upp i underavdelningar (eller lag).

  till exempel kan avdelningensites i framtiden delas upp i lag för siteA och siteB. Och de kan eventuellt dela ännu mer. Det är inte på bilden, bara något att tänka på.

låt oss nu säga att vi vill ha en funktion för att få summan av alla löner. Hur kan vi göra det?

ett iterativt tillvägagångssätt är inte lätt, eftersom strukturen inte är enkel., Den första tanken kan vara att göra enfor slinga övercompany med kapslade delsummor över 1: A nivåavdelningar. Men då behöver vi fler kapslade subloops för att iterera över personalen i 2: a nivåavdelningar som sites … och sedan ett annat subloop inuti de för 3: e nivåavdelningar som kan dyka upp i framtiden? Om vi lägger 3-4 kapslade subloops i koden för att korsa ett enda objekt blir det ganska fult.

låt oss försöka rekursion.,

som vi kan se, när vår funktion får en avdelning att summera, finns det två möjliga fall:

1. antingen är det en ”enkel” avdelning med en rad människor – då kan vi summera lönerna i en enkel slinga.
2. eller det är ett objekt medN delområden – då kan vi göraN rekursiva samtal för att få summan för varje delsteg och kombinera resultaten.

det första fallet är basen för rekursion, det triviala fallet, när vi får en array.

det andra fallet när vi får ett objekt är det rekursiva steget., En komplex uppgift är uppdelad i deluppgifter för mindre avdelningar. De kan i sin tur delas igen, men förr eller senare kommer splittringen att sluta vid (1).

algoritmen är förmodligen ännu enklare att läsa från koden:

koden är kort och lätt att förstå (förhoppningsvis?). Det är kraften i rekursion. Det fungerar också för alla nivåer av avdelning häckning.,

här är diagrammet över samtal:

Observera att koden använder smarta funktioner som vi har använt täckt innan:

• metod arr.reduce förklaras i kapitlet array metoder för att få summan av matrisen.
• Loopfor(val of Object.values(obj)) för att iterera över objektvärden:Object.values returnerar en rad av dem.,

rekursiva strukturer

en rekursiv (rekursivt definierad) datastruktur är en struktur som replikerar sig i delar.

Vi har just sett det i exemplet på en företagsstruktur ovan.

en företagsavdelning är:

• antingen en rad människor.
• eller ett objekt med avdelningar.

för webbutvecklare finns det mycket bättre kända exempel: HTML och XML-dokument.

i HTML-dokumentet kan en HTML-tagg innehålla en lista över:

• textstycken.
• HTML-kommentarer.,
• andra HTML-taggar (som i sin tur kan innehålla textstycken/kommentarer eller andra taggar etc).

det är återigen en rekursiv definition.

för bättre förståelse täcker vi ytterligare en rekursiv struktur med namnet ”länkad lista” som kan vara ett bättre alternativ för matriser i vissa fall.

länkad lista

Tänk dig att vi vill lagra en beställd lista över objekt.

det naturliga valet skulle vara en array:

let arr = ;

…men det finns ett problem med arrayer., Operationerna” ta bort element ”och” infoga element ” är dyra. Till exempel måstearr.unshift(obj) – åtgärden numrera om alla element för att skapa plats för en nyobj, och om matrisen är stor tar det tid. Samma med arr.shift().

de enda strukturella modifieringar som inte kräver massomnumrering är de som fungerar med slutet av arrayen: arr.push/pop. Så en matris kan vara ganska långsam för stora köer, när vi måste arbeta med början.,

alternativt, om vi verkligen behöver snabb infogning / radering, kan vi välja en annan datastruktur som kallas en länkad lista.

det länkade listelementet definieras rekursivt som ett objekt med:

• value.
• next egenskapen refererar till nästa länkade listelement ellernull om det är slutet.,

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., Variabelnlist är det första objektet i kedjan, så efter next pekare från det kan vi nå alla element.

listan kan enkelt delas upp i flera delar och senare gick tillbaka:

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

för att gå med:

list.next.next = secondList;

och säkert kan vi infoga eller ta bort objekt på vilken plats som helst.,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ärdet 1 är nu uteslutet från kedjan. Om den inte lagras någon annanstans kommer den automatiskt att tas bort från minnet.

Till skillnad från arrays finns det ingen massomnumrering, vi kan enkelt omorganisera element.

naturligtvis är listor inte alltid bättre än arrays. Annars skulle alla bara använda listor.

den största nackdelen är att vi inte enkelt kan komma åt ett element med sitt nummer. I en array som är enkel: arr är en direkt referens., Men i listan måste vi börja från det första objektet och gå next N gånger för att få nth-elementet.

…men vi behöver inte alltid sådana operationer. Till exempel, när vi behöver en kö eller till och med en deque – den beställda strukturen som måste tillåta mycket snabb att lägga till/ta bort element från båda ändarna, men tillgång till mitten behövs inte.

listor kan förbättras:

• vi kan lägga till egendomprev förutomnext för att referera till föregående element, för att enkelt flytta tillbaka.,
• vi kan också lägga till en variabel som hetertail referera till det sista elementet i listan (och uppdatera det när du lägger till / tar bort element från slutet).
• …datastrukturen kan variera beroende på våra behov.

sammanfattning

villkor:

• rekursion är en programmeringsperiod som innebär att man ringer en funktion från sig själv. Rekursiva funktioner kan användas för att lösa uppgifter på eleganta sätt.

  När en funktion anropar sig kallas det ett rekursionssteg., Grunden för rekursion är Funktionsargument som gör uppgiften så enkel att funktionen inte gör ytterligare samtal.

• en rekursivt definierad datastruktur är en datastruktur som kan definieras med hjälp av sig själv.

  den länkade listan kan till exempel definieras som en datastruktur som består av ett objekt som refererar till en lista (eller null).

  list = { value, next -> list }

  träd som HTML elements tree eller department tree från detta kapitel är också naturligt rekursiva: de grenar och varje gren kan ha andra grenar.,

  rekursiva funktioner kan användas för att gå dem som vi har sett i exempletsumSalary.

rekursiv funktion kan skrivas om till en iterativ. Och det krävs ibland för att optimera saker. Men för många uppgifter är en rekursiv lösning snabb nog och lättare att skriva och stödja.