Rekursio - Recursion

Visuaalinen rekursion muoto, joka tunnetaan nimellä Droste -efekti . Tässä kuvassa olevalla naisella on esine, joka sisältää pienemmän kuvan hänestä, jolla on identtinen esine, joka puolestaan sisältää pienemmän kuvan hänestä, jolla on sama esine, ja niin edelleen. 1904 Droste kaakao tina, suunnitteli Jan Misset

Rekursio (adjektiivi: rekursiivinen ) tapahtuu, kun asia määritellään itsestään tai sen tyypistä. Rekursio käytetään eri alojen vaihtelevat kielitiede ja logiikkaa . Yleisin rekursion sovellus on matematiikassa ja tietojenkäsittelytieteessä , jossa määritettävää funktiota sovelletaan sen omassa määritelmässä. Vaikka tämä ilmeisesti määrittelee loputtoman määrän esiintymiä (funktioarvoja), se tehdään usein siten, että ääretöntä silmukkaa tai ääretöntä viiteketjua ei voi esiintyä.

Muodolliset määritelmät

Ouroboros , ikivanha symboli, joka kuvaa käärmettä tai lohikäärmettä syömässä omaa häntäänsä.

Matematiikassa ja tietojenkäsittelytieteessä esineiden tai menetelmien luokalla on rekursiivista käyttäytymistä, kun se voidaan määritellä kahdella ominaisuudella:

Yksinkertainen perustapaus (tai tapaukset) - lopetusskenaario, joka ei käytä rekursiota vastauksen tuottamiseen
Rekursiivinen vaihe - joukko sääntöjä, joka vähentää kaikki peräkkäiset tapauksissa pohjaa kohti tapauksessa.

Esimerkiksi seuraava on rekursiivinen määritelmä henkilön esi -isästä . Yhden esi -isä on joko:

Vanhempi ( perustapaus ) tai
Vanhemman esi -isä ( rekursiivinen vaihe ).

Fibonacci-sekvenssi on toinen klassinen esimerkki rekursiota:

Kuitu (0) = 0 peruskotelona

1,

Kuitu (1) = 1 peruskotelona

2,

Kaikki kokonaisluvut

n > 1

,

Fib (n) = Fib (n - 1) + Fib (n - 2)

.

Monet matemaattiset aksioomat perustuvat rekursiivisiin sääntöihin. Esimerkiksi, muodollinen määrittely luonnollisia lukuja , jotka Peanon aksioomaa voidaan kuvata: "Zero on luonnollinen luku, ja kukin luonnollinen luku on seuraaja, joka on myös luonnollinen luku." Tällä perustapauksella ja rekursiivisella säännöllä voidaan luoda joukko kaikkia luonnollisia numeroita.

Muita rekursiivisesti määriteltyjä matemaattisia objekteja ovat tekijät , funktiot (esim. Toistosuhteet ), joukot (esim. Kolmiosainen joukko ) ja fraktaalit .

On useita erilaisia kielen poskessa määritelmiä rekursiosta; katso rekursiivista huumoria .

Epävirallinen määritelmä

Äskettäin virkistetty hapantaikina , käymisen kautta kupliva : resepti vaatii jonkin verran hapantaikinaa, joka on jäljellä saman reseptin viimeisestä valmistuskerrasta.

Rekursio on prosessi, jonka menettely suorittaa, kun yksi menettelyn vaiheista sisältää menettelyn kutsumisen itse. Menettelyn, joka käy läpi rekursion, sanotaan olevan 'rekursiivinen'.

Rekursion ymmärtämiseksi on tunnistettava ero menettelyn ja menettelyn suorittamisen välillä. Menettely on joukko sääntöihin perustuvia vaiheita, kun taas menettelyn suorittaminen edellyttää sääntöjen noudattamista ja vaiheiden suorittamista.

Rekursio liittyy mutta ei samaan viittaukseen menettelyn määritelmän sisällä jonkin muun menettelyn suorittamiseen.

Kun menettely määritellään sellaiseksi, tämä luo välittömästi mahdollisuuden loputtomaan silmukkaan; rekursiota voidaan käyttää oikein määritelmässä vain, jos kyseinen vaihe ohitetaan tietyissä tapauksissa, jotta menettely voidaan suorittaa loppuun.

Mutta vaikka se on määritelty oikein, rekursiivinen menettely ei ole ihmisten helppo suorittaa, koska se edellyttää uuden erottamista menettelyn vanhasta, osittain toteutetusta kutsumisesta; Tämä vaatii hallintoa siitä, kuinka pitkälle eri samanaikaiset tapaukset ovat edenneet. Tästä syystä rekursiiviset määritelmät ovat hyvin harvinaisia jokapäiväisissä tilanteissa.

Kielellä

Kielitieteilijä Noam Chomsky , monien muiden joukossa, on väittänyt, että kielen kieliopillisten lauseiden lukumäärän ylärajan puuttuminen ja kieliopillisen lauseen pituuden ylärajan puuttuminen (käytännön rajoitteiden, kuten lausumiseen käytettävän ajan, ulkopuolella) ), voidaan selittää luonnollisen kielen rekursion seurauksena.

Tämä voidaan ymmärtää syntaktisen luokan, kuten lauseen, rekursiivisella määritelmällä. Lauseella voi olla rakenne, jossa verbin jälkeen on toinen lause: Dorothyn mielestä noidat ovat vaarallisia , ja lause noidat ovat vaarallisia esiintyy suuremmalla. Joten lause voidaan määritellä rekursiivisesti (hyvin karkeasti) sellaiseksi, jolla on rakenne, joka sisältää substantiivilauseen, verbin ja valinnaisesti toisen lauseen. Tämä on oikeastaan vain erikoistapaus rekursion matemaattiselle määritelmälle.

Tämä tarjoaa tavan ymmärtää luovuuden kielestä rajattomaan määrä kieliopillisia lauseita, koska se välittömästi ennakoi lauseet voivat olla mielivaltaisen pituus: Dorothy mielestä Toto epäilee Tin Man sanoi ... . On monia rakenteita lukuun ottamatta lauseita, jotka voidaan määritellä rekursiivisesti, ja siksi monia tapoja, joilla lause voi upottaa yhden luokan esiintymiä toiseen. Vuosien mittaan kielet ovat yleensä osoittautuneet alttiiksi tällaiselle analyysille.

Äskettäin Daniel Everett on kuitenkin vastustanut yleisesti hyväksyttyä ajatusta siitä, että rekursio on ihmiskielen olennainen ominaisuus, Pirahã -kieltä koskevien väitteidensä perusteella . Andrew Nevins, David Pesetsky ja Cilene Rodrigues ovat monien joukossa, jotka ovat väittäneet tätä vastaan. Kirjallisen itseviittauksen voidaan joka tapauksessa väittää olevan luonteeltaan erilainen kuin matemaattinen tai looginen rekursio.

Rekursiolla on ratkaiseva rooli paitsi syntaksissa myös luonnollisen kielen semantiikassa . Sanaa ja esimerkiksi voidaan tulkita funktiona, jota voidaan soveltaa lauseiden merkityksiin uusien lauseiden luomiseksi, samoin substantiivilausekkeiden merkityksiin, verbilauseiden merkityksiin ja muihin. Sitä voidaan soveltaa myös intransitiivisiin verbeihin, transitiivisiin verbeihin tai ditransitiivisiin verbeihin. Jotta sille annettaisiin yksi denotaatio, joka on sopivan joustava ja joka on tyypillisesti määritelty siten, että se voi käyttää mitä tahansa näistä erityyppisistä merkityksistä argumentteina. Tämä voidaan tehdä määrittelemällä se yksinkertaiselle tapaukselle, jossa se yhdistää lauseita, ja määrittelemällä sitten muut tapaukset rekursiivisesti yksinkertaisen tapauksen kannalta.

Rekursiivinen kielioppi on muodollinen kielioppi, joka sisältää rekursiivinen tuotantoa koskevat säännöt .

Rekursiivista huumoria

Rekursiivinen Wikipedia -sivu

Rekursiota käytetään joskus humoristisesti tietojenkäsittelytieteen, ohjelmoinnin, filosofian tai matematiikan oppikirjoissa, yleensä antamalla pyöreä määritelmä tai itseviittaus , jossa oletettu rekursiivinen askel ei pääse lähemmäksi perustapausta, vaan johtaa äärettömään regressioon . Ei ole epätavallista, että tällaiset kirjat sisältävät sanastossaan vitsi -merkinnän seuraavasti:

Rekursio, katso Rekursio .

Variaatio on sivulla 269, että indeksi joidenkin painokset Brian Kernighan ja Dennis Ritchie kirjasta C-kielellä ; indeksin merkintä viittaa rekursiivisesti itseensä ("rekursio 86, 139, 141, 182, 202, 269"). Varhainen versiot vitsi löytyy Puhutaanpa Lisp Laurent Siklóssy (julkaisija Prentice Hall PTR 1. joulukuuta 1975, joiden tekijänoikeus päivämäärä 1976) ja Ohjelmistot vuoteen Kernighan ja Plauger (julkaisema Addison-Wesley Professional 11. tammikuuta 1976). Vitsi näkyy myös Kernighanin ja Piken UNIX -ohjelmointiympäristössä . Se ei ilmestynyt C -ohjelmointikielen ensimmäisessä painoksessa . Vitsi on osa funktionaalisen ohjelmoinnin kansanperinnettä ja se oli laajalle levinnyt toiminnallisessa ohjelmointiyhteisössä ennen edellä mainittujen kirjojen julkaisua.

Toinen vitsi on, että "ymmärtääksesi rekursion, sinun on ymmärrettävä rekursio". Googlen verkkohakukoneen englanninkielisessä versiossa, kun tehdään haku "rekursio", sivusto ehdottaa "Tarkoititko: rekursio ". Vaihtoehtoinen muoto on seuraava, Andrew Plotkin : "Jos tiedät jo, mitä rekursio on, muista vain vastaus. Muussa tapauksessa etsi joku, joka seisoo lähempänä Douglas Hofstadteria kuin sinä; kysy sitten häneltä, mikä on rekursio."

Rekursiiviset lyhenteet ovat muita esimerkkejä rekursiivisesta huumorista. Esimerkiksi PHP tarkoittaa "PHP Hypertext Preprocessor", WINE tarkoittaa "WINE Is Not Emulator" GNU tarkoittaa "GNU's not Unix" ja SPARQL tarkoittaa "SPARQL Protocol and RDF Query Language".

Matematiikassa

Sierpinskin kolmio -a rajoitu rekursio kolmiot, jotka muodostavat fraktaali

Rekursiivisesti määritellyt joukot

Esimerkki: luonnolliset luvut

Kanoninen esimerkki rekursiivisesti määritellystä joukosta annetaan luonnollisilla numeroilla :

0 on mukana

{\ displaystyle \ mathbb {N}}

jos n on sisään , niin n + 1 on sisään

{\ displaystyle \ mathbb {N}}

{\ displaystyle \ mathbb {N}}

Luonnollisten numeroiden joukko on pienin joukko, joka täyttää kaksi edellistä ominaisuutta.

Matemaattisessa logiikassa Peano -aksioomit (tai Peano -postulaatit tai Dedekind – Peano -aksioomit) ovat saksalaisen matemaatikon Richard Dedekindin ja italialaisen matemaatikon Giuseppe Peanon 1800 -luvulla esittämien luonnollisten lukujen aksioomia . Peano -aksioomit määrittelevät rekursiiviseen seuraajafunktioon viittaavat luonnolliset luvut ja rekursiivisiin funktioihin liittämisen ja kertomisen.

Esimerkki: Todistusmenettely

Toinen mielenkiintoinen esimerkki on joukko kaikkia "todistettavissa olevia" ehdotuksia aksiomaattisessa järjestelmässä, jotka on määritelty todistusmenettelyllä, joka on induktiivisesti (tai rekursiivisesti) määritelty seuraavasti:

Jos ehdotus on aksiooma, se on todistettavissa oleva ehdotus.
Jos ehdotus voidaan johtaa todellisista tavoitettavissa olevista ehdotuksista päättelysääntöjen avulla, se on todistettavissa oleva ehdotus.
Todistettavissa olevien ehdotusten joukko on pienin joukko ehdotuksia, jotka täyttävät nämä ehdot.

Äärelliset alajakosäännöt

Äärelliset alajakosäännöt ovat rekursion geometrinen muoto, jota voidaan käyttää fraktaalimaisten kuvien luomiseen. Alajakosääntö alkaa monikulmioista, jotka on merkitty rajallisesti monilla tarroilla, ja sitten jokainen monikulmio jaetaan pienempiin leimattuihin monikulmioihin tavalla, joka riippuu vain alkuperäisen monikulmion tarroista. Tämä prosessi voidaan toistaa. Cantor -sarjan luomisen vakiomuotoinen "keskikolmanneksen" tekniikka on alajakosääntö , samoin kuin barycentric -alajako .

Toiminnallinen rekursio

Toiminto voidaan rekursiivisesti määritellä itse. Tuttu esimerkki on Fibonaccin numerosarja: F ( n ) = F ( n - 1) + F ( n - 2). Jotta tällainen määritelmä olisi hyödyllinen, sen on oltava pelkistettävissä ei-rekursiivisesti määriteltyihin arvoihin: tässä tapauksessa F (0) = 0 ja F (1) = 1.

Kuuluisa rekursiivinen funktio on Ackermann -funktio , jota toisin kuin Fibonaccin sekvenssiä ei voida ilmaista ilman rekursiota.

Todisteet, joihin liittyy rekursiivisia määritelmiä

Soveltamalla tapausten standarditekniikkaa rekursiivisesti määriteltyihin joukkoihin tai toimintoihin, kuten edellisissä osissa, saadaan rakenteellinen induktio - voimakas yleistys matemaattisesta induktiosta, jota käytetään laajasti todisteiden johtamiseen matemaattisen logiikan ja tietojenkäsittelytieteen alalla.

Rekursiivinen optimointi

Dynaaminen ohjelmointi on lähestymistapa optimointiin, joka toistaa monivaiheisen tai monivaiheisen optimointitehtävän rekursiivisessa muodossa. Tärkein tulos dynaamisessa ohjelmoinnissa on Bellmanin yhtälö , joka kirjoittaa optimointitehtävän arvon aikaisemmin (tai aikaisemmassa vaiheessa) sen arvon perusteella myöhempänä ajankohtana (tai myöhemmässä vaiheessa).

Rekursioteoreemi

Vuonna set theory , tämä on lause, joka takaa, että rekursiivisesti funktioita olemassa. Annetaan joukko $X$ , elementti ja $X$ ja funktio $f$ $:$ $X$ $\to$ $X$ , lause todetaan, että on olemassa ainutlaatuinen tehtävä (jossa tarkoittaa joukko luonnolliset luvut nolla mukaan lukien) siten, että ${\ displaystyle F: \ mathbb {N} \ - X}$ ${\ displaystyle \ mathbb {N}}$

{\ displaystyle F (0) = a}

{\ displaystyle F (n+1) = f (F (n))}

mille tahansa luonnolliselle numerolle $n$ .

Todiste ainutlaatuisuudesta

Ota kaksi toimintoa ja sellainen, että: ${\ displaystyle F: \ mathbb {N} \ - X}$ ${\ displaystyle G: \ mathbb {N} \ - X}$

{\ displaystyle F (0) = a}

{\ displaystyle G (0) = a}

{\ displaystyle F (n+1) = f (F (n))}

{\ displaystyle G (n+1) = f (G (n))}

jossa $a$ on $X:$ n elementti .

Voidaan todistaa matemaattisella induktiolla, että $F (n) = G (n)$ kaikille luonnollisille numeroille $n$ :

Perustapaus :

F (0) = a = G (0),

joten yhtälö pätee

n = 0

.

Induktiivinen vaihe : Oletetaan

F (k) = G (k)

joillekin . Sitten

F

(

k

+ 1) =

f

(

F

(

k

)) =

f

(

G

(

k

)) =

G

(

k

+ 1)

.

{\ displaystyle k \ \ mathbb {N}}

Näin ollen

F (k) = G (k)

merkitsee

F (k + 1) = G (k + 1)

.

Induktiolla $F (n) = G (n)$ kaikille . ${\ displaystyle n \ \ mathbb {N}}$

Tietojenkäsittelytieteessä

Yleinen yksinkertaistamismenetelmä on jakaa ongelma samantyyppisiin osaongelmiin. Koska ohjelmointi tekniikkaa, tätä kutsutaan hajoita ja hallitse ja on avain suunnitteluun monia tärkeitä algoritmeja. Jaa ja valloita toimii ylhäältä alas lähestymistapana ongelmanratkaisuun, jossa ongelmat ratkaistaan ratkaisemalla pienempiä tapauksia. Päinvastainen lähestymistapa on dynaaminen ohjelmointi . Tämä lähestymistapa toimii alhaalta ylöspäin, jossa ongelmat ratkaistaan ratkaisemalla suurempia ja suurempia tapauksia, kunnes haluttu koko on saavutettu.

Klassinen esimerkki rekursiota on määritelmän kertoma toiminnon, koska täällä C -koodi:

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

Funktio kutsuu itseään rekursiivisesti pienempi versio tulo (n - 1)ja kertoo tuloksen rekursiivinen puhelun n, kunnes saavutetaan pohjan tapauksessa , analogisesti matemaattisen kertoma.

Tietokoneohjelmoinnin rekursio on esimerkki, kun funktio määritellään yksinkertaisemmiksi, usein pienemmiksi versioiksi itsestään. Ratkaisu ongelmaan suunnitellaan sitten yhdistämällä ongelman yksinkertaisemmista versioista saadut ratkaisut. Yksi esimerkki rekursion sovelluksista on ohjelmointikielien jäsentimissä . Rekursion suuri etu on, että äärellinen tietokoneohjelma voi määritellä, jäsentää tai tuottaa äärettömän joukon mahdollisia lauseita, malleja tai muita tietoja.

Toistumissuhteet ovat yhtälöitä, jotka määrittelevät yhden tai useamman jakson rekursiivisesti. Joitakin erityyppisiä toistosuhteita voidaan "ratkaista" saadakseen ei-rekursiivisen määritelmän (esim. Suljetun muodon lauseke ).

Rekursion käytöllä algoritmissa on sekä etuja että haittoja. Suurin etu on yleensä ohjeiden yksinkertaisuus. Suurin haittapuoli on se, että rekursiivisten algoritmien muistin käyttö voi kasvaa hyvin nopeasti, mikä tekee niistä epäkäytännöllisiä suuremmille esiintymille.

Biologiassa

Muotoja, jotka näyttävät syntyneen rekursiivisilla prosesseilla, esiintyy joskus kasveissa ja eläimissä, kuten haarautuvissa rakenteissa, joissa yksi suuri osa haarautuu kahteen tai useampaan samanlaiseen pienempään osaan. Yksi esimerkki on Romanesco -parsakaali .

Taiteessa

Rekursiivinen nuket: alkuperäinen sarja Maatuska vuoteen Zvyozdochkin ja Malyutin , 1892

Etupinnassa Giotto n Stefaneschi Triptych , 1320, rekursiivisesti sisältää kuvan itsestään (pitämä polvillaan luku keskilevy).

Venäläinen nukke tai Matryoshka -nukke on fyysinen taiteellinen esimerkki rekursiivisesta konseptista.

Rekursio on käytetty maalauksissa vuodesta Giotto n Stefaneschi Triptyykki , tehty 1320. Sen keskeinen paneeli sisältää polvillaan hahmo Cardinal Stefaneschi pitämistä triptyykkiä itsensä uhrina.

MC Escher 's Print Gallery (1956) on tuloste, joka esittää vääristyneen kaupunki sisältää galleria, joka rekursiivisesti sisältää kuvan, ja niin loputtomiin .

Katso myös

Viitteet

Bibliografia

Dijkstra, Edsger W. (1960). "Rekursiivinen ohjelmointi". Numeron matematiikka . 2 (1): 312–318. doi : 10.1007/BF01386232 . S2CID 127891023 .
Johnsonbaugh, Richard (2004). Erillinen matematiikka . Prentice Hall. ISBN 978-0-13-117686-7.
Hofstadter, Douglas (1999). Gödel, Escher, Bach: ikuinen kultainen punos . Peruskirjat. ISBN 978-0-465-02656-2.
Shoenfield, Joseph R. (2000). Rekursioteoria . AK Peters Ltd. ISBN 978-1-56881-149-9.
Causey, Robert L. (2001). Logiikka, sarjat ja rekursio . Jones & Bartlett. ISBN 978-0-7637-1695-0.
Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). Rekursioteoria, Gödelin lauseet, joukkoteoria, malliteoria . Oxford University Press. ISBN 978-0-19-850050-6.
Barwise, Jon ; Moss, Lawrence S. (1996). Noidat piirit . Stanfordin yliopisto kielen ja tiedon tutkimukselle. ISBN 978-0-19-850050-6. - tarjoaa hoitoa ydinkurssille .
Rosen, Kenneth H. (2002). Diskreetti matematiikka ja sen sovellukset . McGraw-Hill College. ISBN 978-0-07-293033-7.
Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Johdatus algoritmeihin . Mit Pr. ISBN 978-0-262-03293-3.
Kernighan, B .; Ritchie, D. (1988). C -ohjelmointikieli . Prentice Hall. ISBN 978-0-13-110362-7.
Stokey, Nancy; Robert Lucas; Edward Prescott (1989). Rekursiiviset menetelmät talousdynamiikassa . Harvard University Press. ISBN 978-0-674-75096-8.
Hungerford (1980). Algebra . Springer. ISBN 978-0-387-90518-1., joukon teorian ensimmäinen luku.

Ulkoiset linkit

Rekursio - opetusohjelma Alan Gauld
Zip -tiedostot koko ajan
Nevins, Andrew ja David Pesetsky ja Cilene Rodrigues. Todisteet ja väitteet: vastaus Everettille (2009). Kieli 85.3: 671--681 (2009)

Languages

In other projects