Rekursion

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 oktober 2021; kontroller kräver 8 redigeringar .

Rekursion är definitionen, beskrivningen, bilden av ett objekt eller en process inom detta objekt eller själva processen, det vill säga situationen när objektet är en del av sig självt. Termen "rekursion" används inom olika speciella kunskapsområden - från lingvistik till logik , men finner den bredaste tillämpningen inom matematik och datavetenskap .

I matematik

I matematik hänvisar rekursion till metoden att definiera funktioner och talserier: en rekursivt given funktion bestämmer sitt värde genom att referera till sig själv med andra argument. I det här fallet är två alternativ möjliga:

Slutlig rekursiv funktion. Den är inställd på ett sådant sätt att för varje finita argument, efter ett ändligt antal rekursiva anrop, leder det till ett av de separat definierade specialfallen som utvärderas utan rekursion. Ett klassiskt exempel: den rekursivt definierade faktorialen för ett icke-negativt heltal: . Här görs varje efterföljande rekursivt anrop med ett argument mindre än ett. Eftersom n per definition är ett icke-negativt heltal, efter n rekursiva anrop, kommer utvärderingen av funktionen garanterat att komma till ett specialfall där rekursionen upphör. Sålunda, trots definitionens rekursivitet, kommer beräkningen av funktionen för alla argument från definitionsdomänen att vara ändlig. $n!=\begin{cases}n\cdot(n-1)!,&n>0\\1,&n=0\end{cases}$ $0!=1$
Oändlig rekursiv funktion. Den ges som en referens till sig själv i alla fall (åtminstone för några av argumenten). Oändliga serier, oändliga fortsatta bråk och så vidare kan specificeras på liknande sätt. Den praktiska beräkningen av det exakta värdet här är naturligtvis omöjlig, eftersom det kommer att kräva oändlig tid. Det erforderliga resultatet hittas med analytiska metoder. Ändå, om vi inte talar om att erhålla ett absolut exakt värde, utan om att beräkna en given approximation av det önskade värdet, är det i vissa fall möjligt att direkt använda den rekursiva definitionen: beräkningar utförs på den tills den erforderliga noggrannheten är nådde. Ett exempel är den fortsatta bråkexpansionen av talet e :

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

, var

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

Direkt beräkning enligt ovanstående formel kommer att orsaka oändlig rekursion, men det kan bevisas att värdet på f (n) tenderar till enhet när n ökar (därför, trots seriens oändlighet, är värdet på Eulertalet ändligt) . För en ungefärlig beräkning av värdet på e räcker det att på konstgjord väg begränsa rekursionsdjupet till något förutbestämt antal och, när man når det, använda ett istället.

f(n)

Ett annat exempel på rekursion i matematik är en talsekvens , given av en rekursiv formel , där varje på varandra följande term i sekvensen beräknas som ett resultat av en funktion av de n föregående termerna. Således, med hjälp av ett ändligt uttryck (som är en kombination av en rekursiv formel och en uppsättning värden för de första n termerna i en serie), kan en oändlig sekvens definieras.

Nära besläktad med rekursion är matematisk induktion : det är ett naturligt sätt att bevisa egenskaperna hos funktioner på naturliga tal , givet rekursivt i termer av deras mindre värden.

Inom matematiken betraktas en klass av så kallade "primitivt rekursiva" funktioner separat. Definitionen av en primitiv rekursiv funktion är också rekursiv, den definierar en uppsättning primitiva funktioner och en uppsättning regler; en funktion är primitiv rekursiv om den kan representeras som en kombination av primitiva rekursiva funktioner bildade enligt dessa regler.

Exempel på rekursion i matematik:

Gauss-Jordan-metoden för att lösa system av linjära algebraiska ekvationer är rekursiv.
Den redan nämnda faktorialen för ett icke-negativt heltal.
Fibonacci-tal definieras med hjälp av återfallsrelationen : Det första och andra Fibonacci-talet är 1 För , -e är Fibonacci-talet lika med summan av -th och -th Fibonacci-talen $n>2$ $n$ $(n-1)$ $(n-2)$
Nästan alla geometriska fraktaler ges i form av en oändlig rekursion (till exempel Sierpinski-triangeln ).
Ett standardexempel på en beräkningsbar rekursiv funktion som inte är primitiv rekursiv är Ackermann-funktionen : för icke-negativa heltal och enligt följande: $m$ $n$

A(m,\;n)=\begin{fall}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}

I programmering

Funktioner

I programmering är rekursion ett anrop till en funktion ( procedur ) från sig själv, direkt ( enkel rekursion ) eller genom andra funktioner ( komplex eller indirekt rekursion ), till exempel en funktion anropar en funktion och en funktion anropar en funktion . Antalet kapslade funktions- eller proceduranrop kallas rekursionsdjupet. Ett rekursivt program låter dig beskriva en upprepande eller till och med potentiellt oändlig beräkning, och utan explicit upprepning av delar av programmet och användning av loopar. $A$ $B$ $B$ $A$

En strukturellt rekursiv funktion på toppnivån är alltid en greninstruktion (val av ett av två eller flera alternativ beroende på villkoren, vilket i detta fall är lämpligt att kalla "rekursionsavslutningsvillkoret"), som har två eller flera alternativa grenar, av vilka även om minst en är rekursiv och minst en är terminal . Den rekursiva grenen exekveras när rekursionsavslutningsvillkoret är falskt och innehåller åtminstone ett rekursivt anrop - ett direkt eller indirekt anrop av funktionen till sig själv. Terminalgrenen exekveras när rekursionsavslutningsvillkoret är sant; den returnerar något värde utan att göra ett rekursivt anrop. En välskriven rekursiv funktion måste säkerställa att efter ett ändligt antal rekursiva anrop uppnås rekursionsavslutningsvillkoret, vilket får kedjan av successiva rekursiva anrop att bryta och återvända.

Förutom funktioner som gör ett rekursivt anrop på varje rekursiv gren, finns det fall av "parallell rekursion" där två eller flera rekursiva anrop görs på samma rekursiva gren. Parallell rekursion är typiskt vid bearbetning av komplexa datastrukturer såsom träd. Det enklaste exemplet på en parallell-rekursiv funktion är beräkningen av Fibonacci-serien, där för att få värdet på den n:te termen är det nödvändigt att beräkna (n-1)-th och (n-2)-th .

Implementeringen av rekursiva funktionsanrop i praktiskt använda språk och programmeringsmiljöer förlitar sig som regel på anropsstackmekanismen - funktionens returadress och lokala variabler skrivs till stacken , på grund av vilket varje nästa rekursiva anrop till den här funktionen använder sin egen uppsättning lokala variabler och på grund av detta fungerar den korrekt. Baksidan av denna ganska enkla mekanism är att varje rekursivt anrop kräver en viss mängd dator- RAM , och om rekursionen är för djup kan anropsstacken svämma över .

Frågan om önskvärdheten av att använda rekursiva funktioner i programmering är tvetydig: å ena sidan kan den rekursiva formen vara strukturellt enklare och tydligare, särskilt när den implementerade algoritmen i sig är väsentligen rekursiv. Dessutom har vissa deklarativa eller rent funktionella språk (som Prolog eller Haskell ) helt enkelt inte syntaktiska medel för att organisera loopar, och rekursion i dem är den enda tillgängliga mekanismen för att organisera upprepade beräkningar. Å andra sidan rekommenderas det generellt att undvika rekursiva program som leder (eller under vissa omständigheter kan leda) till för stort rekursionsdjup. Exemplet med rekursiv beräkning av faktorial, som är utbrett i utbildningslitteraturen, är alltså snarare ett exempel på hur man inte använder rekursion, eftersom det leder till ett tillräckligt stort rekursionsdjup och har en uppenbar implementering i form av en konventionell cyklisk algoritm.

Det finns en speciell typ av rekursion som kallas " svansrekursion " (strukturen av en rekursiv algoritm är sådan att det rekursiva anropet är den sista operationen som utförs i funktionen, och dess resultat returneras direkt som resultatet av funktionen). Tolkar och kompilatorer av funktionella programmeringsspråk som stöder kodoptimering (källa eller körbar) konverterar automatiskt svansrekursion till iteration , vilket säkerställer exekvering av svansrekursionsalgoritmer i en begränsad mängd minne. Sådana rekursiva beräkningar, även om de formellt är oändliga (till exempel när man använder rekursion för att organisera arbetet i ett skal som accepterar användarkommandon), leder aldrig till minnesutmattning . Men programmeringsspråksstandarder definierar inte alltid tydligt exakt vilka villkor en rekursiv funktion måste uppfylla för att översättaren ska garanteras omvandla den till en iteration. Ett av de sällsynta undantagen är Scheme-språket ( en dialekt av Lisp-språket ), vars beskrivning innehåller all nödvändig information.

Teoretiskt kan alla rekursiva funktioner ersättas av en loop och en stack . En sådan modifiering är dock som regel meningslös, eftersom den bara leder till att den automatiska lagringen av sammanhanget i anropsstacken ersätts med manuell exekvering av samma operationer med samma eller mer minnesförbrukning. Ett undantag kan vara situationen när den rekursiva algoritmen måste modelleras på ett språk där rekursion är förbjuden.

Bevis på att programmen är korrekta

Till skillnad från explicit cykliska program, finns det inget behov av att artificiellt introducera en invariant för att bevisa riktigheten av rekursiva . Det analytiska beviset för riktigheten av en rekursiv funktion reduceras till metoden för matematisk induktion, det vill säga till beviset för följande påståenden:

Korrekthet av rekursiv inversion. Det är bevisat att resultatet som beräknas i någon rekursiv gren av funktionen kommer att vara korrekt, förutsatt att funktionsparametrarna är korrekt inställda och motsvarande rekursiva anrop returnerar det korrekta resultatet.
Korrekthet av alla terminalgrenar. Det är bevisat att alla terminalgrenar returnerar korrekta värden. Som regel är detta bevis trivialt, eftersom terminalgrenarna vanligtvis inte innehåller några beräkningar.
Nåbarhet för en terminalgren för valfri korrekt uppsättning parametrar efter ett ändligt antal rekursiva anrop. Det är bevisat att ändring av parametrarna för ett funktionsanrop, som utförs under ett rekursivt anrop, efter ett ändligt antal rekursiva anrop, kommer att leda till en av parameteruppsättningarna för vilka det finns en terminalgren.

Det följer av summan av de första och andra påståendena att om terminalgrenen nås (och detta betyder i alla fall när beräkningen av funktionen visar sig vara slutgiltig), kommer funktionen att returnera det korrekta resultatet. Den tredje propositionen bevisar att varje beräkning kommer att vara finit. Därför kommer alla funktionsanrop med rätt parametrar att returnera det korrekta resultatet (med den uppenbara "tekniska" varningen - om rekursionsdjupet inte är så stort att det orsakar ett minnesspill).

Data

Rekursiv datadefinition uppstår när en datastruktur (post, objekt) innehåller ett kapslat objekt som är strukturellt likt sig självt eller (oftast) en referens till samma objekt. Fördelen med att rekursivt definiera ett objekt är att en sådan finit definition kan beskriva en potentiellt oändlig datastruktur. Liknande strukturer används vid beskrivning av listor och grafer . Listbeskrivningsexempel ( C ):

struct element_of_list { struct element_of_list * nästa ; /* pekare till nästa element av samma typ */ intdata ; _ /* lite data */ };

Eftersom ett oändligt antal kapslade objekt inte kan passa in i ändligt minne, är sådana rekursivt definierade strukturer i verkligheten alltid ändliga. I de sista (terminala) cellerna skrivs vanligtvis tomma pekare, som också är flaggor som indikerar för programmet som bearbetar strukturen att dess slut har nåtts.

Den rekursiva datastrukturen orsakar ofta användningen av rekursion för att bearbeta dessa data. Under de senaste åren har konceptet med så kallad " lat utvärdering " blivit populärt, enligt vilken data som bearbetas av programmet beräknas endast när det behövs. Implementeringen av detta koncept har lett till uppkomsten på vissa språk ( Haskell , Python ) av förmågan att beskriva potentiellt oändliga, inklusive rekursiva sekvenser utan explicita begränsningar för generering av objekt och fritt arbeta med dem.

I fysik

Ett klassiskt exempel på oändlig rekursion är två speglar placerade mitt emot varandra : de bildar två korridorer av minskande spegelreflektioner.

Ett annat exempel på oändlig rekursion är självexciteringseffekten (positiv återkoppling) hos elektroniska förstärkningskretsar, när signalen från utgången går till ingången, förstärks, går tillbaka till kretsens ingång och förstärks igen. Förstärkare för vilka detta driftsätt är standard kallas självoscillatorer .

Inom lingvistik

Inom lingvistik är rekursion ett språks förmåga att generera kapslade meningar och konstruktioner. Grundsatsen " katten åt musen " kan utökas med rekursion som " Vanya gissade att katten åt musen" , ytterligare som " Katya vet att Vanya gissade att katten åt musen", och så vidare. Rekursion anses vara en av de språkliga universalerna , det vill säga det är karakteristiskt för alla naturliga språk. Emellertid har den möjliga frånvaron av rekursion i ett av språken i Amazonas - Pirahana , vilket noteras av lingvisten Daniel Everett [1] , nyligen aktivt diskuterats .

I kulturen

De flesta skämten om rekursion handlar om oändlig rekursion, där det inte finns något utgångsvillkor, till exempel är talesättet känt: "för att förstå rekursion måste du först förstå rekursion" .
- Ett mycket populärt skämt om rekursion, som påminner om en ordbokspost:

rekursion se rekursion

Temat rekursion finns i många berättelser och essäer av den argentinske författaren Jorge Luis Borges .
Flera berättelser av Stanislav Lem ägnas åt (möjliga) incidenter med oändlig rekursion:
- en berättelse från Cyberiad om en rationell maskin som var smart nog och lat nog att bygga en liknande för att lösa ett givet problem och anförtro lösningen till det (resultatet blev en oändlig rekursion, när varje ny maskin byggde en liknande och överförde uppgift till det);
- en berättelse om Iyon the Quiet "The Fourteenth Journey" från " Star Diaries of Iyon the Quiet ", där hjälten successivt går från en artikel om gravar till en artikel om sepulering, därifrån till en artikel om sepulkaria, där det finns är återigen en referens till artikeln "sepulks":

Jag hittade följande korta information:
"SEPULS är ett viktigt inslag i Ardrites civilisation (se) från planeten Enteropia (se). Se SEPULCARIA.
Jag följde detta råd och läste:
"SEPULCARIA - enheter för sepulation (q.v.)".
Jag sökte efter "Sepulenia"; det löd:
”SEPULATION - ockupationen av Ardrits (se) från planeten Enteropia (se). Se SEPULS.

Lem S. ”The Star Diaries of Iyon the Quiet. Resan fjorton.

Rekursiva akronymer : GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor), WINE ( Wine Is Not an Emulator ), etc.
Ryska federationens vapen är ett rekursivt definierat grafiskt objekt: i den högra tassen på den dubbelhövdade örnen som avbildas på den, är en spira fastspänd, som kröns med en reducerad kopia av vapenskölden. Eftersom det på detta vapen även finns en spira i örnens högra tass, erhålls en oändlig rekursion.

Se även

Anteckningar

↑ Om rekursion inom lingvistik, dess varianter och de mest karakteristiska manifestationerna på det ryska språket beskrivs i artikeln av E. A. Lodatko "Recursive Linguistic Structures" Arkivexemplar av 4 mars 2009 på Wayback Machine

Länkar

Artikel i Encyclopedia Foundation // Rekursion

fraktaler
Egenskaper	fraktal dimension Hausdorff dimension Lebesgue dimension rekursion självlikhet
De enklaste fraktalerna	Fern Barnsley Kantor set drakekurva Koch kurva Svamp Menger Sierpinski matta Sierpinski triangel Utrymmesfyllande kurva
konstig attraktion	Multifraktal
L-system	Utrymmesfyllande kurva
Bifurkationsfraktaler	Julia set Lyapunov fraktal Mandelbrot set Newtons pooler
Slumpmässiga fraktaler	Brownsk rörelse brunt träd fraktal yta Perkolationsteori
människor	Georg Kantor Felix Hausdorff Gaston Julia Helge von Koch Paul Levy Alexander Lyapunov Benoit Mandelbrot Lewis Richardson Vaclav Sierpinski
Relaterade ämnen	Hur lång är Storbritanniens kust? » Kustlinjeparadox