A rekurzió olyan folyamat, amely a folyamat tárgyára utal a folyamat egy pontjára. Más szavakkal, ez egy olyan megközelítés, amelynek leírása ugyanazon szabály megismétléséhez vezet. Így a következő esetek a rekurzió konkrét esetei:
A számítástechnikában bizonyos adatszerkezetek , például listák vagy fák meghatározása rekurzív: megemlíti a meghatározandó adatok típusát. Például (lásd az ábrát) egy bináris fa vagy üres, vagy egy csomópont két kisebb bináris fával .
Ezenkívül egy függvény vagy általánosabban egy algoritmus tartalmazhat egy vagy több hívást önmagához, ebben az esetben rekurzívnak mondják . Ezt a módszert különösen rekurzív adatstruktúrák feldolgozására, valamint az „ oszd meg és hódítsd ” algoritmikus paradigma megvalósítására alkalmazzuk .
Kétféle adat utalhat egymásra; hasonlóan két algoritmus hívhatja egymást. Ezután keresztrekurzióról vagy kölcsönös rekurzióról beszélünk .
A hurkok használatához hasonlóan a rekurzió lehetővé teszi számos olyan művelet végrehajtását, amelyek nem ismertek előre, mert a program bemenetei határozzák meg; ez a két módszer lehetővé teszi olyan programok írását is, amelyek nem szűnnek meg . A ciklusokat lehetővé tevő nyelv , csakúgy, mint a rekurziót lehetővé tevő nyelv, általában Turing-teljes .
A rekurzió kényes pont a számítástechnika oktatásában, mert annak elősegítése a tanuló által egy adag absztrakciót igényel.
Egy angol mondás így szól: " Az iterálás emberi, a visszatérés isteni ". Franciaul fordíthatjuk úgy, hogy "az iteráció emberi, de a rekurzió isteni"
A neves amerikai nyelvész, Noam Chomsky többek között azzal érvel, hogy a nyelvtani mondatok számának és hosszának felső korlátjának hiánya (a gyakorlatiasság területén belül maradva) a természetes nyelv megismétlődésének eredménye.
Ezt egy szintaktikai kategória, például egy mondat rekurzív meghatározásával értjük meg. A mondatnak olyan szerkezete lehet, amelyben egy beágyazott mondat található az ige után: Dorothy szerint a boszorkányok veszélyesek , amelyben a boszorkányok veszélyesek a már meglévő mondatban. Tehát egy mondatot rekurzívan (nagyjából) definiálhatunk úgy, mint amelynek szerkezete tartalmaz főnévi mondatot, igét és egy másik (választható) mondatot. Ez valóban egy különleges eset, amikor a rekurzió matematikai meghatározása nyilvánul meg.
A rekurzió fontos szerepet játszik nemcsak a szintaxisban, hanem a természetes nyelv szemantikájában is . A szó, és például funkcióként tekinthető, amely a mondatok jelentésére alkalmazható új mondatok létrehozására. Ez a nominális mondatok jelentéseire is kiterjed, többek között a verbális formák között. Ez vonatkozik a transzitív, intranzitív vagy éppen ditransitív igékre is. Annak érdekében, hogy ez egyetlen kellően rugalmas denotáció, és úgy definiáljuk egészen egyszerűen, mint amelyek a lehetőségét képviselő érvek bármilyen értelmes formában. Ezt meg lehet tenni meghatározásával és egy egyszerű eset, amelyben ötvözzük mondat, majd meghatározzák a többi esetben rekurzív szempontjából az egyszerű esetet.
A nyelvtan a szanszkrit a Panini már használja rekurziót V th század ie. Kr. Az épületek lényegében rekurzív nyelvek, például a főnév építése: a ház bejárati ajtajának zárjának kulcsa a falu végének utcájából . Daniel Everett professzor által végzett munka azonban azt mutatja, hogy a pirahã nyelven nincs rekurzió .
Egyes szerzők úgy vélték, hogy a rekurzív struktúrák felépítésének képessége az emberi kommunikációs rendszerekre jellemző, de ezt az állítást az állatok megismerésére irányuló munka megkérdőjelezi.
A szótár (definíciós szótár) a rekurzió példája: a szótár minden egyes szavát más szavak határozzák meg, amelyeket önmagukban ugyanazon szótár más szavai határoznak meg.
A művészetek terén a rekurzív folyamatot mise en abîme-nak hívják, és Maurits Cornelis Escher művész használja ki a legnagyobb mértékben; rekurziós ihletésű műveiről ismert. A reklám a maga részéről rekurziót is használt, így a La vache qui rit és a Dubonnet híressé vált Franciaországban .
A rekurzió különösen a biológiában van jelen , különösen a növényi mintákban és a fejlődési folyamatokban. A kovaféléknek különösen szép rekurzív szerkezete van.
Egy napraforgó virág.
Központi kovafélék.
A nautilus héj nyilas szakasza .
A függvény önmagában meghatározható. Ismert példa a Fibonacci-szekvencia , amelyet függvénynek tekintünk , ti . Ahhoz, hogy egy ilyen definíciónak jelentése legyen, azonnal értékelhető értékekhez kell vezetnie: az általunk beállított Fibonacci-szekvencia esetén és .
A Koch hópehely egy fraktál figura, egyszerű rekurziós eljárással.
A kezdeti szakaszban egyenlő oldalú háromszögünk van. A következő lépés három egyenlő oldalú háromszög felépítése, amely a kezdeti háromszög mindkét oldalának középső harmadát veszi alapul. Ha először megismétli ezt a folyamatot a három új háromszögnél, majd ahányszor csak akarja, megkapja a Koch hópelyhét.
Definiálása fogalom önmagában is nevezik logikusok matematikusok és unpredicativeness és nem szabad összetéveszteni a rekurzió, bár hasonlít rá. Mi is beszélünk önreferencia . Vannak logikai unpredicative elméletek (mint az F-rendszer miatt Jean-Yves Girard ), de meg kell határozni az ellátás, ha azt akarjuk, hogy megőrizzék a koherenciát, mivel a paradoxonok nem messze. Így a halmazelméletben Russell paradoxona azt mutatja, hogy nem létezhet olyan készlet, amely nem tartalmazza önmagukat (a borbély paradoxonaként népszerűsítve, valójában "ha a borbély borotválja azokat, akik nem borotválkoznak, akik borotválkoznak a fodrász? ”). Még mindig a halmazelméletben az alapozás axiómája előírja azokat a halmazokat, amelyek magukban tartalmazzák.
Ezen az alapelven kell játszani, hogy az ügyes informatikusok rekurzív rövidítéseket határoztak meg, amelyek semmit sem határoznak meg, mivel kiszámíthatatlanok és következetlenek. Hasonlóképpen a következő aforizma: "A rekurzió elvének megértéséhez először meg kell értenünk a rekurzió elvét" , kiszámíthatatlan és a törvényjavaslat könyörgésének tekinthető .
Edgar Morin nagyon gyakran használják a koncepció rekurzió, amely azt kéri rekurzív hurok , különösen műveiben alkotó a módszer . A rekurzív hurok körkörös oksági összefüggést mutat: a következmény a hatás okára hat. Az idegsejtek plaszticitásából és a szinaptikus plaszticitásból álló agyplaszticitás a rekurzív hurok példája. Például: az agy képes arra, hogy a komplex mozgás (golflengés) első tanulása során szabályozza a különböző kontrollizmok sorrendjét. A gesztus megismétlése módosítja az idegi és a szinaptikus hálózatokat, amelyek így képesek új képességekre: a gesztusok megtanulására a labda számára adott effektusokhoz.
" A rekurzió szervezeti elve túlmutat a visszacsatolás ( visszacsatolás ) elvén ; túlmutat az öntermelés és az önszerveződés szabályozásának fogalmán . Ez egy generatív hurok, amelyben a termékek és a hatások maguk is előidézői és okozói annak, ami előállítja őket. […] Az emberi egyének interakcióikban és interakcióik révén termelik a társadalmat, de a társadalom, mint feltörekvő egész , az egyének emberségét úgy állítja elő, hogy nyelvet és kultúrát biztosít számukra ” .
A 6 -én opus A módszer , Edgar Morin javasolja etikai rekurzió.
„Az önvizsgálat, az önkritika és a pszichés torna egybeesik azzal a rekurzív gyakorlattal, amikor értékeléseinket értékeljük, megítéljük ítéleteinket, kritikáinkat kritizáljuk. […]
Az etikai rekurzió hurkolja a megértést / magyarázatot is (azaz objektív / szubjektív vizsgálatot): minden magyarázatot értéssel kell kiegészíteni, minden megértést magyarázattal kell kiegészíteni.
Végül az etikai rekurzió immunológiailag megerősít bennünket azzal a hajlamunkkal szemben, hogy másokat bűnösnek érezzünk, és hibáink bűnbakjává válunk ”.