Rekursion - Recursion

En visuel form for rekursion kendt som Droste -effekten . Kvinden på dette billede har et objekt, der indeholder et mindre billede af hende, der holder et identisk objekt, som igen indeholder et mindre billede af sig selv, der holder et identisk objekt, og så videre. 1904 Droste kakaoform , designet af Jan Misset

Rekursion (adjektiv: rekursiv ) opstår, når en ting er defineret ud fra sig selv eller af dens type. Rekursion bruges i en række forskellige discipliner lige fra lingvistik til logik . Den mest almindelige anvendelse af rekursion er i matematik og datalogi , hvor en funktion, der defineres, anvendes inden for sin egen definition. Selvom dette tilsyneladende definerer et uendeligt antal forekomster (funktionsværdier), gøres det ofte på en sådan måde, at der ikke kan forekomme uendelig sløjfe eller uendelig kæde af referencer.

Formelle definitioner

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

I matematik og datalogi udviser en klasse af objekter eller metoder rekursiv adfærd, når den kan defineres af to egenskaber:

• En simpel basissag (eller sager) - et afslutningsscenario, der ikke bruger rekursion til at producere et svar
• Et rekursivt trin - et regelsæt, der reducerer alle successive sager mod basissagen.

For eksempel er det følgende en rekursiv definition af en persons forfader . Ens forfader er enten:

• Ens forælder ( base case ) eller
• Ens forældres forfader ( rekursivt trin ).

Den Fibonacci sekvensen er et andet klassisk eksempel på rekursion:

Fib (0) = 0 som grundkasse 1,

Fib (1) = 1 som bundkasse 2,

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

Mange matematiske aksiomer er baseret på rekursive regler. For eksempel kan den formelle definition af de naturlige tal ved hjælp af Peano -aksiomerne beskrives som: "Nul er et naturligt tal, og hvert naturligt tal har en efterfølger, som også er et naturligt tal." Ved denne basale sag og rekursive regel kan man generere sættet med alle naturlige tal.

Andre rekursivt definerede matematiske objekter omfatter factorials , funktioner (f.eks. Gentagelsesrelationer ), sæt (f.eks. Cantor ternært sæt ) og fraktaler .

Der findes forskellige flere tunge-i-kind-definitioner på rekursion; se rekursiv humor .

Uformel definition

For nylig forfrisket surdej , der bobler gennem gæring : opskriften kræver lidt surdej tilovers fra sidste gang, den samme opskrift blev lavet.

Rekursion er den proces, en procedure gennemgår, når et af trinene i proceduren involverer at påberåbe sig selve proceduren. En procedure, der gennemgår rekursion, siges at være 'rekursiv'.

For at forstå rekursion skal man erkende sondringen mellem en procedure og afviklingen af ​​en procedure. En procedure er et sæt trin baseret på et sæt regler, mens afviklingen af ​​en procedure indebærer faktisk at følge reglerne og udføre trinene.

Rekursion er relateret til, men ikke det samme, som en henvisning inden for specifikationerne af en procedure til udførelsen af ​​en anden procedure.

Når en procedure er defineret som sådan, skaber dette straks muligheden for en endeløs sløjfe; rekursion kan kun bruges korrekt i en definition, hvis det pågældende trin i visse tilfælde springes over, så proceduren kan gennemføres.

Men selvom den er korrekt defineret, er en rekursiv procedure ikke let for mennesker at udføre, da den kræver at skelne det nye fra det gamle, delvist udførte påkaldelse af proceduren; dette kræver en vis administration af, hvor langt forskellige samtidige tilfælde af procedurerne er skredet frem. Af denne grund er rekursive definitioner meget sjældne i hverdagssituationer.

I sprog

Sprogforsker Noam Chomsky har blandt mange andre argumenteret for, at manglen på en øvre grænse for antallet af grammatiske sætninger på et sprog og manglen på en øvre grænse for den grammatiske sætningslængde (ud over praktiske begrænsninger såsom den tid, der er til rådighed for at ytre et ), kan forklares som konsekvensen af ​​rekursion i naturligt sprog.

Dette kan forstås ud fra en rekursiv definition af en syntaktisk kategori, såsom en sætning. En sætning kan have en struktur, hvor det, der følger verbet, er en anden sætning: Dorothy mener, at hekse er farlige , hvor sætningen hekse er farlige, forekommer i den større. Så en sætning kan defineres rekursivt (meget groft) som noget med en struktur, der indeholder en substantivfrase, et verbum og eventuelt en anden sætning. Dette er virkelig bare et specielt tilfælde af den matematiske definition af rekursion.

Dette giver en måde at forstå kreativitet sprog-det grænseløse antal grammatiske sætninger-fordi det straks forudsiger, at sætninger kan være af vilkårlig længde: Dorothy mener, at Toto mistanke om, at Tin Man sagde, at ... . Der er mange strukturer bortset fra sætninger, der kan defineres rekursivt, og derfor mange måder, hvorpå en sætning kan integrere forekomster af en kategori i en anden. I årenes løb har sprog generelt vist sig modtagelige for denne form for analyse.

For nylig er den generelt accepterede idé om, at rekursion er en væsentlig egenskab ved menneskeligt sprog, blevet udfordret af Daniel Everett på grundlag af hans påstande om Pirahã -sproget . Andrew Nevins, David Pesetsky og Cilene Rodrigues er blandt mange, der har argumenteret imod dette. Litterær selvreference kan under alle omstændigheder argumenteres for at have en anden art end matematisk eller logisk rekursion.

Rekursion spiller en afgørende rolle ikke kun i syntaks, men også i naturligt sprogs semantik . Ordet og kan for eksempel tolkes som en funktion, der kan gælde for sætningsbetydninger for at oprette nye sætninger og ligeledes for navneordssætninger, betydninger af udsagnsord og andre. Det kan også gælde intransitive verber, transitive verber eller ditransitive verber. For at tilvejebringe en enkelt betegnelse for den, der er passende fleksibel og typisk er defineret, så den kan tage enhver af disse forskellige typer betydninger som argumenter. Dette kan gøres ved at definere det for en simpel sag, hvor den kombinerer sætninger, og derefter definere de andre sager rekursivt i form af den simple.

En rekursiv grammatik er en formel grammatik, der indeholder rekursive produktionsregler .

Rekursiv humor

En rekursiv Wikipedia -side

Rekursion bruges undertiden humoristisk i datalogi, programmering, filosofi eller matematik lærebøger, generelt ved at give en cirkulær definition eller selvreference , hvor det formodede rekursive trin ikke kommer tættere på en basiskasse, men i stedet fører til en uendelig tilbagegang . Det er ikke usædvanligt, at sådanne bøger inkluderer en vittighedspost i deres ordliste i retning af:

Rekursion, se Rekursion .

En variation findes på side 269 i indekset over nogle udgaver af Brian Kernighan og Dennis Ritchies bog The C Programming Language ; indeksposten refererer til sig selv rekursivt ("rekursion 86, 139, 141, 182, 202, 269"). Tidlige versioner af denne vittighed findes i Let's talk Lisp af Laurent Siklóssy (udgivet af Prentice Hall PTR den 1. december 1975 med en ophavsretdato fra 1976) og i Software Tools af Kernighan og Plauger (udgivet af Addison-Wesley Professional på 11. januar 1976). Vittigheden vises også i The UNIX Programming Environment af Kernighan og Pike. Det optrådte ikke i den første udgave af The C Programming Language . Vittigheden er en del af den funktionelle programmeringsfolklore og var allerede udbredt i det funktionelle programmeringssamfund inden udgivelsen af ​​de førnævnte bøger.

En anden vittighed er, at "For at forstå rekursion skal du forstå rekursion." I den engelsksprogede version af Googles websøgemaskine, foreslår webstedet "Mente du: rekursion " , når der søges efter "rekursion" . En alternativ form er følgende fra Andrew Plotkin : "Hvis du allerede ved, hvad rekursion er, skal du bare huske svaret. Find ellers nogen, der står tættere på Douglas Hofstadter end du er; spørg ham eller hende, hvad recursion er."

Rekursive akronymer er andre eksempler på rekursiv humor. PHP står for eksempel 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 matematik

Den Sierpinski trekant -a begrænset rekursion af trekanter, som danner en fraktal

Rekursivt definerede sæt

Eksempel: de naturlige tal

Det kanoniske eksempel på et rekursivt defineret sæt er givet af de naturlige tal :

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

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

Sættet med naturlige tal er det mindste sæt, der opfylder de to foregående egenskaber.

I matematisk logik er Peano -aksiomerne (eller Peano -postulater eller Dedekind -Peano -axiomer) aksiomer for de naturlige tal, der blev præsenteret i det 19. århundrede af den tyske matematiker Richard Dedekind og af den italienske matematiker Giuseppe Peano . Peano -aksiomerne definerer de naturlige tal, der refererer til en rekursiv efterfølgerfunktion og addition og multiplikation som rekursive funktioner.

Eksempel: Bevisprocedure

Et andet interessant eksempel er sættet af alle "beviselige" forslag i et aksiomatisk system, der er defineret ud fra en bevisprocedure, der er induktivt (eller rekursivt) defineret som følger:

• Hvis et forslag er et aksiom, er det et beviseligt forslag.
• Hvis et forslag kan udledes af sande tilgængelige forslag ved hjælp af slutningsregler, er det et bevis, der kan bevises.
• Sættet med bevisbare forslag er det mindste sæt forslag, der opfylder disse betingelser.

Endelige opdelingsregler

Endelige inddelingsregler er en geometrisk form for rekursion, som kan bruges til at oprette fraktallignende billeder. En underopdelingsregel starter med en samling af polygoner mærket med uendeligt mange etiketter, og derefter opdeles hver polygon i mindre mærkede polygoner på en måde, der kun afhænger af etiketterne i den originale polygon. Denne proces kan gentages. Standarden `midter tredjedele` teknik til oprettelse af Cantor -sættet er en underopdelingsregel, ligesom barycentrisk underopdeling .

Funktionel rekursion

En funktion kan defineres rekursivt i forhold til sig selv. Et velkendt eksempel er Fibonacci -talssekvensen : F ( n ) = F ( n - 1) + F ( n - 2). For at en sådan definition er nyttig, skal den reduceres til ikke-rekursivt definerede værdier: i dette tilfælde F (0) = 0 og F (1) = 1.

En berømt rekursiv funktion er Ackermann -funktionen , som i modsætning til Fibonacci -sekvensen ikke kan udtrykkes uden rekursion.

Beviser, der involverer rekursive definitioner

Anvendelse af standard bevisteknik ved sager på rekursivt definerede sæt eller funktioner, som i de foregående afsnit, giver strukturel induktion - en kraftfuld generalisering af matematisk induktion, der i vid udstrækning bruges til at udlede beviser i matematisk logik og datalogi.

Rekursiv optimering

Dynamisk programmering er en tilgang til optimering, der gentager et problem med flere perioder eller flere trin i rekursiv form. Nøgleresultatet i dynamisk programmering er Bellman -ligningen , der skriver værdien af ​​optimeringsproblemet på et tidligere tidspunkt (eller tidligere trin) i form af dens værdi på et senere tidspunkt (eller senere trin).

Rekursionsteoremet

I sætteori er dette en sætning, der garanterer, at der findes rekursivt definerede funktioner. I betragtning af et sæt X , et element a af X og en funktion f : X → X , siger sætningen, at der er en unik funktion (hvor betegner mængden af ​​naturlige tal inklusive nul), således at ${\ displaystyle F: \ mathbb {N} \ til X}$${\ displaystyle \ mathbb {N}}$

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

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

for ethvert naturligt tal n .

Bevis for unikhed

Tag to funktioner og sådan 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 af X .

Det kan bevises ved matematisk induktion, at F ( n ) = G ( n ) for alle naturlige tal n :

Base Case : F (0) = a = G (0), så ligestillingen gælder for n = 0 .

Induktivt trin : Antag F ( k ) = G ( k ) for nogle . Derefter er F ( k + 1) = f ( F ( k )) = f ( G ( k )) = G ( k + 1) . ${\ displaystyle k \ in \ mathbb {N}}$

Derfor F ( k ) = G ( k ) betyder F ( k + 1) = G ( k + 1) .

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

Inden for datalogi

En almindelig metode til forenkling er at opdele et problem i delproblemer af samme type. Som en computerprogrammeringsteknik kaldes dette opdeling og erobring og er nøglen til design af mange vigtige algoritmer. Opdel og erobre fungerer som en top-down tilgang til problemløsning, hvor problemer løses ved at løse mindre og mindre instanser. En modsatrettet tilgang er dynamisk programmering . Denne tilgang fungerer som en bottom-up tilgang, hvor problemer løses ved at løse større og større instanser, indtil den ønskede størrelse er nået.

Et klassisk eksempel på rekursion er definitionen af ​​den faktorielle funktion, givet her i C -kode:

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

Funktionen kalder sig rekursivt på en mindre version af input (n - 1)og multiplicerer resultatet af det rekursive opkald med n, indtil den når basistasken , analogt med den matematiske definition af factorial.

Rekursion i computerprogrammering er eksemplificeret, når en funktion er defineret i form af enklere, ofte mindre versioner af sig selv. Løsningen på problemet udformes derefter ved at kombinere løsningerne fra de enklere versioner af problemet. Et eksempel på anvendelse af rekursion er i parsere til programmeringssprog. Den store fordel ved rekursion er, at et uendeligt sæt mulige sætninger, designs eller andre data kan defineres, analyseres eller produceres af et begrænset computerprogram.

Tilbagevendelsesrelationer er ligninger, der definerer en eller flere sekvenser rekursivt. Nogle bestemte former for tilbagefaldsrelation kan "løses" for at opnå en ikke-rekursiv definition (f.eks. Et udtryk i lukket form ).

Brug af rekursion i en algoritme har både fordele og ulemper. Den største fordel er normalt enkelheden i instruktionerne. Den største ulempe er, at hukommelsesforbruget af rekursive algoritmer kan vokse meget hurtigt, hvilket gør dem upraktiske i større tilfælde.

I biologi

Former, der synes at være skabt ved rekursive processer, forekommer undertiden i planter og dyr, såsom i forgreningsstrukturer, hvor en stor del forgrener sig ud i to eller flere lignende mindre dele. Et eksempel er Romanesco broccoli .

I art

Rekursive dukker: det originale sæt Matryoshka -dukker af Zvyozdochkin og Malyutin , 1892

Forsiden af Giotto 's Stefaneschi Triptych , 1320, indeholder rekursivt et billede af sig selv (holdt op af den knælende figur i det centrale panel).

Den russiske dukke eller Matryoshka -dukke er et fysisk kunstnerisk eksempel på det rekursive koncept.

Rekursion har været anvendt i malerier siden Giotto 's Stefaneschi Triptych , lavet i 1320. Dens centrale panel indeholder den knælende figur af kardinal Stefaneschi, holder op treenighed selv som et offer.

MC Escher 's Print Gallery (1956) er en udskrift, der viser et forvrænget by, der indeholder et galleri, der rekursivt indeholder billedet, og så ad infinitum .

Se også

Referencer

Bibliografi

eksterne links

• Rekursion - tutorial af Alan Gauld
• Zip -filer hele vejen ned
• Nevins, Andrew og David Pesetsky og Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Sprog 85.3: 671-681 (2009)