Rekursio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. lokakuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Rekursio on kohteen tai prosessin määritelmä, kuvaus, kuva tässä objektissa tai itse prosessissa, eli tilanne, jossa objekti on osa itseään. Termiä "rekursio" käytetään useilla erityisaloilla - kielitieteestä logiikkaan , mutta se löytää laajimman sovelluksen matematiikassa ja tietojenkäsittelytieteessä .

Matematiikassa

Matematiikassa rekursiolla tarkoitetaan funktioiden ja lukusarjojen määrittelytapaa : rekursiivisesti annettu funktio määrittää arvonsa viittaamalla itseensä muilla argumenteilla. Tässä tapauksessa kaksi vaihtoehtoa on mahdollista:

Lopullinen rekursiivinen funktio. Se asetetaan siten, että mille tahansa äärelliselle argumentille äärellisen määrän rekursiivisia kutsuja jälkeen se johtaa johonkin erikseen määritellyistä erikoistapauksista, jotka arvioidaan ilman rekursiota. Klassinen esimerkki: ei-negatiivisen kokonaisluvun rekursiivisesti määritelty faktoriaali : . Tässä jokainen seuraava rekursiivinen kutsu suoritetaan argumentilla, joka on pienempi kuin yksi. Koska n on määritelmän mukaan ei-negatiivinen kokonaisluku, n: n rekursiivisen kutsun jälkeen funktion arviointi tulee taatusti erikoistapaukseen, jossa rekursio pysähtyy. Siten, huolimatta määritelmän rekursiivisuudesta, funktion laskenta mille tahansa määritelmäalueelta tulevalle argumentille on äärellinen. $n!=\begin{cases}n\cdot(n-1)!,&n>0\\1,&n=0\end{cases}$ $0! = 1$
Ääretön rekursiivinen funktio. Se annetaan viittaukseksi itseensä kaikissa tapauksissa (ainakin joidenkin argumenttien osalta). Äärettömät sarjat, äärettömät jatkuvat murtoluvut ja niin edelleen voidaan määrittää samalla tavalla. Tarkan arvon käytännön laskeminen tässä on tietysti mahdotonta, koska se vaatii äärettömän ajan. Tarvittava tulos löydetään analyyttisin menetelmin. Kuitenkin, jos emme puhu ehdottoman tarkan arvon saamisesta, vaan halutun arvon tietyn likiarvon laskemisesta, niin joissain tapauksissa on mahdollista käyttää suoraan rekursiivista määritelmää: sille suoritetaan laskelmia, kunnes vaadittu tarkkuus on saavutettu. saavutettu. Esimerkki on luvun e jatkuva murto -osan laajennus :

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

, missä

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

Suora laskenta yllä olevan kaavan mukaan aiheuttaa äärettömän rekursion, mutta voidaan todistaa, että f(n):n arvo pyrkii yksikkyyteen n:n kasvaessa (täten sarjan äärettömyydestä huolimatta Eulerin luvun arvo on äärellinen) . e:n arvon likimääräiseen laskemiseen riittää, että rekursion syvyys rajoitetaan keinotekoisesti johonkin ennalta määrättyyn numeroon ja sen saavuttaessa käytetään yhtä sen sijaan.

f(n)

Toinen esimerkki rekursiosta matematiikassa on rekursiivisella kaavalla annettu numerosarja , jossa jokainen peräkkäinen termi sekvenssissä lasketaan n edellisen termin funktion tuloksena. Siten äärettömän lausekkeen avulla (joka on yhdistelmä rekursiivista kaavaa ja arvojoukkoa sarjan ensimmäisille n termille) voidaan määrittää ääretön sekvenssi.

Matemaattinen induktio liittyy läheisesti rekursioon : se on luonnollinen tapa todistaa funktioiden ominaisuudet luonnollisille lukuille , jotka on annettu rekursiivisesti niiden pienempien arvojen perusteella.

Matematiikassa niin kutsuttujen "primitiivisesti rekursiivisten" funktioiden luokkaa tarkastellaan erikseen. Primitiivisen rekursiivisen funktion määritelmä on myös rekursiivinen, se määrittelee joukon primitiivisiä funktioita ja sääntöjoukon; funktio on primitiivinen rekursiivinen, jos se voidaan esittää näiden sääntöjen mukaan muodostettuna primitiivisten rekursiivisten funktioiden yhdistelmänä.

Esimerkkejä matematiikan rekursiosta:

Gauss-Jordanin menetelmä lineaaristen algebrallisten yhtälöiden ratkaisemiseksi on rekursiivinen.
Jo mainittu ei-negatiivisen kokonaisluvun faktoriaali.
Fibonacci-luvut määritellään käyttämällä toistuvuusrelaatiota : Ensimmäinen ja toinen Fibonacci-luku ovat 1 Kun , -e Fibonacci-luku on yhtä suuri kuin -: nnen ja -nnennen Fibonacci -luvun summa $n>2$ $n$ $(n-1)$ $(n-2)$
Lähes kaikki geometriset fraktaalit on annettu äärettömän rekursion muodossa (esimerkiksi Sierpinskin kolmio ).
Vakioesimerkki laskettavasta rekursiivisesta funktiosta, joka ei ole primitiivinen rekursiivinen, on Ackermann-funktio : ei-negatiivisille kokonaisluvuille ja seuraavasti: $m$ $n$

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

Ohjelmoinnissa

Toiminnot

Ohjelmoinnissa rekursio on kutsu funktiolle ( proseduuri ) itsestään, suoraan ( yksinkertainen rekursio ) tai muiden funktioiden kautta ( kompleksi tai epäsuora rekursio ), esimerkiksi funktio kutsuu funktiota ja funktio funktiota . Sisäkkäisten funktio- tai proseduurikutsujen lukumäärää kutsutaan rekursion syvyydeksi. Rekursiivisen ohjelman avulla voit kuvata toistuvan tai jopa potentiaalisesti äärettömän laskutoimituksen ilman ohjelman osien nimenomaista toistoa ja silmukoiden käyttöä. $A$ $B$ $B$ $A$

Rakenteellisesti rekursiivinen funktio ylimmällä tasolla on aina haarakäsky (jommankumman valinta kahdesta tai useammasta vaihtoehdosta riippuen ehdoista, jota tässä tapauksessa on tarkoituksenmukaista kutsua "rekursion lopetusehdoiksi"), jossa on kaksi tai useampi vaihtoehtoisia haaroja, joista ainakin yksi on rekursiivinen ja ainakin yksi terminaali . Rekursiivinen haara suoritetaan, kun rekursion lopetusehto on epätosi ja sisältää vähintään yhden rekursiivisen kutsun - funktion suoran tai epäsuoran kutsun itselleen. Päätehaara suoritetaan, kun rekursion lopetusehto on tosi; se palauttaa jonkin arvon ilman rekursiivista kutsua. Hyvin kirjoitetun rekursiivisen funktion on varmistettava, että rajallisen määrän rekursiivisia kutsuja jälkeen rekursion lopetusehto saavutetaan, jolloin peräkkäisten rekursiivisten kutsujen ketju katkeaa ja palaa.

Niiden toimintojen lisäksi, jotka tekevät yhden rekursiivisen kutsun jokaisessa rekursiivisessa haarassa, on olemassa tapauksia "rinnakkaisrekursiosta", joissa kaksi tai useampia rekursiivisia kutsuja tehdään samassa rekursiivisessa haarassa. Rinnakkaisrekursio on tyypillistä monimutkaisten tietorakenteiden, kuten puiden, käsittelyssä. Yksinkertaisin esimerkki rinnakkaisrekursiivisesta funktiosta on Fibonacci-sarjan laskenta, jossa n:nnen termin arvon saamiseksi on tarpeen laskea (n-1)- ja (n-2)-. .

Rekursiivisten funktiokutsujen toteutus käytännössä käytetyissä kielissä ja ohjelmointiympäristöissä perustuu pääsääntöisesti puhelupinomekanismiin - funktion paluuosoite ja paikalliset muuttujat kirjoitetaan pinoon , minkä ansiosta jokainen seuraava rekursiivinen kutsu tämä funktio käyttää omia paikallismuuttujiaan ja tästä johtuen se toimii oikein. Tämän melko yksinkertaisen mekanismin kääntöpuolena on, että jokainen rekursiivinen puhelu vaatii tietyn määrän tietokoneen RAM -muistia , ja jos rekursio on liian syvä, puhelupino voi vuotaa yli.

Kysymys rekursiivisten funktioiden käytön toivottavuudesta ohjelmoinnissa on epäselvä: toisaalta rekursiivinen muoto voi olla rakenteellisesti yksinkertaisempi ja selkeämpi, varsinkin kun toteutettu algoritmi itsessään on olennaisesti rekursiivinen. Lisäksi joillakin deklaratiivisilla tai puhtaasti toiminnallisilla kielillä (kuten Prolog tai Haskell ) ei yksinkertaisesti ole syntaktisia keinoja silmukoiden järjestämiseen, ja niiden rekursio on ainoa käytettävissä oleva mekanismi toistuvien laskelmien järjestämiseen. Toisaalta on yleensä suositeltavaa välttää rekursiivisia ohjelmia, jotka johtavat (tai joissain tilanteissa voivat johtaa) liian suureen rekursioon. Siten opetuskirjallisuudessa laajalle levinnyt esimerkki faktoriaalin rekursiivisesta laskemisesta on pikemminkin esimerkki siitä, kuinka rekursiota ei saa käyttää, koska se johtaa riittävän suureen rekursioon ja sillä on ilmeinen toteutus perinteisen syklisen muodossa. algoritmi.

On olemassa erityinen rekursio, jota kutsutaan " häntärekursioksi " (rekursiivisen algoritmin rakenne on sellainen, että rekursiivinen kutsu on viimeinen funktiossa suoritettu operaatio ja sen tulos palautetaan suoraan funktion tuloksena). Toiminnallisten ohjelmointikielten tulkit ja kääntäjät , jotka tukevat koodin optimointia (lähde tai suoritettava) muuntaa tail-rekursion automaattisesti iteraatioksi , mikä varmistaa tail-rekursio-algoritmien suorittamisen rajoitetussa muistimäärässä. Tällaiset rekursiiviset laskelmat, vaikka ne olisivat muodollisesti äärettömiä (esimerkiksi käytettäessä rekursiota käyttäjien komennot hyväksyvän kuoren työn järjestämiseen), eivät koskaan johda muistin ehtymiseen . Ohjelmointikielistandardit eivät kuitenkaan aina määrittele tarkasti, mitkä ehdot rekursiivisen funktion on täytettävä, jotta kääntäjä voi taatusti muuntaa sen iteraatioksi. Yksi harvoista poikkeuksista on Scheme-kieli ( lisp-kielen murre ) , jonka kuvaus sisältää kaikki tarvittavat tiedot.

Teoreettisesti mikä tahansa rekursiivinen funktio voidaan korvata silmukalla ja pinolla . Tällainen muutos on kuitenkin pääsääntöisesti merkityksetön, koska se johtaa vain kontekstin automaattisen tallennuksen korvaamiseen puhelupinossa samojen toimintojen manuaalisella suorittamisella samalla tai suuremmalla muistinkulutuksella. Poikkeuksena voi olla tilanne, jossa rekursiivinen algoritmi on mallinnettava kielellä, jossa rekursio on kielletty.

Todiste ohjelmien oikeellisuudesta

Toisin kuin eksplisiittisesti syklisissä ohjelmissa, ei ole tarvetta ottaa keinotekoisesti käyttöön invarianttia todistamaan rekursiivisten ohjelmien oikeellisuutta . Rekursiivisen funktion oikeellisuuden analyyttinen todistus rajoittuu matemaattisen induktion menetelmään eli seuraavien väitteiden todistukseen:

Rekursiivisen inversion oikeellisuus. Osoitetaan, että missä tahansa funktion rekursiivisessa haarassa laskettu tulos on oikea, mikäli funktion parametrit on asetettu oikein ja vastaavat rekursiiviset kutsut palauttavat oikean tuloksen.
Kaikkien päätehaarojen oikeellisuus. On todistettu, että kaikki päätehaarat palauttavat oikeat arvot. Yleensä tämä todistus on triviaali, koska päätehaarat eivät yleensä sisällä laskelmia.
Päätehaaran tavoitettavuus mille tahansa oikealle parametrijoukolle rajallisen määrän rekursiivisia kutsuja jälkeen. On todistettu, että funktiokutsun parametrien muuttaminen, joka suoritetaan rekursiivisen kutsun aikana, äärellisen määrän rekursiivisia kutsuja jälkeen johtaa yhteen parametrijoukoista, jolle on olemassa päätehaara.

Ensimmäisen ja toisen lauseen summasta seuraa, että jos päätehaara saavutetaan (ja tämä tarkoittaa kaikissa tapauksissa, kun funktion laskenta osoittautuu lopulliseksi), funktio palauttaa oikean tuloksen. Kolmas väite todistaa, että mikä tahansa laskelma on äärellinen. Siksi mikä tahansa funktiokutsu oikeilla parametreilla palauttaa oikean tuloksen (ilmeisellä "teknisellä" varoituksella - jos rekursion syvyys ei ole niin suuri, että se aiheuttaa muistin ylivuodon).

Tiedot

Rekursiivinen datamäärittely tapahtuu, kun tietorakenne (tietue, objekti) sisältää sisäkkäisen objektin, joka on rakenteellisesti samanlainen kuin itse tai (useammin) viittauksen samaan objektiin. Objektin rekursiivisen määrittelyn etuna on, että tällainen äärellinen määritelmä voi kuvata mahdollisesti äärettömän tietorakenteen. Samanlaisia rakenteita käytetään kuvattaessa listoja ja kaavioita . Luettelon kuvauksen esimerkki ( C ):

struct element_of_list { struct element_of_list * next ; /* osoitin seuraavaan samantyyppiseen elementtiin */ intdata ; _ /* tietoja */ };

Koska ääretön määrä sisäkkäisiä objekteja ei mahdu äärelliseen muistiin, todellisuudessa tällaiset rekursiivisesti määritellyt rakenteet ovat aina äärellisiä. Lopullisiin (pääte)soluihin kirjoitetaan yleensä tyhjiä osoittimia, jotka ovat myös lippuja, jotka osoittavat rakennetta käsittelevälle ohjelmalle, että sen loppu on saavutettu.

Rekursiivinen tietorakenne aiheuttaa usein rekursion käytön näiden tietojen käsittelyssä. Viime vuosina on yleistynyt käsite ns. " laiska arviointi ", jonka mukaan ohjelman käsittelemät tiedot lasketaan vain silloin, kun sitä tarvitaan. Tämän konseptin toteuttaminen on johtanut joissakin kielissä ( Haskell , Python ) kykyyn kuvata potentiaalisesti ääretöntä, mukaan lukien rekursiiviset sekvenssit ilman nimenomaisia rajoituksia objektien luomiselle ja työskennellä vapaasti niiden kanssa.

Fysiikassa

Klassinen esimerkki äärettömästä rekursiosta on kaksi toisiaan vastapäätä olevaa peiliä : ne muodostavat kaksi pienenevien peiliheijastusten käytävää.

Toinen esimerkki äärettömästä rekursiosta on elektronisten vahvistuspiirien itseherätys (positiivinen takaisinkytkentä) , kun signaali lähdöstä menee sisääntuloon, vahvistetaan, menee takaisin piirin sisäänmenoon ja vahvistetaan uudelleen. Vahvistimia, joille tämä toimintatapa on vakio, kutsutaan itseoskillaattoriksi .

Kielitieteessä

Kielitieteessä rekursio on kielen kykyä luoda sisäkkäisiä lauseita ja rakenteita. Peruslausetta " kissa söi hiiren " voidaan laajentaa rekursiolla " Vanya arvasi, että kissa söi hiiren" , edelleen " Katia tietää, että Vanya arvasi, että kissa söi hiiren" ja niin edelleen. Rekursiota pidetään yhtenä kielellisistä universaaleista , eli se on ominaista mille tahansa luonnolliselle kielelle. Äskettäin on kuitenkin keskusteltu aktiivisesti mahdollisesta rekursion puuttumisesta yhdessä Amazonin kielistä - Pirahana , jonka kielitieteilijä Daniel Everett [1] totesi .

Kulttuurissa

Suurin osa rekursioon liittyvistä vitseista koskee ääretöntä rekursiota, jossa ei ole poistumisehtoa, esimerkiksi tunnetaan sanonta: "Ymmärtääksesi rekursion, sinun on ensin ymmärrettävä rekursio" .
- Erittäin suosittu vitsi rekursiosta, joka muistuttaa sanakirjamerkintää:

rekursio katso rekursio

Rekursion teema on läsnä monissa argentiinalaisen kirjailijan Jorge Luis Borgesin tarinoissa ja esseissä .
Useat Stanislav Lemin tarinat ovat omistettu (mahdollisille) tapauksille, joissa on ääretön rekursio:
- Cyberiadin tarina rationaalisesta koneesta, joka oli tarpeeksi älykäs ja laiska rakentamaan samanlaisen ratkaisemaan tietyn ongelman ja uskomaan ratkaisun siihen (tuloksena oli loputon rekursio, kun jokainen uusi kone rakensi samanlaisen ja siirsi tehtävä sille);
- tarina Iyonista Hiljaisesta "The Fourneyth Journey" " Star Diaries of Iyon the Quiet " -julkaisusta, jossa sankari siirtyy peräkkäin haudoista käsittelevään artikkeliin, josta sepulkaria -artikkeliin, jossa on on taas viittaus artikkeliin "sepulks":

Löysin seuraavan lyhyen tiedon:
"SEPULS ovat tärkeä elementti ardrite-sivilisaatiossa (katso) Enteropia-planeetalta (katso). Katso SEPULCARIA.
Noudatin tätä neuvoa ja luin:
"SEPULCARIA - laitteet erotteluun (q.v.)".
Etsin "Sepulenia"; siinä luki:
"MAISTUS - Ardritsien (katso) miehitys Enteropia-planeetalta (katso). Katso SEPULS.

Lem S. "Iyon the Quietin tähtipäiväkirjat. Matka neljäntoista.

Rekursiiviset lyhenteet : GNU (GNU ei Unix), PHP (PHP: Hypertext Preprocessor), WINE ( Wine Is Not an Emulator ) jne.
Venäjän federaation vaakuna on rekursiivisesti määritelty graafinen esine: siinä kuvatun kaksipäisen kotkan oikeaan tassuun on kiinnitetty valtikka, jonka kruunaa vaakunan pienennetty kopio. Koska tässä vaakunassa on myös valtikka kotkan oikeassa käpälässä, saadaan ääretön rekursio.

Katso myös

Muistiinpanot

↑ Kielitieteen rekursiosta, sen lajikkeista ja venäjän kielen tyypillisimmistä ilmenemismuodoista on kuvattu E. A. Lodatkon artikkelissa " Rekursiiviset kielelliset rakenteet" Arkistokopio 4. maaliskuuta 2009 Wayback Machinessa

Linkit

Artikkeli Encyclopedia Foundationissa // Recursion

fraktaaleja
Ominaisuudet	fraktaali ulottuvuus Hausdorffin ulottuvuus Lebesguen ulottuvuus rekursio itsensä samankaltaisuus
Yksinkertaisimmat fraktaalit	Fern Barnsley Kantorin setti lohikäärmeen käyrä Kochin käyrä Sieni Menger Sierpinski matto Sierpinskin kolmio Tilan täyttökäyrä
outo houkutin	Multifraktaali
L-järjestelmä	Tilan täyttökäyrä
Bifurkaatiofraktaalit	Julia setti Ljapunovin fraktaali Mandelbrot setti Newtonin altaat
Satunnaiset fraktaalit	Brownin liike ruskea puu fraktaalipinta Perkolaatioteoria
Ihmiset	Georg Kantor Felix Hausdorff Gaston Julia Helge von Koch Paul Levy Aleksanteri Ljapunov Benoit Mandelbrot Lewis Richardson Vaclav Sierpinski
liittyvät aiheet	Kuinka pitkä Ison-Britannian rannikko on? » Rannikkoparadoksi