Moderné chápanie rekurzie: definícia funkcionality a prístup k nej zvonku a z tejto funkcionality. Verí sa, že rekurziu zrodili matematici: faktoriálny výpočet, nekonečné rady, fraktály, reťazové zlomky… Rekurziu však možno nájsť všade. Objektívne prírodné zákony „považujú“rekurziu za svoj hlavný algoritmus a formu vyjadrenia (existencie) ani nie tak objektov hmotného sveta, ale vo všeobecnosti za hlavný algoritmus pohybu.
Ľudia rôznych špecializácií v rôznych oblastiach vedy a techniky používajú rekurzívny algoritmus f (x), kde "x ~/=f (x)". Funkcia, ktorá volá sama seba, je silné riešenie, ale vytvorenie a pochopenie tohto riešenia je vo väčšine prípadov veľmi náročná úloha.
V staroveku sa na zväčšenie priestoru paláca používala rekurzia. Prostredníctvom systému zrkadiel nasmerovaných na seba môžete vytvárať úžasné trojrozmerné priestorové efekty. Ale je také ľahké pochopiť akonastaviť tieto zrkadlá? Ešte ťažšie je určiť, kde sa nachádza bod v priestore, ktorý sa odráža cez niekoľko zrkadiel.
Rekurzia, rekurzívne algoritmy: význam a syntax
Problém, ktorý je formulovaný opakovaním postupnosti operácií, možno riešiť rekurzívne. Jednoduchý algoritmus (výpočet kvadratickej rovnice, skript na vyplnenie webovej stránky informáciami, čítanie súboru, odoslanie správy…) nevyžaduje rekurziu.
Hlavné rozdiely v algoritme, ktorý umožňuje rekurzívne riešenie:
- existuje algoritmus, ktorý je potrebné vykonať niekoľkokrát;
- algoritmus potrebuje údaje, ktoré sa zakaždým menia;
- algoritmus sa nemusí zakaždým meniť;
- existuje posledná podmienka: algoritmus je rekurzívny – nie nekonečný.
Vo všeobecnosti nemožno tvrdiť, že jednorazové vykonanie je nevyhnutnou podmienkou absencie dôvodu na rekurziu. Nemôžete tiež vyžadovať povinnú konečnú podmienku: nekonečné rekurzie majú svoj vlastný rozsah.
Algoritmus je rekurzívny: keď sa sekvencia operácií vykonáva opakovane s údajmi, ktoré sa zakaždým menia a zakaždým poskytujú nový výsledok.
Rekurzný vzorec
Matematické chápanie rekurzie a jej analógie v programovaní sú odlišné. Matematika, aj keď existujú znaky programovania, ale programovanie je matematika oveľa vyššieho rádu.
Dobre napísaný algoritmus je ako zrkadlo intelektu svojho autora. generálrekurzný vzorec v programovaní je "f(x)", kde "x ~/=f(x)" má aspoň dve interpretácie. Tu je "~" podobnosť alebo absencia výsledku a "=" je prítomnosť výsledku funkcie.
Prvá možnosť: dynamika údajov.
- funkcia "f(x)" má rekurzívny a nemenný algoritmus;
- "x" a výsledok "f(x)" majú zakaždým nové hodnoty, výsledok "f(x)" je nový parameter "x" tejto funkcie.
Druhá možnosť: dynamika kódu.
- funkcia "f(x)" má niekoľko algoritmov, ktoré spresňujú (analyzujú) údaje;
- analýza údajov - jedna časť kódu a implementácia rekurzívnych algoritmov, ktoré vykonajú požadovanú akciu - druhá časť kódu;
- výsledok funkcie "f(x)" nie je.
Žiadny výsledok nie je normálny. Programovanie nie je matematika, tu výsledok nemusí byť vyslovene prítomný. Rekurzívna funkcia môže jednoducho analyzovať stránky a naplniť databázu alebo vytvoriť inštanciu objektov podľa prichádzajúceho vstupu.
Údaje a rekurzia
Programovanie rekurzívnych algoritmov nie je o výpočte faktoriálu, v ktorom funkcia dostane zakaždým danú hodnotu, ktorá je o jedna väčšia alebo menšia ako jedna – možnosť implementácie závisí od preferencií vývojára.
Nezáleží na tom, ako faktoriál „8!“,algoritmus, ktorý presne dodržiava tento vzorec.
Spracovanie informácií je „matematika“úplne iného poriadku. Rekurzívne funkcie a algoritmy tu pracujú s písmenami, slovami, frázami, vetami a odsekmi. Každá ďalšia úroveň používa predchádzajúcu.
Vstupný dátový tok sa analyzuje v širokom rozsahu podmienok, ale proces analýzy je vo všeobecnosti rekurzívny. Nemá zmysel písať jedinečné algoritmy pre všetky varianty vstupného toku. Mala by existovať jedna funkcia. Tu sú rekurzívne algoritmy príkladmi toho, ako vytvoriť výstupný tok, ktorý je adekvátny vstupu. Toto nie je výstup rekurzívneho algoritmu, ale je to požadované a potrebné riešenie.
Abstrakcia, rekurzia a OOP
Objektovo orientované programovanie (OOP) a rekurzia sú zásadne odlišné entity, ktoré sa však dokonale dopĺňajú. Abstrakcia nemá nič spoločné s rekurziou, ale cez optiku OOP vytvára možnosť implementácie kontextovej rekurzie.
Informácie sa napríklad analyzujú a písmená, slová, frázy, vety a odseky sú zvýraznené oddelene. Je zrejmé, že vývojár zabezpečí vytváranie inštancií objektov týchto piatich typov a ponúkne riešenie rekurzívnych algoritmov na každej úrovni.
Zatiaľ, ak na úrovni písmen „nemá zmysel hľadať význam“, potom sa sémantika objaví na úrovni slov. Slová môžete rozdeliť na slovesá, podstatné mená, príslovky, predložky… Môžete ísť ďalej a definovať prípady.
Na úrovni fráz je sémantika doplnená o interpunkčné znamienka a logikuslovné spojenia. Na úrovni viet sa nachádza dokonalejšia úroveň sémantiky a odsek možno považovať za úplnú myšlienku.
Objektovo orientovaný vývoj predurčuje dedenie vlastností a metód a navrhuje začať hierarchiu objektov vytvorením úplne abstraktného predka. Zároveň bude nepochybne analýza každého potomka rekurzívna a nebude sa na technickej úrovni príliš líšiť v mnohých polohách (písmená, slová, frázy a vety). Odseky, ako napríklad úplné myšlienky, môžu z tohto zoznamu vyčnievať, ale nie sú podstatou.
Je dôležité, aby drvivá časť algoritmu mohla byť formulovaná na úrovni abstraktného predchodcu a spresniť ju na úrovni každého potomka pomocou údajov a metód volaných z abstraktnej úrovne. V tomto kontexte abstrakcia otvára nové obzory pre rekurziu.
Historické prvky OOP
OOP prišiel do sveta softvéru dvakrát, hoci niektorí odborníci môžu označiť vznik cloud computingu a moderných myšlienok o objektoch a triedach ako nové kolo vo vývoji IT technológií.
Pojmy „objekt“a „cieľ“sa v modernom kontexte OOP zvyčajne pripisujú 50. a 60. rokom minulého storočia, ale spájajú sa s rokom 1965 a vznikom Simula, Lisp, Algol, Smalltalk.
V tých časoch nebolo programovanie zvlášť vyvinuté a nemohlo adekvátne reagovať na revolučné koncepty. Boj nápadov a programovacích štýlov (C/C++ a Pascal – väčšinou) bol ešte ďaleko a databázy sa stále tvorili koncepčne.
Koncom 80-tych a začiatkom 90-tych rokov sa objekty objavili v Pascale a každý si pamätal triedy v C/C++ – to znamenalo nové kolo záujmu o OOP a práve vtedy sa nástroje, predovšetkým programovacie jazyky, prestali používať podporovať iba objektovo orientované nápady, ale podľa toho sa vyvíjať.
Samozrejme, ak predchádzajúce rekurzívne algoritmy boli iba funkciami používanými vo všeobecnom kóde programu, teraz by sa rekurzia mohla stať súčasťou vlastností objektu (triedy), čo poskytovalo zaujímavé príležitosti v kontexte dedenia.
Funkcia moderného OOP
Vývoj OOP pôvodne deklaroval objekty (triedy) ako kolekcie údajov a vlastností (metód). V skutočnosti išlo o údaje, ktoré majú syntax a význam. Potom však nebolo možné prezentovať OOP ako nástroj na správu skutočných objektov.
OOP sa stal nástrojom na správu objektov „počítačovej povahy“. Skript, tlačidlo, položka ponuky, panel s ponukami, značka v okne prehliadača je objekt. Ale nie stroj, potravinový výrobok, slovo alebo veta. Skutočné objekty zostali mimo objektovo orientovaného programovania a počítačové nástroje nadobudli novú inkarnáciu.
V dôsledku rozdielov v populárnych programovacích jazykoch sa objavilo mnoho dialektov OOP. Z hľadiska sémantiky sú prakticky ekvivalentné a ich zameranie na inštrumentálnu sféru a nie na aplikovanú sféru umožňuje preniesť popis skutočných objektov nad rámecalgoritmy a zabezpečiť ich „existenciu“medzi platformami a jazykmi.
Zásobníky a mechanizmy volania funkcií
Mechanizmy na volanie funkcií (procedúry, algoritmy) vyžadujú odovzdanie údajov (parametrov), vrátenie výsledku a zapamätanie si adresy operátora, ktorý musí dostať kontrolu po dokončení funkcie (procedúry).
Na tento účel sa zvyčajne používa zásobník, hoci programovacie jazyky alebo samotný vývojár môžu poskytnúť rôzne možnosti na prenos kontroly. Moderné programovanie pripúšťa, že názov funkcie môže byť nielen parametrom, ale môže byť vytvorený počas vykonávania algoritmu. Algoritmus možno vytvoriť aj pri vykonávaní iného algoritmu.
Koncept rekurzívnych algoritmov, keď ich mená a telá možno určiť v čase tvorby úlohy (výberom požadovaného algoritmu), rozširuje rekurzívnosť nielen na to, ako niečo urobiť, ale aj na to, kto presne by mal urob to. Výber algoritmu podľa jeho „zmysluplného“názvu je sľubný, no vytvára ťažkosti.
Rekurzivita na množine funkcií
Nemôžete povedať, že algoritmus je rekurzívny, keď volá sám seba, a to je všetko. Programovanie nie je dogma a koncept rekurzívnosti nie je výhradnou požiadavkou na to, aby ste sa volali z tela vášho vlastného algoritmu.
Praktické aplikácie nie vždy poskytujú čisté riešenie. Často sa musia pripraviť počiatočné údaje a výsledok rekurzívneho volania sa musí analyzovať v kontexte celého problému (celého algoritmu) vcelkovo.
V skutočnosti nielen pred volaním rekurzívnej funkcie, ale aj po jej dokončení môže alebo by mal byť zavolaný iný program. Ak s volaním nie sú žiadne špeciálne problémy: rekurzívna funkcia A() volá funkciu B(), ktorá niečo urobí a zavolá A(), tak okamžite nastáva problém s návratom kontroly. Po dokončení rekurzívneho volania musí funkcia A() dostať kontrolu, aby mohla znova zavolať B(), ktorá ju zavolá znova. Vrátenie kontroly tak, ako by malo byť v poradí, späť na B() je nesprávne riešenie.
Programátor nie je obmedzený vo výbere parametrov a môže ich doplniť názvami funkcií. Inými slovami, ideálnym riešením je odovzdať meno B() A() a nechať A() samo volať B(). V tomto prípade nebudú žiadne problémy s vrátením kontroly a implementácia rekurzívneho algoritmu bude transparentnejšia.
Porozumenie a úroveň rekurzie
Problém pri vývoji rekurzívnych algoritmov je v tom, že musíte pochopiť dynamiku procesu. Pri použití rekurzie v objektových metódach, najmä na úrovni abstraktného predka, vzniká problém porozumieť vlastnému algoritmu v kontexte času jeho vykonávania.
V súčasnosti neexistujú žiadne obmedzenia týkajúce sa úrovne vnorenia funkcií a kapacity zásobníka v mechanizmoch volania, ale existuje problém s pochopením: v akom časovom bode ktorá úroveň údajov alebo ktoré miesto vo všeobecnom algoritme nazývanom rekurzívny funkciu a na akom počte hovorov ona sama je.
Existujúce nástroje na ladenie sú často bezmocnépovedzte programátorovi správne riešenie.
Slučky a rekurzia
Cyklické vykonávanie sa považuje za ekvivalent rekurzie. V niektorých prípadoch môže byť rekurzívny algoritmus implementovaný do syntaxe podmienených a cyklických konštruktov.
Ak je však jasné, že konkrétna funkcia musí byť implementovaná prostredníctvom rekurzívneho algoritmu, malo by sa upustiť od akéhokoľvek externého použitia cyklu alebo podmienených príkazov.
Tu znamená, že rekurzívne riešenie vo forme funkcie, ktorá používa samu seba, bude úplným, funkčne úplným algoritmom. Tento algoritmus bude vyžadovať, aby ho programátor vytvoril s úsilím, porozumel dynamike algoritmu, ale bude to konečné riešenie, ktoré nevyžaduje externú kontrolu.
Akákoľvek kombinácia externých podmienených a cyklických operátorov nám nedovolí reprezentovať rekurzívny algoritmus ako úplnú funkciu.
Rekurzný konsenzus a OOP
V takmer všetkých variantoch vývoja rekurzívneho algoritmu vzniká plán vyvinúť dva algoritmy. Prvý algoritmus generuje zoznam budúcich objektov (inštancií) a druhý algoritmus je vlastne rekurzívna funkcia.
Najlepším riešením by bolo usporiadať rekurziu ako jedinú vlastnosť (metódu), ktorá v skutočnosti obsahuje rekurzívny algoritmus, a vložiť všetky prípravné práce do konštruktora objektu.
Rekurzívny algoritmus bude tým správnym riešením len vtedy, keď bude fungovaťlen sám sebou, bez vonkajšej kontroly a riadenia. Externý algoritmus môže dať iba signál, aby fungoval. Výsledkom tejto práce by malo byť očakávané riešenie bez externej podpory.
Rekurzia by mala byť vždy úplným samostatným riešením.
Intuitívne porozumenie a funkčná úplnosť
Keď sa objektovo orientované programovanie stalo de facto štandardom, bolo zrejmé, že ak chcete efektívne kódovať, musíte zmeniť svoje vlastné myslenie. Programátor musí prejsť od syntaxe a sémantiky jazyka k dynamike sémantiky počas vykonávania algoritmu.
Charakteristika rekurzie: dá sa použiť na všetko:
- web scraping;
- operácie vyhľadávania;
- parsing text information;
- čítanie alebo vytváranie dokumentov MS Word;
- vzorkovanie alebo analýza značiek…
Charakteristika OOP: umožňuje opísať rekurzívny algoritmus na úrovni abstraktného predka, ale umožňuje mu odkazovať na jedinečných potomkov, z ktorých každý má svoju vlastnú paletu údajov a vlastností.
Rekurzia je ideálna, pretože vyžaduje funkčnú úplnosť svojho algoritmu. OOP zlepšuje výkon rekurzívneho algoritmu tým, že mu poskytuje prístup ku všetkým jedinečným deťom.
