térjünk vissza a függvényekhez, és tanulmányozzuk azokat mélyebben.

első témánk a rekurzió lesz.

ha nem vagy új a programozásban, akkor valószínűleg ismerős, és kihagyhatod ezt a fejezetet.

a rekurzió olyan programozási minta, amely hasznos olyan helyzetekben,amikor egy feladat természetesen több azonos típusú, de egyszerűbb feladatra osztható. Vagy ha egy feladat egyszerűsíthető egy egyszerű műveletre, valamint ugyanazon feladat egyszerűbb változatára. Vagy, Amint hamarosan látni fogjuk, bizonyos adatstruktúrákkal foglalkozni.,

amikor egy függvény megoldja a feladatot, a folyamat során sok más funkciót is hívhat. Ennek részleges esete az, amikor egy függvény felhívja magát. Ezt rekurziónak hívják.

két gondolkodásmód

valami egyszerű kezdéshez-írjunk egy függvényt pow(x, n) ez felveti a xa n természetes erejét. Más szóval, a x önmagában szorzata n alkalommal.

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

két módja van annak végrehajtására.,

Felhívjuk figyelmét, hogy a rekurzív változat alapvetően különbözik.

amikor pow(x, n) hívják, a végrehajtás két ágra oszlik:

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

1. Ha n == 1, akkor minden triviális. Ezt a rekurzió alapjának nevezik, mert azonnal létrehozza a nyilvánvaló eredményt: pow(x, 1) egyenlő x.
2. ellenkező esetben a pow(x, n) as x * pow(x, n - 1)., Matematikából xn = x * xn-1írható. Ezt rekurzív lépésnek nevezzük: a feladatot egyszerűbb műveletekké alakítjuk át (szorzás x) és egy egyszerűbb feladathívás (powalacsonyabb n). A következő lépések tovább egyszerűsítik, amíg nel nem éri a 1 értéket.

azt is mondhatjuk, hogy pow rekurzívan hívja magát, amíg n == 1.,

például kiszámításához pow(2, 4) a rekurzív változat ezeket a lépéseket:

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

Szóval, a rekurzió csökkenti egy függvényhívás egy egyszerűbb, majd – még ennél is egyszerűbb, mindaddig, míg az eredmény nyilvánvaló.,

a beágyazott hívások maximális számát (beleértve az elsőt is) rekurziós mélységnek nevezzük. Esetünkben pontosan nlesz.

a maximális rekurziós mélységet a JavaScript motor korlátozza. Támaszkodhatunk rá, hogy 10000, egyes motorok többet engednek meg, de az 100000 valószínűleg meghaladja a többségüket. Vannak olyan automatikus optimalizálások, amelyek segítenek enyhíteni ezt (“tail calls optimizations”), de még nem mindenhol támogatják őket, csak egyszerű esetekben működnek.

Ez korlátozza a rekurzió alkalmazását,de még mindig nagyon széles., Sok olyan feladat van, ahol a rekurzív gondolkodásmód egyszerűbb kódot ad, könnyebben karbantartható.

A végrehajtási kontextus és a verem

most vizsgáljuk meg, hogyan működnek a rekurzív hívások. Ehhez megnézzük a funkciók motorháztetőjét.

a futó funkció végrehajtásának folyamatára vonatkozó információk a végrehajtási kontextusban kerülnek tárolásra.,

a végrehajtási környezet egy belső adatstruktúra, amely egy függvény végrehajtásával kapcsolatos részleteket tartalmaz: ahol a vezérlőáram most van, az aktuális változók, a this értéke (itt nem használjuk), valamint néhány egyéb belső részlet.

egy függvényhívásnak pontosan egy végrehajtási környezete van hozzá társítva.

amikor egy függvény beágyazott hívást kezdeményez, a következő történik:

• az aktuális függvény szünetel.
• az ehhez társított végrehajtási kontextust egy speciális adatstruktúrában, a végrehajtási kontextus veremben emlékezik meg.,
• a beágyazott hívás végrehajtja.
• a befejezés után a régi végrehajtási kontextus lekerül a veremből, a külső függvény pedig onnan folytatódik, ahonnan megállt.

lássuk, mi történik a pow(2, 3) hívás során.

pow(2, 3)

a hívás elején pow(2, 3) a végrehajtási környezet változókat tárol: x = 2, n = 3, a végrehajtási folyamat a 1 sorban van.,

vázolhatjuk:

• kontextus: { x: 2, n: 3, az 1.sorban } pow(2, 3)

ekkor kezdődik a függvény végrehajtása., A feltétel n == 1 falsy, így az áramlás továbbra is a második ága if:

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

A változók azonos, de a vonal változik, így a helyi most:

• Összefüggésben: { x: 2, n: 3, a vonal 5 } pow(2, 3)

kiszámításához x * pow(x, n - 1), szükségünk, hogy egy subcall a pow új érveket pow(2, 2).,

pow (2, 2)

beágyazott hívás végrehajtásához a JavaScript emlékszik az aktuális végrehajtási kontextusra a végrehajtási kontextusban.

itt ugyanazt a függvényt hívjuk pow, de ez egyáltalán nem számít. A folyamat minden funkció esetében azonos:

1. az aktuális kontextus “emlékezett” a verem tetején.
2. az új kontextus az alhívóhoz jön létre.
3. amikor az alhívó befejeződött – az előző szövegkörnyezet kiugrik a veremből, és a végrehajtás folytatódik.,

ez Itt a helyi verem, amikor beléptünk a subcall pow(2, 2):

• Összefüggésben: { x: 2, n: 2, at line 1 } pow(2, 2)
• Összefüggésben: { x: 2, n: 3, a vonal 5 } pow(2, 3)

Az új jelenlegi végrehajtás összefüggésben van a tetején (szőke), valamint a korábbi emlékezett kontextusokban alatt.

amikor befejezzük az alhívást-könnyű folytatni az előző kontextust, mert megtartja mind a változókat, mind a kód pontos helyét, ahol megállt.,

pow(2, 1)

a folyamat ismétlődik: egy új alhívó készül a 5 sorban, most argumentumokkal x=2, n=1.,

új végrehajtási környezet jön létre, az előző tolta a pakli tetejére:

• Összefüggésben: { x: 2, n: 1, at line 1 } pow(2, 1)
• Összefüggésben: { x: 2, n: 2, a vonal 5 } pow(2, 2)
• Összefüggésben: { x: 2, n: 3, a vonal 5 } pow(2, 3)

2 old kontextusokban most 1 jelenleg futó pow(2, 1).,

az exit

végrehajtása során pow(2, 1), ellentétben korábban, a feltétel n == 1 igaz, így az első ága if működik:

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

nincs több beágyazott hívás, így a funkció befejeződik, visszatérve 2.

ahogy a funkció befejeződik, annak végrehajtási környezete már nem szükséges, ezért eltávolításra kerül a memóriából., Az előző helyreáll a verem tetejéről:

• kontextus: { x: 2, n: 2, az 5.sorban } pow(2, 2)
• kontextus: { x: 2, n: 3, az 5. sorban } pow(2, 3)

akkor az előző kontextus visszaáll:

• kontextus: { x: 2, n: 3, az 5. sorban } pow(2, 3)

amikor befejeződik, a pow(2, 3) = 8eredménye.

a rekurzió mélysége ebben az esetben: 3.

amint azt a fenti illusztrációkból láthatjuk, a rekurzió mélysége megegyezik a verem maximális kontextusának számával.

vegye figyelembe a memória követelményeit. A kontextusok memóriát vesznek fel., A mi esetünkben, emelése a hatalom n valójában megköveteli a memória n kontextusok, minden alacsonyabb értékek n.

a hurok-alapú algoritmus több memória-megtakarítás:

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

az iteratív pow egyetlen kontextusváltozást használ i div > és result a folyamat során. Memóriája kicsi, fix és nem függ a n – tól.,

bármely rekurzió újraírható hurokként. A hurok változat általában hatékonyabb lehet.

… de néha az újraírás nem triviális, különösen akkor, ha a függvény a körülményektől függően különböző rekurzív alfejezeteket használ, összeolvasztja az eredményeket, vagy ha az elágazás bonyolultabb. És az optimalizálás szükségtelen lehet, és egyáltalán nem éri meg az erőfeszítéseket.

a rekurzió rövidebb kódot adhat, könnyebben érthető és támogatható. Optimalizálás Nem szükséges minden helyen, többnyire szükségünk van egy jó kódot, ezért használják.,

rekurzív keresztezések

a rekurzió másik nagyszerű alkalmazása egy rekurzív keresztirányú.

képzeljük el, van egy cég. A személyzeti struktúra objektumként jeleníthető meg:

más szóval, a társaságnak szervezeti egységei vannak.

• egy osztálynak lehet egy sor személyzete. Például, sales osztály 2 alkalmazottak: John and Alice.

• vagy egy osztály alosztályokra osztható, mint például a development két ága van: sites és internals. Mindegyiknek saját személyzete van.,

• az is lehetséges, hogy ha egy alosztály nő, akkor részosztályokra (vagy csapatokra) oszlik.

  például a sites osztály a jövőben a siteA és siteBcsapatokra osztható. És potenciálisan még jobban szétválhatnak. Ez nem szerepel a képen, csak valami, amit szem előtt kell tartani.

most tegyük fel, hogy szeretnénk egy függvényt, hogy megkapjuk az összes fizetés összegét. Hogy tehetjük ezt?

egy iteratív megközelítés nem könnyű, mert a szerkezet nem egyszerű., Az első ötlet az lehet, hogy egyfor hurok átcompany beágyazott alcsoport felett 1.szintű osztályok. De akkor több beágyazott alállomásra van szükségünk, hogy megismételjük a 2. szintű osztályok személyzetét, mint például a sites…, majd egy másik alállomást a 3. szintű osztályok számára, amelyek a jövőben megjelenhetnek? Ha 3-4 beágyazott alállomást helyezünk a kódba, hogy egyetlen objektumot áthaladjunk, akkor meglehetősen csúnya lesz.

próbáljuk meg a rekurziót.,

amint láthatjuk, amikor funkciónk egy osztályt összegez, két lehetséges eset van:

1. vagy ez egy “egyszerű” osztály egy sor emberrel – akkor a fizetéseket egy egyszerű hurokban összegezhetjük.
2. vagy ez egy objektum N aldepartments – akkor tudjuk, hogy N rekurzív hívások, hogy az összeget az egyes aldepek és össze az eredményeket.

az 1. eset a rekurzió alapja, a triviális eset, amikor tömböt kapunk.

a 2. eset, amikor egy objektumot kapunk, a rekurzív lépés., Egy összetett feladat a kisebb osztályok részfeladataira oszlik. Ezek viszont osztott újra, de előbb-utóbb a split fejeződik be (1).

az algoritmus valószínűleg még könnyebben olvasható a kódból:

a kód rövid és könnyen érthető (remélhetőleg?). Ez a rekurzió ereje. Úgy is működik, bármilyen szintű alosztály fészkelő.,

Itt a diagram hívások:

Megjegyezzük, hogy a kódot használ smart funkciók, amelyek már tartozó előtt:

• a Módszer arr.reduce magyarázta a fejezet Tömb módszerek, hogy az összeg a tömb.
• Loop for(val of Object.values(obj))to iterate over object values: Object.values returns an array of them.,

rekurzív struktúrák

a rekurzív (rekurzívan definiált) adatstruktúra olyan struktúra, amely részekben replikálódik.

most láttuk a fenti vállalati struktúra példáján.

A vállalati osztály:

• vagy egy sor ember.
• vagy egy objektum osztályok.

a webfejlesztők számára sokkal jobban ismert példák: HTML és XML dokumentumok.

A HTML dokumentumban egy HTML-címke tartalmazhat egy listát:

• Szövegdarabok.
• HTML-comments.,
• egyéb HTML-címkék (ez viszont tartalmazhat szöveges darabokat / megjegyzéseket vagy más címkéket stb.).

Ez ismét egy rekurzív definíció.

A jobb megértés érdekében lefedünk még egy rekurzív struktúrát, melynek neve “Linked list”, amely bizonyos esetekben jobb alternatíva lehet A tömbök számára.

Linked list

képzelje el, hogy az objektumok rendezett listáját szeretnénk tárolni.

a természetes választás egy tömb lenne:

let arr = ;

…de probléma van a tömbökkel., Az” elem törlése “és az” elem beszúrása ” műveletek drágák. Például a arr.unshift(obj) műveletnek újra kell számoznia az összes elemet, hogy helyet biztosítson egy új obj számára, és ha a tömb nagy, időbe telik. Ugyanaz a arr.shift().

az egyetlen olyan szerkezeti módosítás, amely nem igényel tömeges újraszámozást, azok, amelyek a tömb végével működnek: arr.push/pop. Tehát egy tömb meglehetősen lassú lehet A nagy sorok számára, amikor az elején kell dolgoznunk.,

Alternatív megoldásként, ha valóban gyors beillesztésre/törlésre van szükségünk, kiválaszthatunk egy másik adatszerkezetet, amelyet összekapcsolt listának hívnak.

a kapcsolódó lista elem rekurzívan definiálható objektumként:

• value.
• nexttulajdonság a következő kapcsolt listaelemre vagynull ha ez a vége.,

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., Alist változó az első objektum a láncban, így a következő next mutatókat is elérheti bármely elem.

A lista könnyen részre, több részre, majd később csatlakozott vissza:

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

csatlakozni:

list.next.next = secondList;

Pedig biztosan tudjuk helyezze be vagy távolítsa el az elemeket, bárhol.,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., A 1 értéket most kizárják a láncból. Ha máshol nem tárolja, akkor automatikusan eltávolításra kerül a memóriából.

a tömböktől eltérően nincs tömeg-átrendezés, könnyen átrendezhetjük az elemeket.

természetesen a listák nem mindig jobbak, mint a tömbök. Ellenkező esetben mindenki csak listákat használna.

a fő hátrány az, hogy nem tudunk könnyen hozzáférni egy elemhez annak számával. Egy egyszerű tömbben: arr közvetlen hivatkozás., De a listában az első elemből kell indulnunk, és a nextN idők az Nth elem megszerzéséhez.

… de nem mindig van szükségünk ilyen műveletekre. Például, ha szükségünk van egy sorban, vagy akár egy deque-a rendezett szerkezet, amely lehetővé teszi, hogy nagyon gyorsan hozzá / eltávolítása elemek mindkét végén, de hozzáférést a közepén nem szükséges.

A listák fokozhatók:

• a prev tulajdonság mellett hozzáadhatunk a next az előző elem hivatkozásához, hogy könnyen mozogjon.,
• hozzáadhatunk egy tail nevű változót is, amely a lista utolsó elemére hivatkozik (majd frissítjük, amikor elemeket adunk hozzá/távolítunk el a végétől).
• …az adatstruktúra igényeink szerint változhat.

összefoglaló

kifejezések:

• a rekurzió olyan programozási kifejezés, amely azt jelenti, hogy egy függvényt magából hívunk. A rekurzív funkciók elegáns módon oldhatók meg a feladatok megoldására.

  amikor egy függvény hívja magát, ez az úgynevezett rekurziós lépés., A rekurzió alapja olyan függvény argumentumok, amelyek a feladatot olyan egyszerűvé teszik, hogy a funkció nem kezdeményez további hívásokat.

• a rekurzívan definiált adatstruktúra olyan adatstruktúra, amely önmagával definiálható.

  például a hivatkozott lista olyan adatstruktúraként definiálható, amely egy listára hivatkozó objektumból áll (vagy null).

  list = { value, next -> list }

  olyan fák, mint a HTML elements fa vagy az osztályfa ebből a fejezetből szintén természetesen rekurzívak: elágaznak, és minden ágnak más ágai lehetnek.,

  a rekurzív függvények a sumSalary példában láthattuk.

bármely rekurzív függvény átírható iteratívra. És ez néha szükséges a dolgok optimalizálásához. De sok feladat esetén a rekurzív megoldás elég gyors és könnyebb írni és támogatni.