Rekurzia je základný koncept v informatike a matematike, ktorý umožňuje funkciám volať samy seba, čo umožňuje riešenie zložitých problémov prostredníctvom iteračných krokov. Jedna vizuálna reprezentácia bežne používaná na pochopenie a analýzu vykonávania rekurzívnych funkcií je strom rekurzie. V tomto článku budeme skúmať teóriu rekurzívnych stromov, ich štruktúru a ich význam pre pochopenie rekurzívnych algoritmov.

Čo je to strom rekurzie?

Strom rekurzie je grafické znázornenie, ktoré ilustruje tok vykonávania rekurzívnej funkcie. Poskytuje vizuálny rozpis rekurzívnych hovorov, ukazuje postup algoritmu, keď sa rozvetvuje a nakoniec dosiahne základný prípad. Stromová štruktúra pomáha pri analýze časovej zložitosti a pochopení rekurzívneho procesu.

Stromová štruktúra

Každý uzol v strome rekurzie predstavuje konkrétne rekurzívne volanie. Počiatočné volanie je znázornené v hornej časti a ďalšie hovory sa rozvetvujú pod ním. Strom rastie smerom nadol a vytvára hierarchickú štruktúru. Faktor vetvenia každého uzla závisí od počtu rekurzívnych volaní uskutočnených v rámci funkcie. Okrem toho hĺbka stromu zodpovedá počtu rekurzívnych volaní pred dosiahnutím základného prípadu.

Základný prípad

Základný prípad slúži ako podmienka ukončenia rekurzívnej funkcie. Definuje bod, v ktorom sa rekurzia zastaví a funkcia začne vracať hodnoty. V strome rekurzie sú uzly reprezentujúce základný prípad zvyčajne zobrazené ako listové uzly, pretože nevedú k ďalším rekurzívnym volaniam.

veľa štastia

Rekurzívne hovory

Podriadené uzly v strome rekurzie predstavujú rekurzívne volania uskutočnené v rámci funkcie. Každý podriadený uzol zodpovedá samostatnému rekurzívnemu volaniu, čo vedie k vytvoreniu nových čiastkových problémov. Hodnoty alebo parametre odovzdané týmto rekurzívnym volaniam sa môžu líšiť, čo vedie k zmenám v charakteristikách čiastkových problémov.

Priebeh vykonávania:

Prechádzanie stromom rekurzie poskytuje prehľad o toku vykonávania rekurzívnej funkcie. Počnúc počiatočným volaním v koreňovom uzle sledujeme vetvy, aby sme dosiahli ďalšie volania, až kým nenarazíme na základný prípad. Keď sa dosiahnu základné prípady, rekurzívne volania sa začnú vracať a ich príslušné uzly v strome sú označené vrátenými hodnotami. Prechádzanie pokračuje, kým sa neprejde celý strom.

Analýza časovej zložitosti

Rekurzívne stromy pomáhajú pri analýze časovej zložitosti rekurzívnych algoritmov. Preskúmaním štruktúry stromu môžeme určiť počet uskutočnených rekurzívnych hovorov a vykonanú prácu na každej úrovni. Táto analýza pomáha pochopiť celkovú efektívnosť algoritmu a identifikovať všetky potenciálne neefektívnosti alebo príležitosti na optimalizáciu.

Úvod

• Predstavte si program, ktorý určuje faktoriál čísla. Táto funkcia berie ako vstup číslo N a ako výsledok vráti faktoriál N. Pseudokód tejto funkcie sa bude podobať

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Príkladom rekurzie je funkcia, ktorá už bola spomenutá. Vyvolávame funkciu na určenie faktoriálu čísla. Potom pri menšej hodnote rovnakého čísla táto funkcia zavolá sama seba. Toto pokračuje, kým sa nedostaneme k základnému prípadu, v ktorom už neexistujú žiadne volania funkcií.
• Rekurzia je technika na riešenie zložitých problémov, keď výsledok závisí od výsledkov menších prípadov toho istého problému.
• Ak uvažujeme o funkciách, o funkcii sa hovorí, že je rekurzívna, ak sa sama volá, kým nedosiahne základný prípad.
• Každá rekurzívna funkcia má dve primárne zložky: základný prípad a rekurzívny krok. Keď dosiahneme základný prípad, prestaneme prechádzať do rekurzívnej fázy. Aby sa zabránilo nekonečnej rekurzii, základné prípady musia byť správne definované a sú kľúčové. Definícia nekonečnej rekurzie je rekurzia, ktorá nikdy nedosiahne základný prípad. Ak program nikdy nedosiahne základný prípad, pretečenie zásobníka bude pokračovať.

Typy rekurzie

Vo všeobecnosti existujú dve rôzne formy rekurzie:

• Lineárna rekurzia
• Rekurzia stromu
• Lineárna rekurzia

Lineárna rekurzia

• Funkcia, ktorá sa pri každom spustení zavolá len raz, sa považuje za lineárne rekurzívnu. Peknou ilustráciou lineárnej rekurzie je faktorová funkcia. Názov „lineárna rekurzia“ sa vzťahuje na skutočnosť, že lineárne rekurzívna funkcia potrebuje lineárny čas na vykonanie.
• Pozrite sa na nižšie uvedený pseudokód:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Ak sa pozrieme na funkciu doSomething(n), tá akceptuje parameter s názvom n a vykoná niekoľko výpočtov predtým, ako zavolá rovnakú procedúru ešte raz, ale s nižšími hodnotami.
• Keď sa zavolá metóda doSomething() s hodnotou argumentu n, povedzme, že T(n) predstavuje celkové množstvo času potrebného na dokončenie výpočtu. Na to môžeme formulovať aj rekurentný vzťah, T(n) = T(n-1) + K. K tu slúži ako konštanta. Konštanta K je zahrnutá, pretože funkcii trvá určitý čas, kým pridelí alebo zruší pridelenie pamäte premennej alebo vykoná matematickú operáciu. Používame K na definovanie času, pretože je taký minútový a bezvýznamný.
• Časovú zložitosť tohto rekurzívneho programu možno jednoducho vypočítať, pretože v najhoršom scenári sa metóda doSomething() volá n-krát. Formálne povedané, časová zložitosť funkcie je O(N).

Rekurzia stromu

• Keď vykonáte rekurzívne volanie vo svojom rekurzívnom prípade viac ako raz, označuje sa to ako stromová rekurzia. Účinnou ilustráciou stromovej rekurzie je Fibonacciho sekvencia. Rekurzívne funkcie stromu fungujú v exponenciálnom čase; nie sú lineárne vo svojej časovej zložitosti.
• Pozrite sa na pseudokód nižšie,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Jediný rozdiel medzi týmto kódom a predchádzajúcim je ten, že tento vykoná ešte jedno volanie tej istej funkcie s nižšou hodnotou n.
• Dajme T(n) = T(n-1) + T(n-2) + k ako rekurentný vzťah pre túto funkciu. K slúži opäť ako konštanta.
• Keď sa vykoná viac ako jedno volanie tej istej funkcie s menšími hodnotami, tento druh rekurzie je známy ako stromová rekurzia. Zaujímavým aspektom je teraz: ako časovo náročná je táto funkcia?
• Uhádnite na základe nižšie uvedeného stromu rekurzie pre rovnakú funkciu.
  
• Možno vás napadne, že je náročné odhadnúť časovú zložitosť priamym pohľadom na rekurzívnu funkciu, najmä ak ide o stromovú rekurziu. Metóda stromu rekurzie je jednou z niekoľkých techník na výpočet časovej zložitosti takýchto funkcií. Pozrime sa na to podrobnejšie.

Čo je metóda stromu rekurzie?

• Rekurentné vzťahy ako T(N) = T(N/2) + N alebo dva, ktoré sme preberali vyššie v sekcii o druhoch rekurzie, sú riešené pomocou prístupu stromu rekurzie. Tieto recidivujúce vzťahy často využívajú na riešenie problémov stratégiu rozdeľuj a panuj.
• Integrácia odpovedí na menšie čiastkové problémy, ktoré vznikajú, keď sa väčší problém rozdelí na menšie čiastkové problémy, si vyžaduje čas.
• Vzťah opakovania je napríklad T(N) = 2 * T(N/2) + O(N) pre triedenie Zlúčiť. Čas potrebný na spojenie odpovedí na dva čiastkové problémy s kombinovanou veľkosťou T(N/2) je O(N), čo platí aj na úrovni implementácie.
• Napríklad, keďže vzťah opakovania pre binárne vyhľadávanie je T(N) = T(N/2) + 1, vieme, že každá iterácia binárneho hľadania má za následok zmenšenie priestoru vyhľadávania na polovicu. Po určení výsledku funkciu opustíme. Vzťah opakovania sa pridal +1, pretože ide o operáciu s konštantným časom.
• Je potrebné zvážiť rekurentný vzťah T(n) = 2T(n/2) + Kn. Kn označuje množstvo času potrebného na spojenie odpovedí na n/2-rozmerné čiastkové problémy.
• Ukážme si strom rekurzie pre vyššie uvedený vzťah rekurencie.

Zo štúdia vyššie uvedeného stromu rekurzie môžeme vyvodiť niekoľko záverov, vrátane

1. Na určenie hodnoty uzla záleží len na veľkosti problému na každej úrovni. Veľkosť emisie je n na úrovni 0, n/2 na úrovni 1, n/2 na úrovni 2 atď.

2. Vo všeobecnosti definujeme výšku stromu ako log (n), kde n je veľkosť problému a výška tohto stromu rekurzie sa rovná počtu úrovní v strome. To je pravda, pretože, ako sme práve zistili, stratégiu rozdeľuj a panuj používajú rekurentné vzťahy na riešenie problémov a dostať sa z veľkosti problému n na veľkosť problému 1 si jednoducho vyžaduje urobiť log (n) krokov.

• Zoberme si napríklad hodnotu N = 16. Ak je nám dovolené deliť N v každom kroku 2, koľko krokov je potrebných na získanie N = 1? Vzhľadom na to, že v každom kroku delíme dvoma, správna odpoveď je 4, čo je hodnota log(16) základ 2.

log(16) základ 2

log(2^4) základ 2

4 * log(2) základ 2, pretože log(a) základ a = 1

takže 4 * log(2) základ 2 = 4

3. Na každej úrovni sa druhý člen v opakovaní považuje za koreň.

Hoci sa v názve tejto stratégie objavuje slovo „strom“, nemusíte byť odborníkom na stromy, aby ste to pochopili.

Ako použiť strom rekurzie na riešenie vzťahov s opakovaním?

Náklady na čiastkový problém v technike stromu rekurzie predstavujú množstvo času potrebného na vyriešenie čiastkového problému. Preto, ak si všimnete frázu „náklady“ spojenú so stromom rekurzie, jednoducho sa vzťahuje na množstvo času potrebného na vyriešenie určitého čiastkového problému.

ďalej skener

Poďme pochopiť všetky tieto kroky pomocou niekoľkých príkladov.

Príklad

Zvážte vzťah opakovania,

T(n) = 2T(n/2) + K

Riešenie

Daný vzťah opakovania vykazuje nasledujúce vlastnosti,

Problém veľkosti n je rozdelený na dva podproblémy, každý s veľkosťou n/2. Náklady na kombináciu riešení týchto čiastkových problémov sú K.

Každý problém veľkosti n/2 je rozdelený na dva podproblémy, každý veľkosti n/4 atď.

Na poslednej úrovni sa veľkosť čiastkového problému zníži na 1. Inými slovami, konečne sme dosiahli základný prípad.

Nasledujme kroky na vyriešenie tohto vzťahu opakovania,

Krok 1: Nakreslite strom rekurzie

pripojenia v jave

Krok 2: Vypočítajte výšku stromu

Keďže vieme, že keď priebežne delíme číslo 2, príde čas, keď sa toto číslo zníži na 1. Rovnako ako pri veľkosti problému N, predpokladajme, že po K delení číslom 2 sa N rovná 1, čo znamená, ( n/2^k) = 1

Tu n / 2^k je veľkosť problému na poslednej úrovni a vždy sa rovná 1.

Teraz môžeme ľahko vypočítať hodnotu k z vyššie uvedeného výrazu tak, že vezmeme log() na obe strany. Nižšie je jasnejší odvodenie,

previesť znak na reťazec

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) základ 2

Výška stromu je teda log (n) základňa 2.

Krok 3: Vypočítajte náklady na každej úrovni

• Náklady na úrovni 0 = K, dva čiastkové problémy sú zlúčené.
• Náklady na úrovni 1 = K + K = 2*K, dva čiastkové problémy sa zlúčia dvakrát.
• Náklady na úrovni 2 = K + K + K + K = 4*K, dva čiastkové problémy sa zlúčia štyrikrát. a tak ďalej....

Krok 4: Vypočítajte počet uzlov na každej úrovni

Najprv určme počet uzlov v poslednej úrovni. Zo stromu rekurzie to môžeme odvodiť

• Úroveň 0 má 1 (2^0) uzol
• Úroveň 1 má 2 (2^1) uzly
• Úroveň 2 má 4 (2^2) uzly
• Úroveň 3 má 8 (2^3) uzlov

Takže log(n) úrovne by mal mať 2^(log(n)) uzlov, t.j. n uzlov.

Krok 5: Zhrňte náklady na všetky úrovne

• Celkové náklady možno zapísať ako,
• Celkové náklady = náklady na všetky úrovne okrem poslednej úrovne + náklady na poslednú úroveň
• Celková cena = Cena za úroveň 0 + Cena za úroveň 1 + Cena za úroveň 2 +.... + Cena za úroveň-log(n) + Cena za poslednú úroveň

Náklady na poslednú úroveň sa vypočítavajú oddelene, pretože ide o základný prípad a na poslednej úrovni sa neuskutočňuje žiadne zlúčenie, takže náklady na vyriešenie jedného problému na tejto úrovni predstavujú určitú konštantnú hodnotu. Zoberme si to ako O (1).

Dajme hodnoty do vzorcov,

• T(n) = K + 2*K + 4*K + .... + log(n)` krát + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) krát)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) krát + O(n)

Ak sa bližšie pozriete na vyššie uvedený výraz, tvorí geometrickú postupnosť (a, ar, ar^2, ar^3 ...... nekonečný čas). Súčet GP je daný vzťahom S(N) = a / (r - 1). Tu je prvý člen a r je spoločný pomer.