Rekurzió

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 19-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A rekurzió egy tárgy vagy folyamat definíciója, leírása, képe ezen az objektumon vagy folyamaton belül, vagyis az a helyzet, amikor az objektum önmaga része. A "rekurzió" kifejezést a tudás különféle speciális területein használják - a nyelvészettől a logikáig , de a legszélesebb körben a matematikában és a számítástechnikában alkalmazzák .

A matematikában

A matematikában a rekurzió a függvények, számsorok meghatározásának módszerét jelenti: egy rekurzívan adott függvény úgy határozza meg az értékét, hogy más argumentumokkal önmagára hivatkozik. Ebben az esetben két lehetőség közül választhat:

Végső rekurzív függvény. Úgy van beállítva, hogy bármely véges argumentum esetén véges számú rekurzív hívás után a külön definiált speciális esetek valamelyikéhez vezet, amelyek rekurzió nélkül kerülnek kiértékelésre. Klasszikus példa: egy nemnegatív egész szám rekurzívan definiált faktoriálisa : . Itt minden további rekurzív hívás egynél kisebb argumentummal történik. Mivel n definíció szerint nemnegatív egész szám, n rekurzív hívás után a függvény kiértékelése garantáltan olyan speciális esetbe kerül, amikor a rekurzió leáll. Így a definíció rekurzivitása ellenére a függvény számítása a definíciós tartomány bármely argumentumára véges lesz. $n!=\begin{cases}n\cdot(n-1)!,&n>0\\1,&n=0\end{cases}$ $0!=1$
Végtelen rekurzív függvény. Minden esetben (legalábbis néhány érvnél) önmagára való hivatkozásként adják meg. Hasonló módon adhatók meg a végtelen sorozatok, a végtelen folyamatos törtek és így tovább. A pontos érték gyakorlati kiszámítása itt természetesen lehetetlen, mivel ez végtelen időt igényel. A kívánt eredményt analitikai módszerekkel találjuk meg. Mindazonáltal, ha nem abszolút pontos érték megszerzéséről beszélünk, hanem a kívánt érték adott közelítéséről, akkor bizonyos esetekben közvetlenül is használható a rekurzív definíció: a számításokat addig végezzük, amíg a kívánt pontosságot el nem érjük. elérte. Példa erre az e szám folyamatos törtbővítése :

e = 2+\cfrac{2}{2+\cfrac{3}{3+\cfrac{4}{4+\lpont}}}\; = 2+f(2)

, ahol

f(n)=\cfrac{n}{n+f(n+1)}

A fenti képlet szerinti közvetlen számítás végtelen rekurziót okoz, de bebizonyítható, hogy f (n) értéke egységre hajlik n növekedésével (tehát a sorozat végtelensége ellenére az Euler-szám értéke véges) . Az e értékének hozzávetőleges kiszámításához elegendő mesterségesen korlátozni a rekurziós mélységet valamilyen előre meghatározott számra, és annak elérésekor helyette egyet használni.

f(n)

Egy másik példa a matematikában a rekurzióra egy rekurzív képlettel megadott számsorozat , ahol a sorozat minden egymást követő tagját az n előző tag függvényének eredményeként számítjuk ki. Így egy véges kifejezés segítségével (amely egy rekurzív képlet és egy sorozat első n tagjának értékkészletének kombinációja) végtelen sorozat definiálható.

A rekurzióval szorosan összefügg a matematikai indukció : természetes módja a függvények tulajdonságainak bizonyításának természetes számokon , amelyek rekurzív módon adják meg kisebb értékeiket.

A matematikában az úgynevezett "primitíven rekurzív" függvények osztályát külön vizsgálják. A primitív rekurzív függvény definíciója is rekurzív, primitív függvények halmazát és szabályhalmazt határoz meg; egy függvény primitív rekurzív, ha e szabályok szerint képzett primitív rekurzív függvények kombinációjaként ábrázolható.

Példák a rekurzióra a matematikában:

A Gauss-Jordan módszer lineáris algebrai egyenletrendszerek megoldására rekurzív.
Nemnegatív egész szám már említett faktoriálisa.
A Fibonacci-számokat az ismétlődési reláció segítségével határozzuk meg : Az első és a második Fibonacci-szám 1 -e esetén a Fibonacci-szám egyenlő a -edik és -edik Fibonacci-szám összegével $n>2$ $n$ $(n-1)$ $(n-2)$
Szinte minden geometriai fraktál végtelen rekurzió formájában van megadva (például a Sierpinski-háromszög ).
A nem primitív rekurzív kiszámítható rekurzív függvény szabványos példája az Ackermann -függvény : nemnegatív egész számokhoz és a következők szerint: $m$ $n$

A(m,\;n)=\begin{esetek}n+1,&m=0;\\A(m-1,\;1),&m>0,\;n=0;\\A(m -1,\;A(m,\;n-1)),&m>0,\;n>0.\end{esetek}

A programozásban

Funkciók

A programozásban a rekurzió egy függvény ( eljárás ) hívása önmagából közvetlenül ( egyszerű rekurzió ) vagy más függvényeken keresztül ( komplex vagy közvetett rekurzió ), például egy függvény függvényt hív meg , a függvény pedig függvényt . A beágyazott függvény- vagy eljáráshívások számát rekurziós mélységnek nevezzük. A rekurzív program lehetővé teszi egy ismétlődő vagy akár potenciálisan végtelen számítás leírását a program részeinek kifejezett ismétlődése és ciklusok használata nélkül. $A$ $B$ $B$ $A$

A strukturálisan rekurzív függvény a legfelső szinten mindig egy elágazási utasítás (két vagy több alternatíva közül egy kiválasztása a feltétel(ek)től függően, ami ebben az esetben a "rekurziós lezárási feltétel" hívása, kettő vagy több alternatív ágak, amelyek közül legalább egy rekurzív és legalább egy terminál . A rekurzív ág akkor kerül végrehajtásra, ha a rekurzió befejezési feltétele hamis, és legalább egy rekurzív hívást tartalmaz – a függvény közvetlen vagy közvetett hívása önmagának. A terminálág akkor kerül végrehajtásra, ha a rekurzió befejezési feltétele igaz; rekurzív hívás nélkül ad vissza valamilyen értéket. Egy jól megírt rekurzív függvénynek biztosítania kell, hogy véges számú rekurzív hívás után elérje a rekurzió befejezési feltételét, aminek következtében az egymást követő rekurzív hívások lánca megszakad és visszatér.

Azon függvényeken kívül, amelyek minden rekurzív ágon egy rekurzív hívást hajtanak végre, vannak "párhuzamos rekurziós" esetek, amikor két vagy több rekurzív hívás történik ugyanazon a rekurzív ágon. A párhuzamos rekurzió jellemző összetett adatszerkezetek, például fák feldolgozásakor. A párhuzamos-rekurzív függvény legegyszerűbb példája a Fibonacci-sor számítása, ahol az n-edik tag értékének megszerzéséhez az (n-1)-edik és az (n-2)-edik kiszámítása szükséges. .

A rekurzív függvényhívások megvalósítása a gyakorlatban használt nyelveken és programozási környezetekben általában a hívásverem mechanizmusára támaszkodik - a függvény visszatérési címe és helyi változói a verembe íródnak, aminek köszönhetően minden következő rekurzív hívás ez a függvény a saját helyi változókészletét használja, és ennek köszönhetően megfelelően működik. Ennek a meglehetősen egyszerű mechanizmusnak a hátoldala az, hogy minden rekurzív hívás bizonyos mennyiségű számítógép RAM -ot igényel , és ha a rekurzió túl mély, a hívási verem túlcsordulhat .

A rekurzív függvények programozásban való alkalmazásának kívánatosságának kérdése nem egyértelmű: egyrészt a rekurzív forma szerkezetileg egyszerűbb és áttekinthetőbb lehet, különösen akkor, ha maga a megvalósított algoritmus lényegében rekurzív. Ezenkívül egyes deklaratív vagy tisztán funkcionális nyelvek (például a Prolog vagy a Haskell ) egyszerűen nem rendelkeznek szintaktikai eszközökkel a hurkok szervezésére, és bennük a rekurzió az egyetlen rendelkezésre álló mechanizmus az ismételt számítások szervezésére. Másrészt általában ajánlott kerülni az olyan rekurzív programokat, amelyek túl nagy rekurziós mélységhez vezetnek (vagy bizonyos körülmények között vezethetnek is). Így a faktoriális rekurzív számításának az oktatási irodalomban elterjedt példája inkább arra mutat példát, hogyan ne használjuk a rekurziót, mivel kellően nagy rekurziós mélységhez vezet, és nyilvánvaló megvalósítása van hagyományos ciklikus formában. algoritmus.

A rekurziónak létezik egy speciális típusa, az úgynevezett " farok rekurzió " (a rekurzív algoritmus felépítése olyan, hogy a rekurzív hívás a függvényben végrehajtott utolsó művelet, és ennek eredménye közvetlenül a függvény eredményeként kerül visszaadásra). A kódoptimalizálást (forrás vagy végrehajtható) támogató funkcionális programozási nyelvek értelmezői és fordítói automatikusan iterációvá konvertálják a farokrekurziót , ami biztosítja a farokrekurziós algoritmusok végrehajtását korlátozott mennyiségű memóriában. Az ilyen rekurzív számítások, még ha formálisan végtelenek is (például ha rekurziót használnak a felhasználói parancsokat elfogadó shell munkájának megszervezésére), soha nem vezetnek a memória kimerüléséhez . A programozási nyelvi szabványok azonban nem mindig határozzák meg egyértelműen, hogy egy rekurzív függvénynek milyen feltételeknek kell megfelelnie ahhoz, hogy a fordító garantáltan iterációvá alakítsa azt. A ritka kivételek egyike a Scheme nyelv ( a Lisp nyelv dialektusa ), amelynek leírása minden szükséges információt tartalmaz.

Elméletileg bármely rekurzív függvény helyettesíthető ciklussal és veremmel . Egy ilyen módosítás azonban általában értelmetlen, mivel csak ahhoz vezet, hogy a kontextus automatikus mentését a hívásveremben ugyanazon műveletek kézi végrehajtásával helyettesítik azonos vagy több memóriafelhasználással. Kivételt képezhet az a helyzet, amikor a rekurzív algoritmust olyan nyelven kell modellezni, amelyen a rekurzió tilos.

A programok helyességének igazolása

A kifejezetten ciklikus programokkal ellentétben nincs szükség invariáns mesterséges bevezetésére a rekurzív programok helyességének bizonyítására . A rekurzív függvény helyességének analitikus bizonyítása a matematikai indukció módszerére, azaz a következő állítások bizonyítására redukálódik:

A rekurzív inverzió helyessége. Bebizonyosodott, hogy a függvény bármely rekurzív ágában számított eredmény helyes lesz, feltéve, hogy a függvény paraméterei helyesen vannak beállítva, és a megfelelő rekurzív hívások a megfelelő eredményt adják vissza.
Az összes terminálág helyessége. Bebizonyosodott, hogy minden terminálág helyes értéket ad vissza. Általában ez a bizonyítás triviális, mivel a terminális ágak általában nem tartalmaznak számításokat.
Egy terminálág elérhetősége bármely helyes paraméterkészlethez véges számú rekurzív hívás után. Bebizonyosodott, hogy a rekurzív hívás során végrehajtott függvényhívás paramétereinek megváltoztatása véges számú rekurzív hívás után olyan paraméterkészlethez vezet, amelyhez terminálág van.

Az első és a második állítás összegéből az következik, hogy ha elérjük a terminális ágat (és ez minden olyan esetben, amikor a függvény számítása véglegesnek bizonyul), a függvény a helyes eredményt adja vissza. A harmadik állítás azt bizonyítja, hogy minden számítás véges lesz. Ezért a megfelelő paraméterekkel rendelkező függvényhívások a megfelelő eredményt adják vissza (a nyilvánvaló "technikai" figyelmeztetéssel - ha a rekurziós mélység nem olyan nagy, hogy memóriatúlcsordulást okozzon).

Adatok

Rekurzív adatdefiníció akkor fordul elő, ha egy adatstruktúra (rekord, objektum) tartalmaz egy magához szerkezetileg hasonló beágyazott objektumot, vagy (gyakrabban) utal ugyanarra az objektumra. Egy objektum rekurzív definiálásának az az előnye, hogy egy ilyen véges definíció leírhat egy potenciálisan végtelen adatstruktúrát. Hasonló struktúrákat használunk listák és grafikonok leírásánál . Listaleírás példa ( C ):

struct elem_of_list { struct elem_of_list * next ; /* mutató a következő azonos típusú elemre */ intdata ; _ /* néhány adat */ };

Mivel végtelen számú beágyazott objektum nem fér el a véges memóriában, a valóságban az ilyen rekurzívan meghatározott struktúrák mindig végesek. A végső (terminális) cellákba általában üres mutatókat írnak, amelyek egyben flagek is, amelyek jelzik a struktúrát feldolgozó programnak, hogy elérkezett a vége.

A rekurzív adatstruktúra gyakran rekurzió használatát idézi elő ezen adatok feldolgozásához. Az utóbbi években elterjedt az úgynevezett „ lusta kiértékelés ” koncepciója, amely szerint a program által feldolgozott adatokat csak akkor számolja ki, amikor arra szükség van. Ennek a koncepciónak a megvalósítása néhány nyelvben ( Haskell , Python ) a potenciálisan végtelen leírására való képesség megjelenéséhez vezetett, beleértve a rekurzív sorozatokat is, anélkül, hogy az objektumok generálására vonatkozóan kifejezett korlátozásokat szabnának, és szabadon dolgozhatnak velük.

A fizikában

A végtelen rekurzió klasszikus példája két egymással szemben elhelyezett tükör : két csökkenő tükör-visszaverődések folyosóját alkotják.

A végtelen rekurzió másik példája az elektronikus erősítő áramkörök öngerjesztő (pozitív visszacsatolás) hatása , amikor a kimenetről a jel a bemenetre kerül, felerősítik, visszamegy az áramkör bemenetére, és újra felerősítik. Azokat az erősítőket, amelyeknél ez a működési mód szabványos, önoszcillátoroknak nevezzük .

A nyelvészetben

A nyelvészetben a rekurzió a nyelv azon képessége, hogy egymásba ágyazott mondatokat és konstrukciókat generáljon. A „ macska megette az egeret ” alapmondat rekurzióval kibővíthető: „ Ványa kitalálta, hogy a macska megette az egeret” , továbbá „ Kátya tudja, hogy Ványa kitalálta, hogy a macska megette az egeret” stb. A rekurziót az egyik nyelvi univerzálisnak tekintik , vagyis minden természetes nyelvre jellemző. Azonban a közelmúltban aktívan megvitatták a rekurzió esetleges hiányát az Amazonas egyik nyelvén - Pirahana , amelyet Daniel Everett [1] nyelvész is megjegyez .

A kultúrában

A rekurzióval kapcsolatos viccek többsége a végtelen rekurzióról szól, amelyben nincs kilépési feltétel, például ismert a mondás: "A rekurzió megértéséhez először meg kell értened a rekurziót" .
- Egy nagyon népszerű vicc a rekurzióról, amely egy szótári bejegyzésre emlékeztet:

rekurzió lásd rekurzió

A rekurzió témája Jorge Luis Borges argentin író számos történetében és esszéjében jelen van .
Stanislav Lem számos története végtelen rekurziójú (lehetséges) eseményeknek szentel:
- a Cyberiad története egy racionális gépről, amely elég okos és lusta volt ahhoz, hogy egy hasonlót építsen, hogy megoldjon egy adott problémát, és rábízza a megoldást (az eredmény egy végtelen rekurzió volt, amikor minden új gép épített egy hasonlót, és áthelyezte a feladat neki);
- egy történet Csendes Iyonról "A tizennegyedik utazás" a " Csendes Iyon csillagnaplóiból ", amelyben a hős egymás után lép át a sírokról szóló cikkről a szepulációról szóló cikkre, onnan pedig a sepulkariáról szóló cikkre, amelyben ott van ismét egy hivatkozás a "sepulks" cikkre:

A következő rövid információt találtam:
„A SEPULS az ardrita civilizáció fontos eleme (lásd) az Enteropia bolygóról (lásd). Lásd SEPULCARIA.
Követtem ezt a tanácsot, és ezt olvastam:
"SEPULCARIA - eszközök szeplációhoz (q.v.)".
Rákerestem a "Sepulenia" kifejezésre; ez állt rajta:
„SZEPULÁCIÓ – Ardritok elfoglalása (lásd) az Enteropia bolygóról (lásd). Lásd SEPULS.

Lem S. „Csendes Iyon csillagnaplói. Utazás tizennégy.

Rekurzív betűszavak : GNU (GNU nem Unix), PHP (PHP: Hypertext Preprocessor), WINE ( Wine Is Not an Emulator ) stb.
Az Orosz Föderáció címere rekurzívan meghatározott grafikai objektum: a rajta ábrázolt kétfejű sas jobb mancsába egy jogar van befogva, amelyet a címer kicsinyített másolata koronáz meg. Mivel ezen a címeren is van egy jogar a sas jobb mancsában, végtelen rekurziót kapunk.

Lásd még

Jegyzetek

↑ A nyelvtudományi rekurzióról, annak fajtáiról és az orosz nyelv legjellemzőbb megnyilvánulásairól E. A. Lodatko „ Rekurzív nyelvi struktúrák” című cikke .

Linkek

Cikk az Encyclopedia Foundation-ben // Rekurzió

fraktálok
Jellemzők	fraktál dimenzió Hausdorff dimenzió Lebesgue dimenzió rekurzió önhasonlóság
A legegyszerűbb fraktálok	Fern Barnsley Kántor készlet sárkánygörbe Koch-görbe Szivacs Menger Sierpinski szőnyeg Sierpinski háromszög Térkitöltő görbe
furcsa vonzerő	Multifraktál
L-rendszer	Térkitöltő görbe
Bifurkációs fraktálok	Julia meg Ljapunov-fraktál Mandelbrot készlet Newton medencéi
Véletlenszerű fraktálok	Brown-mozgás barna fa fraktál felület Perkolációs elmélet
Emberek	Georg Kantor Felix Hausdorff Gaston Julia Helge von Koch Paul Levy Alekszandr Ljapunov Benoit Mandelbrot Lewis Richardson Václav Sierpinski
Kapcsolódó témák	Milyen hosszú Nagy-Britannia partja? » Tengerparti paradoxon