palataan toimintoja ja tutkia niitä syvällisemmin.

ensimmäinen aiheemme on rekursio.

Jos et ole Uusi ohjelmoinnissa, niin se on todennäköisesti tuttu ja voit jättää tämän luvun väliin.

Rekursio on ohjelmoinnin malli, joka on hyödyllinen tilanteissa, kun tehtävä voidaan luonnollisesti jakaa useita tehtäviä samanlaista, mutta yksinkertaisempi. Tai kun tehtävä voidaan yksinkertaistaa helpoksi toiminnaksi sekä yksinkertaisemmaksi muunnokseksi samasta tehtävästä. Tai kuten pian näemme, käsitellä tiettyjä tietorakenteita.,

kun funktio ratkaisee tehtävän, prosessissa se voi kutsua monia muita funktioita. Osittainen tapaus tästä on, kun funktio kutsuu itseään. Sitä kutsutaan rekursioksi.

Kaksi tapaa ajatella

jotain yksinkertaista aloittaa – katsotaanpa kirjoita funktio pow(x, n) nostaa x luonnollinen voima n. Toisin sanoen, kertoo x itsestään n kertaa.

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

On olemassa kaksi tapaa toteuttaa se.,

huomaa, miten rekursiivinen muunnos on olennaisesti erilainen.

Kun pow(x, n) kutsutaan, toteutus jakautuu kahteen osaan:

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

1. Jos n == 1, niin kaikki on triviaali. Se on nimeltään pohjan rekursio, koska se välittömästi tuottaa ilmeinen tulos: pow(x, 1) vastaa x.
2. Muuten, voimme edustaa pow(x, n) kuten x * pow(x, n - 1)., Matematiikassa kirjoitettaisiin xn = x * xn-1. Tätä kutsutaan rekursiivinen askel: me muuttaa tehtävän yksinkertaisempi toiminta (kertomalla x) ja yksinkertaisempaa soittaa saman tehtävän (pow pienempi n). Seuraavat vaiheet yksinkertaistaa sitä edelleen ja edelleen, kunnes n saavuttaa 1.

– Voimme myös sanoa, että pow kutsuu itseään rekursiivisesti, kunnes n == 1.,

esimerkiksi laskea pow(2, 4) rekursiivinen versiossa ei näitä ohjeita:

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

Joten, myös rekursio vähentää toiminto soittaa yksinkertaisempi, ja sitten – vielä enemmän yksinkertaisempi, ja niin edelleen, kunnes tulos on ilmeinen.,

sisäkkäisten puhelujen maksimimäärää (mukaan lukien ensimmäinen) kutsutaan rekursiosyvyydeksi. Meidän tapauksessamme se on täsmälleen n.

maksimaalista rekursiosyvyyttä rajoittaa JavaScript engine. Voimme luottaa, että se on 10000, jotkut moottorit sallia enemmän, mutta 100000 on luultavasti pois raja suurin osa niistä. On automaattisia optimointeja, jotka auttavat lievittämään tätä (”tail calls optimizations”), mutta niitä ei vielä tueta kaikkialla ja ne toimivat vain yksinkertaisissa tapauksissa.

se rajoittaa rekursion soveltamista, mutta on edelleen hyvin laaja., On monia tehtäviä, joissa rekursiivinen ajattelutapa antaa yksinkertaisempaa koodia, helpompi ylläpitää.

teloituskonteksti ja pino

nyt tutkitaan, miten rekursiiviset puhelut toimivat. Sitä varten katsomme toimintojen konepellin alle.

tiedot juoksevan toiminnon suoritusprosessista tallennetaan sen suorituskontekstiin.,

suorittamisen yhteydessä on sisäinen tietorakenne, joka sisältää tietoja suoritus-toiminto: jos virtausta on nyt, nykyinen muuttujan arvo this (emme käytä sitä täällä) ja muutamia muita sisäisiä yksityiskohtia.

yhdellä funktiokutsulla on täsmälleen yksi siihen liittyvä suoritusyhteys.

kun funktio tekee sisäkkäisen puhelun, tapahtuu seuraavaa:

• nykyinen funktio keskeytetään.
• toteutuksen yhteydessä liittyy se muistetaan erityinen tietorakenne kutsutaan suorittamisen yhteydessä pino.,
• the nested call executes.
• sen päätyttyä vanha suorituskonteksti haetaan pinosta, ja ulompi funktio jatketaan siitä, mistä se pysähtyi.

katsotaan, mitä tapahtuu aikana pow(2, 3) puhelu.

pow(2, 3)

puhelun alusta pow(2, 3) suorittamisen yhteydessä tallentaa muuttujat: x = 2, n = 3, toteutus virtaus on line 1 toiminto.,

Emme voi luonnos se kuten:

• Konteksti: { x: 2, n: 3, linja 1 } pow(2, 3)

Se on kun toiminto alkaa suorittaa., Kunto n == 1 on falsy, joten virtaus jatkuu toinen haara if:

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

muuttujat ovat samat, mutta linja muuttuu, niin asiayhteys on nyt:

• Konteksti: { x: 2, n: 3, rivillä 5 } pow(2, 3)

laskea x * pow(x, n - 1) meidän täytyy tehdä subcall on pow uusia perusteluja pow(2, 2).,

pow(2, 2)

tehdä sisäkkäisiä soittaa, JavaScript muistaa nykyisen suorituksen yhteydessä suorituksen yhteydessä pino.

täällä kutsumme samaa funktiota pow, mutta sillä ei ole mitään väliä. Prosessi on sama kaikille toimintoja:

1. nykytilanne on ”muisti” päälle pinon.
2. Uusi konteksti luodaan alakallille.
3. kun alakerta on valmis – edellinen konteksti poksahtaa pinosta, ja sen toteutus jatkuu.,

Tässä yhteydessä pino kun astuimme subcall pow(2, 2):

• Konteksti: { x: 2, n: 2, rivi 1 } pow(2, 2)
• Konteksti: { x: 2, n: 3, rivillä 5 } pow(2, 3)

uusi nykyinen suorittamisen yhteydessä on päällä (ja rohkea), ja edellinen muistetaan yhteyksissä ovat alla.

kun lopetamme subcallin – on helppo jatkaa edellistä kontekstia, koska se pitää sekä muuttujat että koodin tarkan paikan, jossa se pysähtyi.,

pow(2, 1)

prosessi toistuu: uusi subcall on tehty rivi 5, nyt perustelut x=2, n=1.,

uusi suorittamisen yhteydessä on luotu, edellinen työnnetään pinoon:

• Konteksti: { x: 2, n: 1, rivi 1 } pow(2, 1)
• Konteksti: { x: 2, n: 2, linja 5 } pow(2, 2)
• Konteksti: { x: 2, n: 3, rivillä 5 } pow(2, 3)

On 2 vanha yhteyksissä nyt ja 1 tällä hetkellä käynnissä pow(2, 1).,

poistua

suorituksen Aikana pow(2, 1) toisin kuin ennen, kunto n == 1 on truthy, joten ensimmäinen haara if toimii:

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

enää ei ole sisäkkäisiä puhelut, joten toiminto on valmis, palaa 2.

funktion päättyessä sen suoritusyhteyttä ei enää tarvita, joten se poistetaan muistista., Edellinen on palautettu päältä pino:

• Konteksti: { x: 2, n: 2, linja 5 } pow(2, 2)
• Konteksti: { x: 2, n: 3, rivillä 5 } pow(2, 3)

Sitten edellisen yhteydessä on kunnostettu:

• Konteksti: { x: 2, n: 3, rivillä 5 } pow(2, 3)

Kun se on valmis, meillä on tulos pow(2, 3) = 8.

rekursion syvyys tässä tapauksessa oli: 3.

kuten yllä olevista havainnekuvista näkyy, rekursion syvyys vastaa pinossa olevan asiayhteyden maksimimäärää.

huomaa muistivaatimukset. Kontekstit vievät muistia., Meidän tapauksessamme, nostaa valtaan n oikeastaan vaatii muistia n yhteyksissä, sillä kaikki pienemmät arvot n.

silmukka-pohjainen algoritmi on enemmän muistia säästävä:

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

iteratiivinen pow käyttää yhden yhteydessä muuttuvat i ja result prosessissa. Sen muistivaatimukset ovat pieniä, kiinteitä eivätkä riipu n.,

mikä tahansa rekursio voidaan kirjoittaa uudelleen silmukaksi. Silmukan muunnos voidaan yleensä tehdä tehokkaammaksi.

…Mutta joskus uudelleenkirjoitus on ei-triviaali, varsinkin kun toiminto käyttää eri rekursiivinen subcalls olosuhteista riippuen ja yhdistää niiden tulokset tai kun aluevaltaus on enemmän monimutkainen. Ja optimointi voi olla tarpeetonta ja täysin ei kannata ponnisteluja.

rekursio voi antaa lyhyemmän koodin, helpompi ymmärtää ja tukea. Optimointeja ei tarvita Joka paikassa, useimmiten tarvitsemme hyvän koodin, siksi sitä käytetään.,

rekursiiviset traversiot

rekursion toinen suuri sovellus on rekursiivinen traversio.

Imagine, we have a company. Henkilöstörakenne voidaan esittää objektina:

eli yrityksellä on osastoja.

• osastossa voi olla joukko henkilökuntaa. Esimerkiksi sales osasto on 2 työntekijää: John ja Alice.

• Tai osasto voi jakaa subdepartments, kuten development on kaksi haaraa: sites ja internals. Jokaisella heistä on oma henkilökuntansa.,

• Se on myös mahdollista, että kun päälliköksi kasvaa, se jakautuu subsubdepartments (tai joukkuetta).

  esimerkiksi sites osasto tulevaisuudessa voi olla jaettu joukkueet siteA ja siteB. Ja ne voivat mahdollisesti hajaantua vielä enemmän. Se ei näy kuvassa, vaan mielessä.

nyt sanotaan, että haluamme funktion, jolla saadaan kaikkien palkkojen summa. Miten voimme tehdä sen?

iteratiivinen lähestymistapa ei ole helppo, koska rakenne ei ole yksinkertainen., Ensimmäinen ajatus voi olla tehdä for silmukan yli company sisäkkäisiä subloop yli 1-taso yksiköt. Mutta sitten me tarvitsemme enemmän sisäkkäisiä subloops kerrata henkilöstön 2. tason yksiköiden, kuten sites… Ja sitten toinen subloop sisällä nämä 3 tason yksiköt, jotka saattavat näkyä tulevaisuudessa? Jos laitamme koodiin 3-4 sisäkkäistä sublooppia yhden kohteen läpiajamiseksi, siitä tulee melko ruma.

kokeillaan rekursiota.,

Kuten näemme, kun funktio saa osasto summa, on olemassa kaksi mahdollista tapausta:

1. Joko se on ”yksinkertainen” – osasto, jossa joukko ihmisiä – sitten voimme summa palkat yksinkertainen silmukka.
2. Tai se on esine, jossa N subdepartments – sitten voimme tehdä N rekursiokutsua saada summa kunkin subdeps ja yhdistää tulokset.

1.tapaus on rekursion pohja, triviaali tapaus, kun saamme array.

toinen tapaus, kun saamme objektin, on rekursiivinen vaihe., Monimutkainen tehtävä jaetaan pienempien osastojen välisummiin. Ne voivat puolestaan jakaa uudelleen, mutta ennemmin tai myöhemmin jako päättyy (1).

algoritmi on todennäköisesti jopa helpompaa lukea koodi:

koodi on lyhyt ja helppo ymmärtää (toivottavasti?). Se on rekursion voima. Se toimii myös minkä tahansa tasoisen aliperämäisen pesinnän osalta.,

Tässä on kaavio puhelut:

Huomaa, että koodi käyttää älykkäitä ominaisuuksia, jotka olemme katettu ennen:

• Tapa arr.reduce selitetty luvussa Array menetelmiä saada summa array.
• Loop for(val of Object.values(obj)) kerrata kohde arvot: Object.values palauttaa joukko niitä.,

Rekursiiviset rakenteet

rekursiivinen (rekursiivisesti määritelty) tietojen rakenne on rakenne, joka kopioi itsensä osiin.

olemme juuri nähneet sen yllä olevassa yritysrakenteen esimerkissä.

yritys osasto on:

• Joko joukko ihmisiä.
• tai objekti osastoineen.

web-kehittäjille on paljon paremmin tunnettuja esimerkkejä: HTML-ja XML-dokumentteja.

HTML-dokumentissa HTML-tag voi sisältää luettelon:

• Tekstikappaleista.
• HTML-Kommentit.,
• muut HTML-tunnisteet (jotka puolestaan voivat sisältää tekstikappaleita / kommentteja tai muita tageja jne.).

se on jälleen rekursiivinen määritelmä.

paremman ymmärryksen vuoksi käsittelemme vielä yhden rekursiivisen rakenteen nimeltä ”linkitetty lista”, joka voisi olla joissakin tapauksissa parempi vaihtoehto matriiseille.

linkitetty lista

kuvitella, haluamme tallentaa tilatun listan esineitä.

luonnollinen valinta olisi array:

let arr = ;

– Mutta siellä on ongelma taulukot., ”Delete element” ja ”insert element” – toiminnot ovat kalliita. Esimerkiksi arr.unshift(obj) toiminta on numeroida kaikki elementtejä, jotta tilaa uudelle obj, ja jos matriisi on suuri, se vie aikaa. Sama arr.shift().

ainoa rakenteellisia muutoksia, jotka eivät vaadi massa-numerointia ovat ne, jotka toimivat loppuun array: arr.push/pop. Jono voi siis olla aika hidas isoille jonoille, kun pitää tehdä töitä alun kanssa.,

Vaihtoehtoisesti, jos me todella tarvitsemme nopeasti lisäys/poisto, voimme valita toinen tietorakenne kutsutaan linkitetty lista.

linkitetty lista elementti on rekursiivisesti määritelty objekti:

• value.
• next omaisuuden löytymistä seuraavana linkitetty lista-elementti tai null jos se on lopussa.,

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 muuttuja on ensimmäinen kohde ketjussa, joten seuraavat next viitteitä siitä voimme saavuttaa minkä tahansa elementin.

luettelo voidaan helposti jakaa useisiin osiin ja liittyi myöhemmin takaisin:

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

liittyä:

list.next.next = secondList;

Ja voimme varmasti lisätä tai poistaa kohteita tahansa paikkaan.,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., Arvo 1 jää nyt ketjun ulkopuolelle. Jos sitä ei tallenneta muualle, se poistetaan automaattisesti muistista.

toisin kuin matriisit, ei ole massa-numerointia, voimme helposti järjestää elementtejä uudelleen.

luonnollisesti listat eivät ole aina parempia kuin matriisit. Muuten kaikki käyttäisivät vain listoja.

suurin haittapuoli on, että emme pääse helposti käsiksi elementtiin sen numeron perusteella. Array se on helppoa: arr on suora viittaus., Mutta luettelosta meidän täytyy aloittaa ensimmäinen kohde ja mennä next N kertaa saada Nnen elementin.

…mutta emme aina tarvitse tällaisia operaatioita. Esimerkiksi, kun tarvitsemme jonon tai jopa deque-tilatun rakenteen, jonka on mahdollistettava erittäin nopea lisääminen/poistaminen elementtejä molemmista päistä, mutta pääsy sen keskelle ei tarvita.

Listoja voi olla parannettu:

• Voimme lisätä omaisuutta prev lisäksi next viittaus edellisen osan, siirtyä takaisin helposti.,
• Voimme myös lisätä muuttuja nimeltä tail löytymistä viimeinen osa luettelon (ja päivittää sitä milloin lisäämällä/poistamalla elementtejä lopusta).
• … tietorakenne voi vaihdella tarpeidemme mukaan.

Tiivistelmä

Käyttö:

• Rekursio on ohjelmointi termi, joka tarkoittaa soittamalla toiminto itse. Rekursiivisilla funktioilla voidaan ratkaista tehtäviä eleganteilla tavoilla.

  Kun funktio kutsuu itseään, sitä kutsutaan rekursio vaihe., Rekursion perusteena ovat funktioargumentit, jotka tekevät tehtävästä niin yksinkertaisen, ettei funktio tee jatkokutsuja.

• rekursiivisesti määritelty tietorakenne on tietorakenne, joka voidaan määritellä itse.

  esimerkiksi linkitetty lista voidaan määritellä tietojen rakenne, joka koostuu kohteen löytymistä listan (tai null).

  list = { value, next -> list }

  Puut, kuten HTML-elementit puu-tai osasto-puu tässä luvussa on myös luonnollisesti rekursiivinen: he haaraa ja jokainen haara voi olla muita oksia.,

  rekursiivisten funktioiden avulla niitä voi kävellä kutensumSalary – esimerkissä on nähty.

Kaikki rekursiivinen funktio voidaan kirjoittaa osaksi iteratiivinen. Ja se on joskus tarpeen optimoida asioita. Mutta monissa tehtävissä rekursiivinen ratkaisu on riittävän nopea ja helpompi kirjoittaa ja tukea.