Rekursjon - Recursion

En visuell form for rekursjon kjent som Droste -effekten . Kvinnen i dette bildet har et objekt som inneholder et mindre bilde av henne som holder et identisk objekt, som igjen inneholder et mindre bilde av seg selv som holder et identisk objekt, og så videre. 1904 Droste kakao tinn, designet av Jan Misset

Rekursjon (adjektiv: rekursiv ) oppstår når en ting er definert i form av seg selv eller av dens type. Rekursjon brukes i en rekke disipliner som spenner fra lingvistikk til logikk . Den vanligste anvendelsen av rekursjon er i matematikk og informatikk , der en funksjon som defineres brukes innenfor sin egen definisjon. Selv om dette tilsynelatende definerer et uendelig antall forekomster (funksjonsverdier), gjøres det ofte på en slik måte at ingen uendelig sløyfe eller uendelig referansekjede kan forekomme.

Formelle definisjoner

Ouroboros , et gammelt symbol som skildrer en slange eller drage som spiser sin egen hale.

I matematikk og informatikk viser en klasse med objekter eller metoder rekursiv atferd når den kan defineres av to egenskaper:

• En enkel basesak (eller saker) - et avsluttende scenario som ikke bruker rekursjon for å gi et svar
• Et rekursivt trinn - et sett med regler som reduserer alle påfølgende saker mot grunnsaken.

For eksempel er følgende en rekursiv definisjon av en persons stamfar . Ens forfader er enten:

• Ens forelder ( grunnleggende sak ), eller
• Ens foreldres stamfar ( rekursivt trinn ).

Den Fibonacci sekvensen er et klassisk eksempel på rekursjon:

Fib (0) = 0 som grunnkasse 1,

Fib (1) = 1 som grunnkasse 2,

For alle heltall n > 1 , Fib ( n ) = Fib ( n - 1) + Fib ( n - 2) .

Mange matematiske aksiomer er basert på rekursive regler. For eksempel kan den formelle definisjonen av de naturlige tallene med Peano -aksiomene beskrives som: "Null er et naturlig tall, og hvert naturlig tall har en etterfølger, som også er et naturlig tall." Ved denne basistasjen og rekursive regelen kan man generere settet med alle naturlige tall.

Andre rekursivt definerte matematiske objekter inkluderer factorials , funksjoner (f.eks. Gjentakelsesrelasjoner ), sett (f.eks. Cantor ternary sett ) og fraktaler .

Det finnes forskjellige flere tunge-i-kinn definisjoner av rekursjon; se rekursiv humor .

Uformell definisjon

Nylig forfrisket surdeig , som bobler gjennom gjæring : oppskriften krever litt surdeig til overs fra siste gang den samme oppskriften ble laget.

Rekursjon er prosessen en prosedyre går gjennom når et av trinnene i prosedyren innebærer å påkalle selve prosedyren. En prosedyre som går gjennom rekursjon sies å være 'rekursiv'.

For å forstå rekursjon må man gjenkjenne skillet mellom en prosedyre og en prosedyre. En prosedyre er et sett med trinn basert på et sett med regler, mens kjøring av en prosedyre innebærer å faktisk følge reglene og utføre trinnene.

Rekursjon er relatert til, men ikke det samme, som en referanse innenfor spesifikasjonen av en prosedyre til utførelsen av en annen prosedyre.

Når en prosedyre er definert som sådan, skaper dette umiddelbart muligheten for en endeløs sløyfe; rekursjon kan bare brukes riktig i en definisjon hvis det aktuelle trinnet hoppes over i visse tilfeller slik at prosedyren kan fullføres.

Men selv om den er riktig definert, er det ikke lett for mennesker å utføre en rekursiv prosedyre, ettersom den krever at den nye skilles fra den gamle, delvis utførte påkallelsen av prosedyren; dette krever en viss administrasjon av hvor langt ulike samtidige forekomster av prosedyrene har kommet. Av denne grunn er rekursive definisjoner svært sjeldne i dagligdagse situasjoner.

På språk

Lingvist Noam Chomsky , blant mange andre, har hevdet at mangelen på en øvre grense for antall grammatiske setninger på et språk, og mangel på en øvre grense for grammatisk setningslengde (utover praktiske begrensninger som tiden som er tilgjengelig for å si et ), kan forklares som en konsekvens av rekursjon i naturlig språk.

Dette kan forstås i form av en rekursiv definisjon av en syntaktisk kategori, for eksempel en setning. En setning kan ha en struktur der det som følger verbet er en annen setning: Dorothy tror hekser er farlige , der setningen hekser er farlige forekommer i den større. Så en setning kan defineres rekursivt (veldig grovt) som noe med en struktur som inneholder en substantivfrase, et verb og eventuelt en annen setning. Dette er egentlig bare et spesielt tilfelle av den matematiske definisjonen av rekursjon.

Dette gir en måte å forstå kreativitet språk det ubegrenset antall grammatiske setninger-fordi det umiddelbart spår at setninger kan være av vilkårlig lengde: Dorothy mener at Toto mistenker at Tin Man sa at ... . Det er mange strukturer bortsett fra setninger som kan defineres rekursivt, og derfor mange måter en setning kan bygge inn forekomster av en kategori i en annen. Gjennom årene har språk generelt vist seg egnet for denne typen analyse.

Nylig har imidlertid den allment aksepterte ideen om at rekursjon er en vesentlig egenskap for menneskelig språk blitt utfordret av Daniel Everett på grunnlag av hans påstander om Pirahã -språket . Andrew Nevins, David Pesetsky og Cilene Rodrigues er blant mange som har argumentert mot dette. Litterær selvreferanse kan uansett argumenteres for å være annerledes enn matematisk eller logisk rekursjon.

Rekursjon spiller en avgjørende rolle ikke bare i syntaks, men også i semantikk i naturlig språk . Ordet og kan for eksempel tolkes som en funksjon som kan gjelde setningsbetydninger for å lage nye setninger, og på samme måte for substantivfrasebetydninger, betydninger av verbfraser og andre. Det kan også gjelde intransitive verb, transitive verb eller ditransitive verb. For å gi en enkelt betegnelse for den som er passende fleksibel, og som vanligvis er definert slik at den kan ta noen av disse forskjellige typene betydninger som argumenter. Dette kan gjøres ved å definere det for et enkelt tilfelle der det kombinerer setninger, og deretter definere de andre sakene rekursivt når det gjelder det enkle.

En rekursiv grammatikk er en formell grammatikk som inneholder rekursive produksjonsregler .

Rekursiv humor

En rekursiv Wikipedia -side

Rekursjon brukes noen ganger humoristisk i datavitenskap, programmering, filosofi eller matematikkbøker, vanligvis ved å gi en sirkulær definisjon eller selvreferanse , der det antatte rekursive trinnet ikke kommer nærmere et grunnleggende tilfelle, men i stedet fører til en uendelig tilbakegang . Det er ikke uvanlig at slike bøker inkluderer en vitsoppføring i ordlisten i tråd med:

Rekursjon, se Rekursjon .

En variant finnes på side 269 i indeksen til noen utgaver av Brian Kernighan og Dennis Ritchies bok The C Programming Language ; indeksoppføringen refererer til seg selv rekursivt ("rekursjon 86, 139, 141, 182, 202, 269"). Tidlige versjoner av denne vitsen finnes i Let's talk Lisp av Laurent Siklóssy (utgitt av Prentice Hall PTR 1. desember 1975, med en opphavsrettsdato fra 1976) og i Software Tools av Kernighan og Plauger (utgitt av Addison-Wesley Professional på 11. januar 1976). Vitsen vises også i UNIX Programming Environment av Kernighan og Pike. Den dukket ikke opp i den første utgaven av The C Programming Language . Vitsen er en del av Functional programming folklore og var allerede utbredt i det funksjonelle programmeringssamfunnet før utgivelsen av de nevnte bøkene.

En annen spøk er at "For å forstå rekursjon, må du forstå rekursjon." I den engelskspråklige versjonen av Googles nettsøkemotor, når et søk etter "rekursjon" foretas, foreslår nettstedet "Did you mean: recursion ." En alternativ form er følgende, fra Andrew Plotkin : "Hvis du allerede vet hva rekursjon er, bare husk svaret. Ellers finn noen som står nærmere Douglas Hofstadter enn deg; så spør ham eller henne hva rekursjon er."

Rekursive akronymer er andre eksempler på rekursiv humor. PHP , for eksempel, står for "PHP Hypertext Preprocessor", WINE står for "WINE Is Not an Emulator" GNU står for "GNU's not Unix", og SPARQL betegner "SPARQL Protocol and RDF Query Language".

I matematikk

Den Sierpinski trekant -en begrenset rekursjon av trekanter som danner en fraktal

Rekursivt definerte sett

Eksempel: de naturlige tallene

Det kanoniske eksempelet på et rekursivt definert sett er gitt av de naturlige tallene :

0 er inne ${\ displaystyle \ mathbb {N}}$

hvis n er i , så er n + 1 in${\ displaystyle \ mathbb {N}}$${\ displaystyle \ mathbb {N}}$

Settet med naturlige tall er det minste settet som tilfredsstiller de to foregående egenskapene.

I matematisk logikk er Peano -aksiomene (eller Peano -postulatene eller Dedekind - Peano -aksiomene) aksiomer for de naturlige tallene som ble presentert på 1800 -tallet av den tyske matematikeren Richard Dedekind og av den italienske matematikeren Giuseppe Peano . Peano -aksiomene definerer de naturlige tallene som refererer til en rekursiv etterfølgerfunksjon og tillegg og multiplikasjon som rekursive funksjoner.

Eksempel: Prosedyre

Et annet interessant eksempel er settet med alle "bevisbare" proposisjoner i et aksiomatisk system som er definert i form av en bevisprosedyre som er induktivt (eller rekursivt) definert som følger:

• Hvis et forslag er et aksiom, er det et bevis som kan bevises.
• Hvis et forslag kan stammer fra sanne forslag som kan nås ved hjelp av slutningsregler, er det et bevis som kan bevises.
• Settet med bevisbare forslag er det minste settet med forslag som tilfredsstiller disse betingelsene.

Endelige inndelingsregler

Endelige inndelingsregler er en geometrisk form for rekursjon, som kan brukes til å lage fraktallignende bilder. En underavdelingsregel starter med en samling polygoner merket med endel mange etiketter, og deretter blir hver polygon delt inn i mindre merkede polygoner på en måte som bare avhenger av etikettene til den opprinnelige polygonen. Denne prosessen kan gjentas. Standard `` mellomtredjedels '' teknikk for å lage Cantor -settet er en underavdelingsregel, det samme er barycentrisk underavdeling .

Funksjonell rekursjon

En funksjon kan defineres rekursivt i form av seg selv. Et kjent eksempel er Fibonacci -tallsekvensen: F ( n ) = F ( n - 1) + F ( n - 2). For at en slik definisjon skal være nyttig, må den reduseres til ikke-rekursivt definerte verdier: i dette tilfellet F (0) = 0 og F (1) = 1.

En berømt rekursiv funksjon er Ackermann -funksjonen , som i motsetning til Fibonacci -sekvensen ikke kan uttrykkes uten rekursjon.

Bevis som involverer rekursive definisjoner

Ved å bruke standard bevisteknikk etter saker på rekursivt definerte sett eller funksjoner, som i de foregående seksjonene, får man strukturell induksjon - en kraftig generalisering av matematisk induksjon som er mye brukt for å utlede bevis i matematisk logikk og datavitenskap.

Rekursiv optimalisering

Dynamisk programmering er en tilnærming til optimalisering som gjentar et multiperiod- eller flertrinnsoptimaliseringsproblem i rekursiv form. Hovedresultatet i dynamisk programmering er Bellman -ligningen , som skriver verdien av optimaliseringsproblemet på et tidligere tidspunkt (eller tidligere trinn) når det gjelder verdien på et senere tidspunkt (eller senere trinn).

Rekursjonsteoremet

I settteori er dette et teorem som garanterer at det finnes rekursivt definerte funksjoner. Gitt et sett X , et element a av X og en funksjon f : X → X , sier teoremet at det er en unik funksjon (hvor betegner settet med naturlige tall inkludert null) slik at ${\ displaystyle F: \ mathbb {N} \ til X}$${\ displaystyle \ mathbb {N}}$

${\ displaystyle F (0) = a}$

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

for ethvert naturlig nummer n .

Bevis på unikhet

Ta to funksjoner og slik at: ${\ displaystyle F: \ mathbb {N} \ til X}$${\ displaystyle G: \ mathbb {N} \ til X}$

${\ displaystyle F (0) = a}$

${\ displaystyle G (0) = a}$

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

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

hvor en er et element av x .

Det kan bevises ved matematisk induksjon at F ( n ) = G ( n ) for alle naturlige tall n :

Grunnfall : F (0) = a = G (0) så likestillingen gjelder for n = 0 .

Induktivt trinn : Anta at F ( k ) = G ( k ) for noen . Deretter er F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1) . ${\ displaystyle k \ in \ mathbb {N}}$

Derav F ( k ) = G ( k ) betyr F ( k + 1) = G ( k + 1) .

Ved induksjon er F ( n ) = G ( n ) for alle . ${\ displaystyle n \ in \ mathbb {N}}$

I informatikk

En vanlig forenklingsmetode er å dele et problem i delproblemer av samme type. Som en dataprogrammeringsteknikk kalles dette dele og erobre og er nøkkelen til utformingen av mange viktige algoritmer. Del og erobre fungerer som en ovenfra og ned tilnærming til problemløsning, der problemer løses ved å løse mindre og mindre forekomster. En motsatt tilnærming er dynamisk programmering . Denne tilnærmingen fungerer som en bottom-up-tilnærming, der problemer løses ved å løse større og større forekomster, til ønsket størrelse er nådd.

Et klassisk eksempel på rekursjon er definisjonen av faktorfunksjonen , gitt her i C -kode:

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

Funksjonen kaller seg rekursivt på en mindre versjon av inngangen (n - 1)og multipliserer resultatet av det rekursive anropet med n, inntil den når basetasjen , analogt med den matematiske definisjonen av factorial.

Rekursjon i dataprogrammering er eksemplifisert når en funksjon er definert i form av enklere, ofte mindre versjoner av seg selv. Løsningen på problemet blir deretter utviklet ved å kombinere løsningene som er oppnådd fra de enklere versjonene av problemet. Et eksempel på anvendelse av rekursjon er i parsere for programmeringsspråk. Den store fordelen med rekursjon er at et uendelig sett med mulige setninger, design eller andre data kan defineres, analyseres eller produseres av et begrenset dataprogram.

Gjentagelsesrelasjoner er ligninger som definerer en eller flere sekvenser rekursivt. Noen spesifikke typer gjentagelsesrelasjoner kan "løses" for å oppnå en ikke-rekursiv definisjon (f.eks. Et uttrykk i lukket form ).

Bruk av rekursjon i en algoritme har både fordeler og ulemper. Den største fordelen er vanligvis enkelheten i instruksjonene. Den største ulempen er at minnebruk av rekursive algoritmer kan vokse veldig raskt, noe som gjør dem upraktiske i større tilfeller.

I biologi

Former som ser ut til å ha blitt skapt ved rekursive prosesser, vises noen ganger i planter og dyr, for eksempel i forgreningsstrukturer der en stor del forgrener seg ut i to eller flere lignende mindre deler. Et eksempel er Romanesco brokkoli .

I art

Rekursive dukker: det originale settet med Matryoshka -dukker av Zvyozdochkin og Malyutin , 1892

Frontflaten av Giotto 's Stefaneschi Triptych , 1320, inneholder rekursivt et bilde på seg selv (holdt oppe av den knelende tall i det sentrale panel).

Den russiske dukken eller Matryoshka -dukken er et fysisk kunstnerisk eksempel på det rekursive konseptet.

Rekursjon har vært brukt i malerier siden Giotto 's Stefaneschi Triptych , laget i 1320. Den sentrale panel inneholder knelende skikkelse Cardinal Stefaneschi, holder opp alterskap i seg selv som et offer.

MC Escher 's Print Gallery (1956) er en utskrift som viser et forvrengt byen inneholder et galleri som rekursivt inneholder bildet, og så ad infinitum .

Se også

Referanser

Bibliografi

Eksterne linker

• Rekursjon - opplæring av Alan Gauld
• Zip -filer helt ned
• Nevins, Andrew og David Pesetsky og Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Språk 85.3: 671--681 (2009)