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

het iteratief powgebruikt een enkele context dieienresultin het proces. De geheugenvereisten zijn klein, vast en hangen niet af van n.,

elke recursie kan herschreven worden als een lus. De lus variant kan in het algemeen effectiever worden gemaakt.

… maar soms is het herschrijven niet-triviaal, vooral wanneer de functie verschillende recursieve subcalls gebruikt afhankelijk van omstandigheden en hun resultaten samenvoegt of wanneer de vertakking complexer is. En de optimalisatie kan onnodig en totaal niet de moeite waard zijn.

recursie kan een kortere code geven, gemakkelijker te begrijpen en te ondersteunen. Optimalisaties zijn niet overal vereist, meestal hebben we een goede code nodig, daarom wordt deze gebruikt.,

recursieve traversals

een andere grote toepassing van de recursie is een recursieve traversal.

stel je voor, we hebben een bedrijf. De personeelsstructuur kan worden gepresenteerd als een object:

met andere woorden, een bedrijf heeft afdelingen.

• een dienst kan een personeelsbestand hebben. Zo heeft de afdeling sales 2 werknemers: John en Alice.

• of een afdeling kan worden opgesplitst in subonderdelen, zoals development heeft twee branches: sites en internals. Elk van hen heeft zijn eigen personeel.,

• Het is ook mogelijk dat wanneer een subafdeling groeit, het zich verdeelt in subsubdepartments (of teams).

  bijvoorbeeld, desites afdeling kan in de toekomst worden opgesplitst in teams voor siteA en siteB. En ze kunnen mogelijk nog meer splitsen. Dat staat niet op de foto, gewoon iets om in gedachten te hebben.

laten we nu zeggen dat we een functie willen om de som van alle salarissen te krijgen. Hoe kunnen we dat doen?

een iteratieve benadering is niet eenvoudig, omdat de structuur niet eenvoudig is., Het eerste idee kan zijn om eenfor loop te maken overcompany met geneste subloop over afdelingen op het 1e niveau. Maar dan hebben we meer geneste subloops nodig om over het personeel in afdelingen van het 2e niveau te itereren, zoals sites… en dan nog een subloop binnen die voor afdelingen van het 3e niveau die in de toekomst zouden kunnen verschijnen? Als we 3-4 geneste subloops in de code zetten om een enkel object te doorkruisen, wordt het nogal lelijk.

laten we recursie proberen.,

zoals we kunnen zien, zijn er twee mogelijke gevallen:

1. ofwel is het een” eenvoudige ” afdeling met een reeks mensen-dan kunnen we de salarissen optellen in een eenvoudige lus.
2. of het is een object met N subonderdelen – dan kunnen we N recursieve aanroepen maken om de som voor elk van de subdeps te krijgen en de resultaten te combineren.

het eerste geval is de basis van recursie, het triviale geval, wanneer we een array krijgen.

het tweede geval wanneer we een object krijgen is de recursieve stap., Een complexe taak wordt opgesplitst in subtaken voor kleinere afdelingen. Ze kunnen op hun beurt weer splitsen, maar vroeg of laat zal de splitsing eindigen op (1).

het algoritme is waarschijnlijk nog makkelijker te lezen uit de code:

de code is kort en gemakkelijk te begrijpen (hopelijk?). Dat is de kracht van recursie. Het werkt ook voor elk niveau van subdepartment nesting.,

Hier is het diagram van aanroepen:

merk op dat de code slimme functies gebruikt die we eerder hebben behandeld:

• method arr.reduce uitgelegd in het hoofdstuk array methods om de som van de array te krijgen.
• Loop for(val of Object.values(obj)) om over objectwaarden te herhalen: Object.values geeft een array van deze waarden terug.,

recursieve structuren

een recursieve (recursief gedefinieerde) gegevensstructuur is een structuur die zichzelf in delen repliceert.

we hebben het zojuist gezien in het voorbeeld van een bedrijfsstructuur hierboven.

een bedrijfsafdeling is:

• ofwel een array van mensen.
• of een object met afdelingen.

voor webontwikkelaars zijn er veel bekendere voorbeelden: HTML-en XML-documenten.

In het HTML-document kan een HTML-tag een lijst bevatten van:

• Tekststukken.
• HTML-opmerkingen.,
• andere HTML-tags (die op hun beurt tekststukken/opmerkingen of andere tags enz.kunnen bevatten).

dat is opnieuw een recursieve definitie.

voor een beter begrip, behandelen we nog een recursieve structuur met de naam “Linked list” die in sommige gevallen een beter alternatief voor arrays zou kunnen zijn.

Linked list

stel je voor, we willen een geordende lijst van objecten opslaan.

de natuurlijke keuze zou een array zijn:

let arr = ;

…maar er is een probleem met arrays., De” Delete element “en” insert element ” operaties zijn duur. Bijvoorbeeld, arr.unshift(obj) operatie moet alle elementen hernummeren om ruimte te maken voor een nieuwe obj, en als de array groot is, kost het tijd. Hetzelfde met arr.shift().

de enige structurele wijzigingen waarvoor geen massa-hernummering nodig is, zijn die welke werken met het einde van de array: arr.push/pop. Dus een array kan vrij traag zijn voor grote wachtrijen, wanneer we moeten werken met het begin.,

als we echt snel moeten invoegen/verwijderen, kunnen we ook een andere gegevensstructuur kiezen, een gelinkte lijst genaamd.

het gelinkte lijstelement is recursief gedefinieerd als een object met:

• value.
• next property referencing the next linked list element or null if that ‘ s the end.,

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., Delist variabele is het eerste object in de keten, dus nanext pointers kunnen we elk element bereiken.

De lijst kan gemakkelijk worden gesplitst in meerdere delen en later kwam terug:

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

om deel Te nemen:

list.next.next = secondList;

En we kunnen zeker invoegen of verwijderen van items in elke plaats.,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., De waarde 1 is nu uitgesloten van de keten. Als het nergens anders is opgeslagen, wordt het automatisch uit het geheugen verwijderd.

In tegenstelling tot arrays is er geen massa-hernummering, we kunnen eenvoudig elementen herschikken.

natuurlijk zijn lijsten niet altijd beter dan arrays. Anders zou iedereen alleen lijsten gebruiken.

het belangrijkste nadeel is dat we niet gemakkelijk toegang kunnen krijgen tot een element door zijn nummer. In een array die eenvoudig is: arr is een directe referentie., Maar in de lijst moeten we beginnen met het eerste item en gaan next N keer om het nde element te krijgen.

… maar we hebben dergelijke operaties niet altijd nodig. Bijvoorbeeld, wanneer we een wachtrij of zelfs een deque nodig hebben – de geordende structuur die het mogelijk moet maken zeer snel elementen aan beide uiteinden toe te voegen/te verwijderen, maar toegang tot het midden is niet nodig.

lijsten kunnen worden verbeterd:

• We kunnen eigenschap prev toevoegen naast next om te verwijzen naar het vorige element, om gemakkelijk terug te gaan.,
• We kunnen ook een variabele toevoegen met de naam tail die verwijst naar het laatste element van de lijst (en deze bijwerken bij het toevoegen/verwijderen van elementen aan het einde).
• …de gegevensstructuur kan variëren afhankelijk van onze behoeften.

samenvatting

termen:

• recursie is een programmeerterm die een functie vanuit zichzelf aanroept. Recursieve functies kunnen worden gebruikt om taken op elegante manieren op te lossen.

  wanneer een functie zichzelf aanroept, wordt dat een recursiestap genoemd., De basis van recursie is Functieargumenten die de taak zo eenvoudig maken dat de functie geen verdere oproepen doet.

• een recursief gedefinieerde gegevensstructuur is een gegevensstructuur die kan worden gedefinieerd met behulp van zichzelf.

  de gelinkte lijst kan bijvoorbeeld worden gedefinieerd als een gegevensstructuur die bestaat uit een object dat verwijst naar een lijst (Of null).

  list = { value, next -> list }

  bomen zoals HTML-elementen of de afdelingsstructuur uit dit hoofdstuk zijn ook van nature recursief: ze vertakken en elke tak kan andere takken hebben.,

  recursieve functies kunnen worden gebruikt om ze te lopen zoals we hebben gezien in het voorbeeld sumSalary.

  elke recursieve functie kan worden herschreven in een iteratieve functie. En dat is soms nodig om dingen te optimaliseren. Maar voor veel taken is een recursieve oplossing snel genoeg en gemakkelijker te schrijven en te ondersteunen.