A rekurzió modern megértése: a funkcionalitás meghatározása és hozzáférése kívülről és ebből a funkcióból. Úgy tartják, hogy a rekurziót a matematikusok szülték: faktorszámítás, végtelen sorozatok, fraktálok, folytonos törtek… A rekurzió azonban mindenhol megtalálható. Az objektív természeti törvények a rekurziót „tekintik” fő algoritmusuknak és kifejezési (létezési) formájuknak nem annyira az anyagi világ tárgyait, hanem általában a mozgás fő algoritmusát.
A tudomány és a technológia különböző területein különböző szakterületeken dolgozók az f (x) rekurzív algoritmust használják, ahol "x ~/=f (x)". Az önmagát meghívó függvény erős megoldás, de ennek kialakítása és megértése a legtöbb esetben nagyon nehéz feladat.
Az ókorban a rekurziót a palota terének növelésére használták. Az egymásra irányított tükrök rendszerén keresztül lenyűgöző, háromdimenziós térhatásokat hozhat létre. De vajon ilyen könnyű megérteni, hogyanbeállítani ezeket a tükröket? Még nehezebb meghatározni, hol van egy pont a térben, több tükörön keresztül visszaverve.
Rekurzió, rekurzív algoritmusok: jelentés és szintaxis
A műveletsor ismétlésével megfogalmazott probléma rekurzív módon megoldható. Egy egyszerű algoritmus (másodfokú egyenlet kiszámítása, egy weboldal információval való feltöltésére szolgáló szkript, fájl olvasása, üzenet küldése…) nem igényel rekurziót.
A rekurzív megoldást lehetővé tevő algoritmus főbb különbségei:
- van egy algoritmus, amit többször kell végrehajtani;
- algoritmusnak olyan adatokra van szüksége, amelyek minden alkalommal változnak;
- az algoritmusnak nem kell minden alkalommal változnia;
- van egy végső feltétel: az algoritmus rekurzív – nem végtelen.
Általában nem vitatható, hogy az egyszeri végrehajtás szükséges feltétele a rekurziós ok hiányának. Kötelező végső feltételt sem írhat elő: a végtelen rekurzióknak saját hatókörük van.
Az algoritmus rekurzív: amikor egy műveletsorozatot ismételten végrehajtanak, olyan adatokon, amelyek minden alkalommal változnak, és minden alkalommal új eredményt adnak.
Rekurziós képlet
A rekurzió és analógjának matematikai értelmezése a programozásban különbözik. A matematika, bár vannak a programozás jelei, de a programozás sokkal magasabb rendű matematika.
Egy jól megírt algoritmus olyan, mint a szerzője intellektusának tükre. Tábornoka programozásban a rekurziós képlet "f(x)", ahol az "x ~/=f(x)"-nek legalább két értelmezése van. Itt a "~" az eredmény hasonlósága vagy hiánya, a "=" pedig a függvény eredményének jelenléte.
Első lehetőség: adatdinamika.
- az "f(x)" függvénynek rekurzív és megváltoztathatatlan algoritmusa van;
- "x" és az "f(x)" eredmény minden alkalommal új értéket kap, az "f(x)" eredmény ennek a függvénynek az új "x" paramétere.
Második lehetőség: kóddinamika.
- Az "f(x)" függvénynek számos algoritmusa van, amelyek finomítják (elemzik) az adatokat;
- adatelemzés - a kód egy része és a kívánt műveletet végrehajtó rekurzív algoritmusok megvalósítása - a kód második része;
- az "f(x)" függvény eredménye nem.
Nincs normális eredmény. A programozás nem matematika, itt az eredménynek nem kell kifejezetten jelen lennie. A rekurzív függvény egyszerűen elemzi a helyeket és feltölti az adatbázist, vagy példányosít objektumokat a bejövő bemenet szerint.
Adatok és rekurzió
A rekurzív algoritmusok programozása nem egy faktoriális kiszámításáról szól, amelyben a függvény minden alkalommal egy adott értéket kap, amely egynél több vagy kevesebb – a megvalósítási lehetőség a fejlesztő preferenciáitól függ.
Nem számít, hogy a faktoriális "8!"algoritmus, amely szigorúan követi ezt a képletet.
Az információ feldolgozása teljesen más sorrendű "matematika". A rekurzív függvények és algoritmusok itt betűkkel, szavakkal, kifejezésekkel, mondatokkal és bekezdésekkel működnek. Minden következő szint az előzőt használja.
A bemeneti adatfolyamot számos körülmény között elemzik, de az elemzési folyamat általában rekurzív. Nincs értelme egyedi algoritmusokat írni a bemeneti adatfolyam minden változatához. Egyetlen funkciónak kell lennie. Itt a rekurzív algoritmusok példák arra, hogyan lehet a bemenetnek megfelelő kimeneti adatfolyamot létrehozni. Ez nem a rekurzív algoritmus kimenete, de ez a kívánt és szükséges megoldás.
Absztrakció, rekurzió és OOP
Az objektum-orientált programozás (OOP) és a rekurzió alapvetően különböző entitások, de tökéletesen kiegészítik egymást. Az absztrakciónak semmi köze a rekurzióhoz, de az OOP lencséjén keresztül megteremti a kontextuális rekurzió megvalósításának lehetőségét.
Például az információk elemzése folyamatban van, és a betűk, szavak, kifejezések, mondatok és bekezdések külön kiemelve vannak. Nyilvánvaló, hogy a fejlesztő gondoskodik az öt típusú objektumok példányainak létrehozásáról, és minden szinten kínál megoldást rekurzív algoritmusokra.
Eközben, ha a betűk szintjén „nincs értelme értelmet keresni”, akkor a szemantika a szavak szintjén jelenik meg. A szavakat feloszthatja igékre, főnevekre, határozókra, elöljárószavakra… Továbbléphet és meghatározhatja az eseteket.
A kifejezések szintjén a szemantika írásjelekkel és logikával egészül kiszóösszetételek. A mondatok szintjén a szemantika tökéletesebb szintje található, és egy bekezdés teljes gondolatnak tekinthető.
Az objektumorientált fejlesztés előre meghatározza a tulajdonságok és módszerek öröklődését, és azt javasolja, hogy az objektumok hierarchiáját egy teljesen absztrakt ős létrehozásával kezdjük. Ugyanakkor kétségtelenül az egyes leszármazottak elemzése rekurzív lesz, és technikai szinten sem tér el túlságosan sok pozícióban (betűk, szavak, kifejezések és mondatok). A bekezdések, akárcsak a teljes gondolatok, kiemelkedhetnek ebből a listából, de nem ezek jelentik a lényeget.
Fontos, hogy az algoritmus túlnyomó része az absztrakt ősök szintjén megfogalmazható legyen, az egyes leszármazottak szintjén az absztrakt szintről meghívott adatokkal és módszerekkel finomítva. Ebben az összefüggésben az absztrakció új távlatokat nyit a rekurzió előtt.
Az OOP történelmi jellemzői
Az OOP kétszer érkezett a szoftverek világába, bár egyes szakértők a számítási felhő, valamint az objektumokkal és osztályokkal kapcsolatos modern elképzelések megjelenését emelhetik ki az IT-technológiák fejlesztésének új fordulójaként.
Az "objektum" és az "objektív" kifejezéseket az OOP modern kontextusában általában a múlt század 50-es és 60-as éveinek tulajdonítják, de 1965-höz és a Simula, Lisp, Algol, Smalltalk megjelenéséhez kötik őket..
Abban az időben a programozás nem volt különösebben fejlett, és nem tudott megfelelően reagálni a forradalmi koncepciókra. Az ötletek és a programozási stílusok (C / C ++ és Pascal - többnyire) harca még messze volt, az adatbázisok fogalmilag még kialakultak.
A 80-as évek végén és a 90-es évek elején az objektumok megjelentek a Pascalban, és mindenki emlékezett a C / C ++ osztályaira – ez egy új érdeklődési kört jelentett az OOP iránt, és ekkor váltak az eszközök, elsősorban a programozási nyelvek csak az objektum-orientált ötleteket támogatja, de ennek megfelelően fejlődik.
Természetesen, ha a korábbi rekurzív algoritmusok csak a program általános kódjában használt függvények voltak, most a rekurzió egy objektum (osztály) tulajdonságainak részévé válhatott, ami érdekes lehetőségeket kínált az öröklődés összefüggésében.
A modern OOP jellemzője
Az OOP fejlesztése kezdetben adat- és tulajdonsággyűjteményként deklarált objektumok (osztályok) (metódusok). Valójában olyan adatokról volt szó, amelyeknek van szintaxisa és jelentése. De akkor nem lehetett bemutatni az OOP-t valós objektumok kezelésére szolgáló eszközként.
Az OOP a "számítógépes jellegű" objektumok kezelésének eszközévé vált. Egy script, egy gomb, egy menüelem, egy menüsor, egy címke a böngészőablakban egy objektum. De nem gépet, élelmiszerterméket, szót vagy mondatot. A valódi objektumok kívül maradtak az objektumorientált programozáson, és a számítógépes eszközök új inkarnációt kaptak.
A népszerű programozási nyelvek közötti különbségek miatt az OOP számos dialektusa megjelent. Szemantikailag gyakorlatilag egyenértékűek, és az instrumentális szférára, és nem az alkalmazottra való fókuszálásuk lehetővé teszi, hogy a valós tárgyak leírását túlmutassuk.algoritmusokat, és biztosítsák azok többplatformos és többnyelvű „létezését”.
Veremek és függvényhívási mechanizmusok
A függvények (eljárások, algoritmusok) meghívására szolgáló mechanizmusok megkövetelik az adatok (paraméterek) átadását, az eredmény visszaadását és az operátor címének emlékezését, amelynek a függvény (eljárás) befejezése után a vezérlést meg kell kapnia.
Általában a verem használatos erre a célra, bár a programozási nyelvek vagy maga a fejlesztő számos lehetőséget kínálhat a vezérlés átadására. A modern programozás elismeri, hogy egy függvény neve nem csak paraméter lehet, hanem az algoritmus végrehajtása során is kialakulhat. Egy algoritmus egy másik algoritmus végrehajtása közben is létrehozható.
A rekurzív algoritmusok fogalma, amikor a nevük és testük meghatározható a feladat kialakításakor (a kívánt algoritmus kiválasztásakor), a rekurzivitást nem csak arra terjeszti ki, hogy hogyan kell valamit csinálni, hanem arra is, hogy pontosan kinek kell csináld. Az algoritmus „értelmes” neve alapján történő kiválasztása ígéretes, de nehézségeket okoz.
Rekurzivitás egy függvénykészleten
Nem mondhatod, hogy egy algoritmus rekurzív, ha meghívja magát, és ennyi. A programozás nem dogma, és a rekurzivitás fogalma nem kizárólagos követelmény ahhoz, hogy a saját algoritmusod törzséből hívd magad.
A gyakorlati alkalmazások nem mindig adnak tiszta megoldást. Gyakran elő kell készíteni a kezdeti adatokat, és a rekurzív hívás eredményét a teljes probléma (a teljes algoritmus) összefüggésében elemezni kell.összességében.
Valójában nem csak egy rekurzív függvény meghívása előtt, hanem annak befejezése után is egy másik programot lehet vagy kell meghívni. Ha nincs különösebb probléma a hívással: az A() rekurzív függvény meghívja a B() függvényt, ami csinál valamit, és meghívja az A(-t), akkor azonnal gond van a vezérlés visszaadásával. A rekurzív hívás befejezése után az A() függvénynek vezérlést kell kapnia ahhoz, hogy újra meghívhassa a B() függvényt, amely újra meghívja. A vezérlés visszaadása sorrendben a veremben B()-be rossz megoldás.
A programozó nem korlátozza a paraméterek kiválasztását, és kiegészítheti azokat függvénynevekkel. Más szóval, az ideális megoldás az, ha a B() nevét átadjuk A()-nak, és hagyjuk, hogy A() maga hívja B()-t. Ebben az esetben nem lesz probléma a vezérlés visszaadásával, és a rekurzív algoritmus megvalósítása átláthatóbb lesz.
A rekurzió megértése és szintje
A rekurzív algoritmusok fejlesztésével az a probléma, hogy meg kell értened a folyamat dinamikáját. Ha rekurziót használunk objektummetódusokban, különösen az absztrakt ősök szintjén, probléma adódik a saját algoritmusunk végrehajtási idejének megértésében.
Jelenleg nincs korlátozás a függvények egymásba ágyazási szintjére és a veremkapacitásra a hívási mechanizmusokban, de probléma van a megértéssel: melyik időpontban melyik adatszintet vagy az általános algoritmus melyik helyét nevezik rekurzívnak. funkciót, és hány hívást kezdeményez.
A meglévő hibakereső eszközök gyakran tehetetlenekmondd el a programozónak a helyes megoldást.
Hurkok és rekurzió
A ciklikus végrehajtás egyenértékű a rekurzióval. Valójában bizonyos esetekben a rekurzív algoritmus megvalósítható feltételes és ciklikus konstrukciók szintaxisában.
Ha azonban világosan megértjük, hogy egy adott függvényt rekurzív algoritmuson keresztül kell megvalósítani, a hurok vagy feltételes utasítások bármilyen külső használatát fel kell hagyni.
Ez azt jelenti, hogy egy önmagát használó függvény formájában megjelenő rekurzív megoldás egy teljes, funkcionálisan teljes algoritmus lesz. Ez az algoritmus megköveteli, hogy a programozó erőfeszítéssel hozza létre, megértve az algoritmus dinamikáját, de ez lesz a végső megoldás, amely nem igényel külső vezérlést.
A külső feltételes és ciklikus operátorok bármilyen kombinációja nem teszi lehetővé, hogy a rekurzív algoritmust teljes függvényként ábrázoljuk.
Rekurziós konszenzus és OOP
A rekurzív algoritmus fejlesztésének szinte minden változatában felmerül a terv két algoritmus kidolgozására. Az első algoritmus létrehozza a jövőbeli objektumok (példányok) listáját, a második algoritmus pedig valójában egy rekurzív függvény.
A legjobb megoldás az lenne, ha a rekurziót egyetlen tulajdonságként (metódusként) rendeznénk el, amely ténylegesen tartalmazza a rekurzív algoritmust, és az összes előkészítő munkát az objektumkonstruktorba helyezzük.
A rekurzív algoritmus csak akkor lesz a megfelelő megoldás, ha működikcsak egyedül, külső ellenőrzés és irányítás nélkül. Egy külső algoritmus csak jelzést adhat a működésre. A munka eredménye a várt megoldás legyen, külső támogatás nélkül.
A rekurziónak mindig teljes, önálló megoldásnak kell lennie.
Intuitív megértés és funkcionális teljesség
Amikor az objektumorientált programozás de facto szabvánnyá vált, nyilvánvalóvá vált, hogy a hatékony kódoláshoz meg kell változtatni a saját gondolkodásodat. A programozónak az algoritmus végrehajtása során a nyelv szintaxisától és szemantikájától a szemantika dinamikájáig kell elmozdulnia.
A rekurzió jellemzője: mindenre alkalmazható:
- webkaparás;
- keresési műveletek;
- szöveginformációk elemzése;
- MS Word dokumentumok olvasása vagy létrehozása;
- címkék mintavétele vagy elemzése…
Az OOP jellemzője: lehetővé teszi egy rekurzív algoritmus leírását az absztrakt ősök szintjén, de gondoskodik arról, hogy egyedi leszármazottokra hivatkozzon, amelyek mindegyikének saját adat- és tulajdonságpalettája van.
A rekurzió ideális, mert megköveteli az algoritmus funkcionális teljességét. Az OOP javítja a rekurzív algoritmus teljesítményét azáltal, hogy hozzáférést biztosít az összes egyedi gyermekhez.
