pojďme se vrátit k funkcím a studovat je hlouběji.

naším prvním tématem bude rekurze.

Pokud nejste v programování noví, pak je to pravděpodobně známé a můžete tuto kapitolu přeskočit.

rekurze je programovací vzorec, který je užitečný v situacích, kdy lze úkol přirozeně rozdělit na několik úkolů stejného druhu, ale jednodušší. Nebo když může být úkol zjednodušen do jednoduché akce plus jednodušší varianta stejného úkolu. Nebo, jak uvidíme brzy, vypořádat se s určitými datovými strukturami.,

Když funkce řeší úkol, může v procesu volat mnoho dalších funkcí. Částečným případem je, když se funkce volá. Tomu se říká rekurze.

Dva způsoby, jak přemýšlet

Pro něco jednoduchého pro začátek – pojďme napsat funkci pow(x, n), který vyvolává x přírodní síla n. Jinými slovy, násobí xsám n časy.

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

existují dva způsoby, jak jej implementovat.,

Vezměte prosím na vědomí, jak je rekurzivní varianta zásadně odlišná.

Když pow(x, n) je volána, výkon se rozdělí do dvou větví:

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

1. Pokud n == 1, pak je vše triviální. Nazývá se základna rekurze, protože okamžitě vytváří zřejmý výsledek: pow(x, 1)se rovná x.
2. jinak můžeme reprezentovat pow(x, n)jako x * pow(x, n - 1)., V matematice by se psalo xn = x * xn-1. To se nazývá rekurzivní krok: jsme změnit úkol na jednodušší akce (násobení x) a jednodušší zavolat stejného úkolu (pow s nižší n). Další kroky jej dále a dále zjednodušují ,dokudn nedosáhne 1.

můžeme také říci, že pow se rekurzivně nazývá till n == 1.,

například, vypočítat pow(2, 4) rekurzivní varianta má tyto kroky:

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

rekurze snižuje volání funkce na jednodušší, a pak – ještě jednodušší, a tak dále, dokud výsledek se stává zřejmé.,

maximální počet vnořených hovorů (včetně prvního) se nazývá hloubka rekurze. V našem případě to bude přesně n.

maximální hloubka rekurze je omezena JavaScriptovým motorem. Můžeme se spolehnout na to, že je 10000, některé motory umožňují více, ale 100000 je pro většinu z nich pravděpodobně mimo limit. Existují automatické optimalizace, které to pomáhají zmírnit („tail calls optimizations“), ale dosud nejsou podporovány všude a fungují pouze v jednoduchých případech.

, která omezuje aplikaci rekurze, ale stále zůstává velmi široká., Existuje mnoho úkolů, kde rekurzivní způsob myšlení dává jednodušší kód, snadněji se udržuje.

kontext provádění a stack

nyní se podívejme, jak rekurzivní hovory fungují. Za to se podíváme pod kapotu funkcí.

informace o procesu provádění běžící funkce jsou uloženy v kontextu jejího provádění.,

kontext spuštění je interní datová struktura, která obsahuje podrobnosti o výkonu funkce, kde tok řízení je teď aktuální proměnné, hodnota this (my ji nepoužíváme) a několik dalších vnitřních detailů.

jedno volání funkce má přesně jeden kontext provedení s ním spojené.

Když funkce provede vnořené volání, stane se následující:

• aktuální funkce je pozastavena.
• kontext provedení, který je s ním spojen, je zapamatován ve speciální datové struktuře nazvané execution context stack.,
• vnořený hovor se spustí.
• po ukončení se starý kontext provedení načte ze zásobníku a vnější funkce se obnoví, odkud se zastaví.

uvidíme, co se stane během volánípow(2, 3).

pow(2, 3)

na začátku: pow(2, 3) kontext spuštění bude ukládat proměnné: x = 2, n = 3, provedení tok je na řádek 1 funkce.,

můžeme ho nakreslit jako:

• Kontext: { x: 2, n: 3, na řádku 1 } pow(2, 3)

to je, když funkce začne vykonávat., Stav n == 1 je falsy, tak tok pokračuje do druhé pobočce if:

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

proměnné jsou stejné, ale řada změn, takže kontext je teď:

• Kontext: { x: 2, n: 3, na řádku 5 } pow(2, 3)

vypočítat x * pow(x, n - 1) potřebujeme, aby se subcall pow s novými argumenty pow(2, 2).,

pow(2, 2)

Chcete-li provést vnořený hovor, JavaScript si pamatuje aktuální kontext provádění v kontextovém zásobníku provádění.

zde nazýváme stejnou funkci pow, ale na tom vůbec nezáleží. Proces je stejný pro všechny funkce:

1. aktuální kontext je „vzpomněl“ na vrcholu zásobníku.
2. nový kontext je vytvořen pro subkall.
3. Po dokončení subkallu-předchozí kontext se vyskočí ze zásobníku a jeho provedení pokračuje.,

Zde je kontext stack, když jsme vstoupili do subcall pow(2, 2):

• Kontext: { x: 2, n: 2, na řádku 1 } pow(2, 2)
• Kontext: { x: 2, n: 3, na řádku 5 } pow(2, 3)

nová aktuální kontext spuštění je na vrcholu (a odvážné), a předchozí vzpomněl kontexty jsou níže.

po dokončení subcall-je snadné obnovit předchozí kontext, protože udržuje proměnné i přesné místo kódu, kde se zastavil.,

pow(2, 1)

proces Se opakuje: nový subcall je vyroben na řádek 5, nyní s argumenty x=2 n=1.,

nový kontext spuštění je vytvořen, ten předchozí je tlačen na vrcholu zásobníku:

• Kontext: { x: 2, n: 1, řádek 1 } pow(2, 1)
• Kontext: { x: 2, n: 2, na řádku 5 } pow(2, 2)
• Kontext: { x: 2, n: 3, na řádku 5 } pow(2, 3)

k Dispozici jsou 2 staré kontextech nyní a 1 v současné době běží na pow(2, 1).,

exit

Při spuštění pow(2, 1), na rozdíl od dříve, stav n == 1 je pravdivý, takže první část if funguje:

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

nejsou žádné další vnořené volání, takže funkce dokončí, vrací 2.

Jak funkce skončí, její kontext provádění již není potřeba, takže je odstraněn z paměti., Předchozí je obnoven z vrcholu zásobníku:

• Kontext: { x: 2, n: 2, na řádku 5 } pow(2, 2)
• Kontext: { x: 2, n: 3, na řádku 5 } pow(2, 3)

Pak se v předchozím kontextu je obnovena:

• Kontext: { x: 2, n: 3, na řádku 5 } pow(2, 3)

Když to skončí, máme výsledek pow(2, 3) = 8.

hloubka rekurze v tomto případě byla: 3.

jak můžeme vidět z výše uvedených ilustrací, hloubka rekurze se rovná maximálnímu počtu kontextu v zásobníku.

Všimněte si požadavků na paměť. Kontexty berou paměť., V našem případě zvyšování síly n ve skutečnosti vyžaduje paměť pro n kontextech, pro všechny nižší hodnoty n.

loop-based algoritmus je více paměti-uložení:

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

iterativní pow používá jeden kontextu měnící i result v tomto procesu. Jeho požadavky na paměť jsou malé, pevné a nezávisí na n.,

jakákoli rekurze může být přepsána jako smyčka. Varianta smyčky může být obvykle účinnější.

…ale někdy je přepsání netriviální, zvláště když funkce používá různé rekurzivní subkaly v závislosti na podmínkách a sloučí jejich výsledky nebo když je větvení složitější. A optimalizace může být nepotřebná a rozhodně nestojí za úsilí.

rekurze může poskytnout kratší kód, snadnější pochopení a podporu. Optimalizace nejsou vyžadovány na každém místě, většinou potřebujeme dobrý kód, proto se používá.,

rekurzivní traversals

Další skvělou aplikací rekurze je rekurzivní traversal.

Představte si, že máme společnost. Struktura zaměstnanců může být prezentována jako objekt:

jinými slovy, společnost má oddělení.

• oddělení může mít řadu zaměstnanců. Napříkladsales oddělení má 2 zaměstnance: John a Alice.

• Nebo oddělení může rozdělit do subdepartments, jako development má dvě větve: sites internals. Každý z nich má svůj vlastní personál.,

• je také možné, že když subdepartment roste, dělí se na subsubdepartmenty (nebo týmy).

  například sites oddělení v budoucnu může být rozdělena do týmů pro siteA siteB. A potenciálně se mohou ještě více rozdělit. To není na obrázku, jen něco, co je třeba mít na paměti.

nyní řekněme, že chceme funkci získat součet všech platů. Jak to můžeme udělat?

iterativní přístup není snadný, protože struktura není jednoduchá., První myšlenkou může být vytvořenífor smyčky přes company s vnořeným subloopem přes oddělení 1. úrovně. Ale pak potřebujeme více vnořených subloops iterovat přes personál v 2. úrovni oddělení, jako je sites… A pak další subloop uvnitř těch, pro 3. úroveň oddělení, které se mohou objevit v budoucnu? Pokud do kódu vložíme 3-4 vnořené subloopy, abychom procházeli jediným objektem, stává se to spíše ošklivé.

zkusme rekurzi.,

Jak můžeme vidět, když se naše funkce dostane oddělení, abych to shrnul, jsou dva možné případy:

1. Buď je to „jednoduché“ oddělení s řadou lidí – pak můžeme součet platů v jednoduché smyčce.
2. Nebo je to objekt s N subdepartments – pak můžeme udělat N rekurzivní volání, aby se součet pro každý z subdeps a kombinovat výsledky.

1. případ je základem rekurze, triviálního případu, když dostaneme pole.

2. případ, kdy dostaneme objekt, je rekurzivní krok., Komplexní úkol je rozdělen na dílčí úkoly pro menší oddělení. Mohou zase rozdělit znovu, ale dříve nebo později rozdělení skončí na (1).

algoritmus je pravděpodobně ještě snazší číst z kódu:

kód je krátký a snadno pochopitelný (doufejme?). To je síla rekurze. Funguje také pro jakoukoli úroveň vnoření subdepartmentu.,

Tady je diagram volání:

Všimněte si, že kód používá inteligentní funkce, které jsme probrali dříve, než:

• Metoda arr.reduce vysvětleno v kapitole Array metody, aby se součet pole.
• Loop for(val of Object.values(obj)) pro iteraci nad hodnotami objektů: Object.values vrací jejich pole.,

rekurzivní struktury

rekurzivní (rekurzivně definovaná) datová struktura je struktura, která se replikuje po částech.

právě jsme to viděli v příkladu struktury společnosti výše.

firemní oddělení je:

• buď řada lidí.
• nebo objekt s odděleními.

pro webové vývojáře existují mnohem známější příklady: HTML a XML dokumenty.

v dokumentu HTML může značka HTML obsahovat seznam:

• textových kusů.
• HTML-komentáře.,
• další HTML značky (které zase mohou obsahovat textové kusy/komentáře nebo jiné značky atd.).

to je opět rekurzivní definice.

pro lepší pochopení pokryjeme ještě jednu rekurzivní strukturu s názvem „Linked list“, která by v některých případech mohla být lepší alternativou pro pole.

propojený seznam

Představte si, že chceme uložit objednaný seznam objektů.

přírodní výběr by být pole:

let arr = ;

…Ale je tam problém s poli., Operace“ odstranit prvek „a“ vložit prvek “ jsou drahé. Například arr.unshift(obj) operace musí přečíslovat všechny prvky, aby se prostor pro nové obj, a v případě, že pole je velký, to trvá dlouho. Stejné s arr.shift().

jediné strukturální modifikace, které nevyžadují hromadné přečíslování, jsou ty, které pracují s koncem pole: arr.push/pop. Takže pole může být docela pomalé pro velké fronty, když musíme pracovat se začátkem.,

alternativně, pokud opravdu potřebujeme rychlé vložení/vymazání, můžeme zvolit jinou strukturu dat nazvanou propojený seznam.

prvek propojeného seznamu je rekurzivně definován jako objekt s:

• value.
• next vlastnost odkazující na další spojový seznam prvek nebo null pokud to je konec.,

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 proměnná je první objekt v řetězci, takže následující next ukazatele z ní můžeme dosáhnout jakéhokoli prvku.

seznam lze snadno rozdělit na více částí a později se připojil zpět:

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

připojit:

list.next.next = secondList;

A jistě můžeme vložit nebo odstranit položky v každém místě.,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., Hodnota 1 je nyní z řetězce vyloučena. Pokud není uložen nikde jinde, bude automaticky odstraněn z paměti.

Na rozdíl od polí neexistuje žádné hromadné přečíslování, můžeme snadno uspořádat prvky.

seznamy samozřejmě nejsou vždy lepší než pole. Jinak by každý používal pouze seznamy.

hlavní nevýhodou je, že nemůžeme snadno přistupovat k prvku podle jeho čísla. V poli, které je snadné: arr je přímý odkaz., Ale v seznamu musíme začít od první položka a next N krát získat N-tý prvek.

…ale takové operace nepotřebujeme vždy. Například, když potřebujeme frontě nebo deque – objednané strukturu, která musí umožnit velmi rychlé přidání/odebrání prvků z obou konců, ale přístup k jeho středu není potřeba.

Seznamy mohou být rozšířené:

• můžeme přidat vlastnost prev kromě next odkaz na předchozí prvek, přesunout zpět snadno.,
• můžeme také přidat proměnné s názvem tail odkazující na poslední prvek seznamu (a aktualizovat při přidání/odebrání prvků od konce).
• …struktura dat se může lišit podle našich potřeb.

Shrnutí

Termíny:

• Rekurze je programovací termín, který znamená volání funkce ze sebe. Rekurzivní funkce lze použít k řešení úkolů elegantními způsoby.

  když se funkce volá, nazývá se to krok rekurze., Základem rekurze jsou Funkční argumenty, které činí úkol tak jednoduchým, že funkce neprovádí další hovory.

• rekurzivně definovaná datová struktura je datová struktura, kterou lze definovat pomocí sebe sama.

  například propojený seznam lze definovat jako datovou strukturu sestávající z objektu odkazujícího na seznam (nebo null).

  list = { value, next -> list }

  Stromy, jako jsou prvky HTML strom nebo oddělení stromu od této kapitole jsou také přirozeně rekurzivní: se větví a každá větev může mít jiné větve.,

  rekurzivní funkce lze použít k jejich procházce,jak jsme viděli v příkladu sumSalary.

libovolnou rekurzivní funkci lze přepsat na iterativní. A to je někdy nutné k optimalizaci věci. Ale pro mnoho úkolů je rekurzivní řešení dostatečně rychlé a snadnější psát a podporovat.