Rekurze a zásobník

Vraťme se k funkcím a prostudujme je podrobněji.

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

Pokud nejste v programování nováčkem, pak je pravděpodobně povědomý a tuto kapitolu byste mohli přeskočit.

Rekurze je programovací vzor, ​​který je užitečný v situacích, kdy lze úlohu přirozeně rozdělit na několik úloh stejného druhu, ale jednodušší. Nebo když lze úkol zjednodušit na snadnou akci plus jednodušší variantu stejného úkolu. Nebo, jak brzy uvidíme, zabývat se určitými datovými strukturami.

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

Dva způsoby myšlení

Pro začátek něco jednoduchého – napišme funkci pow(x, n) což vyvolává x na přirozenou mocninu n . Jinými slovy, vynásobí x sám o sobě n krát.

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

Existují dva způsoby, jak jej implementovat.

1. Iterativní myšlení:for smyčka:

   function pow(x, n) {
    let result = 1;
   
    // multiply result by x n times in the loop
    for (let i = 0; i < n; i++) {
    result *= x;
    }
   
    return result;
   }
   
   alert( pow(2, 3) ); // 8

2. Rekurzivní myšlení:zjednodušte úkol a říkejte si:

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

Všimněte si prosím, jak se rekurzivní varianta zásadně liší.

Když pow(x, n) je zavoláno, provedení se rozdělí na dvě větve:

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

1. Pokud n == 1 , pak je vše triviální. Říká se tomu základ rekurze, protože okamžitě produkuje zřejmý výsledek:pow(x, 1) rovná se x .
2. Jinak můžeme reprezentovat pow(x, n) jako x * pow(x, n - 1) . V matematice by člověk napsal xn = x * xn-1 . Tomu se říká rekurzivní krok :transformujeme úlohu na jednodušší akci (násobení x ) a jednodušší volání stejné úlohy (pow s nižším n ). Další kroky jej dále a dále zjednodušují až do n dosáhne 1 .

Můžeme také říci, že pow rekurzivně volá sám sebe do n == 1 .

Například pro výpočet pow(2, 4) rekurzivní varianta provádí 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 tedy redukuje volání funkce na jednodušší a pak – na ještě jednodušší a tak dále, dokud nebude výsledek zřejmý.

Rekurzivní řešení je obvykle kratší než iterativní.

Zde můžeme totéž přepsat pomocí podmíněného operátoru ? místo if vytvořit pow(x, n) stručnější a stále velmi čtivé:

function pow(x, n) {
 return (n == 1) ? x : (x * pow(x, n - 1));
}

Maximální počet vnořených volání (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 enginem. Můžeme se spolehnout, že je to 10 000, některé motory umožňují více, ale 100 000 je pro většinu z nich pravděpodobně mimo limit. Existují automatické optimalizace, které to pomáhají zmírnit („optimalizace „tail calls“), ale zatím nejsou všude podporovány a fungují pouze v jednoduchých případech.

To omezuje použití rekurze, ale stále zůstává velmi široké. Existuje mnoho úloh, kde rekurzivní způsob myšlení poskytuje jednodušší kód a snadnější údržbu.

Kontext provádění a zásobník

Nyní se podívejme, jak fungují rekurzivní volání. Za tímto účelem se podíváme pod pokličku funkcí.

Informace o procesu provádění spuštěné funkce jsou uloženy v jejím kontextu provádění .

Kontext provádění je interní datová struktura, která obsahuje podrobnosti o provádění funkce:kde je nyní řídicí tok, aktuální proměnné, hodnota this (zde jej nepoužíváme) a několik dalších interních podrobností.

Jedno volání funkce má přidružen přesně jeden kontext provádění.

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

• Aktuální funkce je pozastavena.
• Kontext provádění, který je s ním spojen, je zapamatován ve speciální datové struktuře zvané zásobník kontextu provádění .
• Provede se vnořené volání.
• Po jejím skončení je ze zásobníku načten starý kontext provádění a vnější funkce je obnovena od místa, kde byla zastavena.

Podívejme se, co se stane během pow(2, 3) zavolejte.

pow(2, 3)

Na začátku volání pow(2, 3) kontext provádění bude ukládat proměnné:x = 2, n = 3 , tok provádění je na řádku 1 funkce.

Můžeme to načrtnout jako:

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

Tehdy se funkce začne vykonávat. Podmínka n == 1 je falešný, takže tok pokračuje do druhé větve 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 mění se řádek, takže kontext je nyní:

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

Pro výpočet x * pow(x, n - 1) , musíme provést dílčí volání pow s novými argumenty pow(2, 2) .

pow(2, 2)

Aby bylo možné provést vnořené volání, JavaScript si pamatuje aktuální kontext provádění v zásobníku kontextu provádění .

Zde nazýváme stejnou funkci pow , ale to je úplně jedno. Postup je stejný pro všechny funkce:

1. Aktuální kontext je „zapamatován“ v horní části zásobníku.
2. Pro dílčí volání se vytvoří nový kontext.
3. Po dokončení dílčího volání – předchozí kontext se vytáhne ze zásobníku a jeho provádění pokračuje.

Zde je zásobník kontextu, když jsme zadali dílčí volání 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 provádění je nahoře (a tučný) a předchozí zapamatované kontexty jsou níže.

Když dokončíme dílčí volání – je snadné obnovit předchozí kontext, protože zachovává obě proměnné a přesné místo kódu, kde se zastavil.

Zde na obrázku používáme slovo „řádek“, protože v našem příkladu je v řadě pouze jedno dílčí volání, ale obecně může jeden řádek kódu obsahovat více dílčích volání, například pow(…) + pow(…) + somethingElse(…) .

Bylo by tedy přesnější říci, že provádění se obnoví „ihned po dílčím volání“.

pow(2, 1)

Proces se opakuje:na řádku 5 se provede nové dílčí volání , nyní s argumenty x=2 , n=1 .

Vytvoří se nový kontext provádění, předchozí se přesune na vrchol zásobníku:

• Kontext:{ x:2, n:1, na řádku 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)

Nyní existují 2 staré kontexty a 1 aktuálně běží pro pow(2, 1) .

Výstup

Během provádění pow(2, 1) , na rozdíl od dříve podmínka n == 1 je pravdivý, takže první větev if funguje:

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

Již neexistují žádná vnořená volání, takže funkce skončí a vrátí 2 .

Jakmile funkce skončí, její kontext provádění již není potřeba, takže je odstraněna z paměti. Předchozí se obnoví z horní části 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)

Provedení pow(2, 2) je obnoveno. Má výsledek dílčího volání pow(2, 1) , takže také může dokončit vyhodnocení x * pow(x, n - 1) , vrací 4 .

Poté se obnoví předchozí kontext:

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

Po dokončení 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ě zvýšení na mocninu n ve skutečnosti vyžaduje paměť pro n kontextech, pro všechny nižší hodnoty n .

Algoritmus založený na smyčce šetří paměť:

function pow(x, n) {
 let result = 1;

 for (let i = 0; i < n; i++) {
 result *= x;
 }

 return result;
}

Iterativní pow používá jeden kontext měnící i a result v průběhu. Jeho požadavky na paměť jsou malé, pevné a nezávisí na n .

Jakoukoli rekurzi lze přepsat jako smyčku. Varianta smyčky může být obvykle efektivnější.

…Ale někdy je přepis netriviální, zvláště když funkce používá různá rekurzivní dílčí volání v závislosti na podmínkách a slučuje jejich výsledky nebo když je větvení složitější. A optimalizace může být zbytečná a vůbec nestojí za námahu.

Rekurze může poskytnout kratší kód, snazší na 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í procházení

Další skvělou aplikací rekurze je rekurzivní procházení.

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

let company = {
 sales: [{
 name: 'John',
 salary: 1000
 }, {
 name: 'Alice',
 salary: 1600
 }],

 development: {
 sites: [{
 name: 'Peter',
 salary: 2000
 }, {
 name: 'Alex',
 salary: 1800
 }],

 internals: [{
 name: 'Jack',
 salary: 1300
 }]
 }
};

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

• Oddělení může mít řadu zaměstnanců. Například sales oddělení má 2 zaměstnance:Johna a Alice.

• Nebo se oddělení může rozdělit na pododdělení, například development má dvě větve:sites a internals . Každý z nich má své vlastní zaměstnance.

• Je také možné, že když se pododdělení rozroste, rozdělí se na pododdělení (nebo týmy).

  Například sites oddělení může být v budoucnu rozděleno do týmů pro siteA a siteB . A mohou se potenciálně rozdělit ještě více. To na obrázku není, jen 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í nápad může být vytvořit for smyčka přes company s vnořenou podsmyčkou přes oddělení 1. úrovně. Ale pak potřebujeme více vnořených dílčích smyček, abychom mohli iterovat přes zaměstnance v odděleních 2. úrovně, jako je sites … A pak další dílčí smyčka uvnitř těch pro oddělení 3. úrovně, která by se mohla objevit v budoucnu? Pokud do kódu vložíme 3-4 vnořené podsmyčky k procházení jednoho objektu, bude to dost ošklivé.

Zkusme rekurzi.

Jak vidíme, když naše funkce sčítá oddělení, existují dva možné případy:

1. Buď je to „jednoduché“ oddělení s polí lidí – pak můžeme platy shrnout do jednoduché smyčky.
2. Nebo je to objekt s N pododdělení – pak můžeme vytvořit N rekurzivní volání, abyste získali součet pro každou z dílčích úrovní a spojili výsledky.

První případ je základem rekurze, triviální případ, kdy získáme pole.

2. případ, kdy dostaneme objekt, je rekurzivní krok. Složitý úkol je rozdělen do dílčích úkolů pro menší oddělení. Mohou se zase rozdělit, ale dříve nebo později rozdělení skončí na (1).

Algoritmus je pravděpodobně ještě snadněji čitelný z kódu:

let company = { // the same object, compressed for brevity
 sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
 development: {
 sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
 internals: [{name: 'Jack', salary: 1300}]
 }
};

// The function to do the job
function sumSalaries(department) {
 if (Array.isArray(department)) { // case (1)
 return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
 } else { // case (2)
 let sum = 0;
 for (let subdep of Object.values(department)) {
 sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
 }
 return sum;
 }
}

alert(sumSalaries(company)); // 7700

Kód je krátký a snadno srozumitelný (doufejme?). To je síla rekurze. Funguje také pro jakoukoli úroveň vnoření pododdělení.

Zde je schéma hovorů:

Princip můžeme snadno vidět:pro objekt {...} provádějí se dílčí volání, zatímco pole [...] jsou „listy“ stromu rekurze, poskytují okamžitý výsledek.

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

• Metoda arr.reduce vysvětleno v kapitole Metody pole k získání součtu pole.
• Smyčka for(val of Object.values(obj)) pro iteraci přes hodnoty objektu:Object.values vrátí pole z nich.

Rekurzivní struktury

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

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

Oddělení společnosti je:

• Buď řada lidí.
• Nebo objekt s odděleními .

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

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

• Textové části.
• Komentáře HTML.
• Další značky HTML (které zase mohou obsahovat části textu/komentáře nebo jiné značky atd.).

To je opět rekurzivní definice.

Pro lepší pochopení pokryjeme ještě jednu rekurzivní strukturu nazvanou „Propojený seznam“, která může být v některých případech lepší alternativou pro pole.

Propojený seznam

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

Přirozenou volbou by bylo pole:

let arr = [obj1, obj2, obj3];

…Je tu ale problém s poli. Operace „smazat prvek“ a „vložit prvek“ jsou drahé. Například arr.unshift(obj) operace musí přečíslovat všechny prvky, aby se uvolnilo místo pro nový obj a pokud je pole velké, trvá to. Totéž s arr.shift() .

Jediné strukturální úpravy, 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.

Případně, pokud opravdu potřebujeme rychlé vkládání/mazání, můžeme zvolit jinou datovou strukturu nazvanou propojený seznam.

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

• value .
• next vlastnost odkazující na další propojený prvek seznamu nebo null pokud je to konec.

Například:

let list = {
 value: 1,
 next: {
 value: 2,
 next: {
 value: 3,
 next: {
 value: 4,
 next: null
 }
 }
 }
};

Grafické znázornění seznamu:

Alternativní kód pro vytvoření:

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;

Zde můžeme ještě jasněji vidět, že existuje více objektů, každý má value a next ukazující na souseda. list proměnná je prvním objektem v řetězci, takže následuje next ukazatelů z něj můžeme dosáhnout jakéhokoli prvku.

Seznam lze snadno rozdělit na více částí a později zpět spojit:

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

Chcete-li se připojit:

list.next.next = secondList;

A určitě můžeme vkládat nebo odebírat položky na libovolném místě.

Například, abychom předřadili novou hodnotu, musíme aktualizovat hlavičku seznamu:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

// prepend the new value to the list
list = { value: "new item", next: list };

Chcete-li odstranit hodnotu ze středu, změňte next předchozího:

list.next = list.next.next;

Vytvořili jsme list.next přeskočit 1 na hodnotu 2 . Hodnota 1 je nyní z řetězce vyloučen. Pokud není uložen nikde jinde, bude automaticky odstraněn z paměti.

Na rozdíl od polí zde nedochází k hromadnému přečíslování, prvky můžeme snadno přeskupit.

Seznamy přirozeně nejsou vždy lepší než pole. Jinak by všichni používali pouze seznamy.

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

…Ale ne vždy takové operace potřebujeme. Například, když potřebujeme frontu nebo dokonce deque – uspořádanou strukturu, která musí umožňovat velmi rychlé přidávání/odebírání prvků z obou konců, ale přístup k jejímu středu není potřeba.

Seznamy lze vylepšit:

• Můžeme přidat vlastnost prev kromě next odkazovat na předchozí prvek, snadno se vrátit zpět.
• Můžeme také přidat proměnnou s názvem tail odkazovat na poslední prvek seznamu (a aktualizovat jej při přidávání/odebírání prvků z konce).
• ...Struktura dat se může lišit podle našich potřeb.

Shrnutí

Podmínky:

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

  Když funkce volá sama sebe, nazývá se to krok rekurze . Základ rekurze jsou argumenty funkce, díky nimž je úloha tak jednoduchá, že funkce neprovádí další volání.

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

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

  list = { value, next -> list }

  Stromy jako strom elementů HTML nebo strom oddělení z této kapitoly jsou také přirozeně rekurzivní:mají větve a každá větev může mít další větve.

  K jejich procházení lze použít rekurzivní funkce, jak jsme viděli v sumSalary příklad.

Jakoukoli rekurzivní funkci lze přepsat na iterativní. A to je někdy potřeba k optimalizaci věcí. Ale pro mnoho úloh je rekurzivní řešení dostatečně rychlé a jednodušší na psaní a podporu.