Ömsesidig rekursion

Inom matematik och programmering är ömsesidig rekursion en typ av rekursion där två matematiska eller programobjekt, såsom funktioner eller datatyper, definieras i termer av varandra [1] . Ömsesidig rekursion är vanligt inom funktionell programmering och i vissa problemområden som den rekursiva descentmetoden , där datatyper är naturligt ömsesidigt rekursiva, vilket inte är vanligt inom andra områden.

Exempel

Datatyper

Det viktigaste exemplet på data som kan definieras med ömsesidig rekursion är ett träd , som kan definieras i termer av en skog (en lista med träd). I symbolisk form:

f: [t[1], ..., t[k]] t:vf

Skog f består av en lista med träd, medan träd t består av ett par - värde v och skog f (barn). Denna definition är elegant och lätt att arbeta med eftersom trädet uttrycks i enkla termer - en lista med en typ och ett par av två typer. Denna datatyp är lämplig för många trädalgoritmer som bearbetar värden på ett sätt och hanterar förgrening på ett annat sätt.

Denna ömsesidigt rekursiva definition kan konverteras till en enda rekursiv definition med hjälp av den inbyggda skogsdefinitionen: t: v [t[1], ..., t[k]]. Trädet t är ett par - värdet v och en lista med träd (barn). Den här definitionen är mer kompakt, men allt är inte rent här - ett träd är ett par - ett värde av en typ och en lista av en annan typ, vilket kommer att kräva avveckling till definitionen ovan.

I Standard ML kan träd- och skogsdatatyper definieras ömsesidigt rekursivt enligt följande, om tomma träd är tillåtna [2] :

datatyp ' ett träd = Tom | Nod för ' a * ' en skog och ' en skog = Noll | Nackdelar med " ett träd * " en skog

Datorfunktioner

Precis som algoritmer för rekursiva datatyper kan definieras av rekursiva funktioner, kan algoritmer på ömsesidigt rekursiva datastrukturer naturligtvis definieras av ömsesidigt rekursiva funktioner. Välkända exempel inkluderar trädalgoritmer och den rekursiva härkomstmetoden . Liksom i fallet med direktrekursion är svansrekursionsoptimering nödvändig om rekursionsdjupet är stort eller inte alls begränsat. Observera att optimering av svansrekursion i allmänhet (om den anropade funktionen inte är samma som den ursprungliga funktionen, som i svansrekursion) kan vara svårare att implementera än i fallet med optimering av svansrekursion, och en effektiv implementering av ömsesidig svansrekursion kanske inte är tillgängligt på språk som enbart optimerar tail calls. I språk som Pascal , som kräver objektdefinitioner innan ett objekt kan användas, kräver ömsesidigt rekursiva funktioner en framåtriktad deklaration .

Precis som med direkt rekursiva funktioner kan omslagsfunktioner med ömsesidigt rekursiva funktioner definierade som kapslade funktioner omfattning vara användbara om de stöds. Detta är särskilt användbart för att dela data mellan flera funktioner utan att skicka parametrar.

Grundläggande exempel

Ett standardexempel på ömsesidig rekursion, som är ett visserligen konstgjort trick, avgör om ett tal är jämnt eller inte genom att definiera två separata funktioner som anropar varandra och minskar numret vid varje samtal [3] . På C:

bool is_even ( unsigned int n ) { om ( n == 0 ) returnera sant ; annan returnera är_udda ( n - 1 ); } bool is_odd ( unsigned int n ) { om ( n == 0 ) returnera falskt ; annan return is_even ( n - 1 ); }

Dessa funktioner är baserade på observationen att frågan "4 är jämnt?" motsvarar frågan "3 är udda?", vilket i sin tur motsvarar frågan "2 är jämnt", och så vidare upp till 0. Exemplet visar ömsesidig enhetsrekursion , som enkelt kan ersättas av en slinga. I det här exemplet är de ömsesidiga rekursionsanropen tail calls , och det är önskvärt att optimera tail calls så att exekvering sker på ett konstant stackutrymme. I C kommer funktioner att kräva O ( n ) stackutrymme om man inte använder hopp (goto) istället för funktionsanrop [4] . Exemplet kan konverteras till en enda rekursiv funktion is_even. I det här fallet is_odd, kan användas inline och kommer att ringa is_even, men is_evenkommer bara att ringa sig själv.

Ett exempel från en mer allmän klass av exempel, trädalgoritmen, kan delas upp i en värdeoperation och en grenoperation, och sedan kan delas upp i två ömsesidigt rekursiva funktioner, en av funktionerna verkar på trädet och anropar skogsfunktionen , den andra arbetar med skogen och anropar funktionen för trädet för varje element i skogen. På Python-språket:

def f_träd ( träd ): f_värde ( träd . värde ) f_skog ( träd . barn ) def f_skog ( skog ): för träd i skog : f_träd ( träd )

I det här fallet anropar trädfunktionen skogsfunktionen med enkel rekursion, men skogsfunktionen använder multipel rekursion på trädet .

Med hjälp av datatyperna som beskrivs ovan i Standard ML , kan trädstorleken (antal kanter) beräknas med följande ömsesidigt rekursiva funktioner [5] :

kul storlek_träd Tomt = 0 | size_tree ( Nod (_, f )) = 1 + size_forest f och size_forest Noll = 0 | size_forest ( Cons ( t , f' )) = size_tree t + size_forest f'

Ett mer detaljerat schemaexempel som räknar antalet löv i ett träd [6] :

( definiera ( räkna-löv träd ) ( om ( löv? träd ) 1 ( räkna-löv-i-skog ( barn träd )))) ( definiera ( räkna-löv-i-skog ) ( om ( null ? skog ) 0 ( + ( räkna-löv ( bilskog )) ( räkna-löv-i-skog ( cdr skog ) ))))

Dessa exempel reduceras enkelt till en enda rekursiv funktion genom att bädda in skogsfunktionen i trädfunktionen, vilket ofta görs i praktiken.

Mer avancerade exempel

Mer komplexa exempel är exempel på rekursiv härkomst , som kan implementeras på ett naturligt sätt genom att ge en funktion för varje generativ regel i grammatiken, som sedan ömsesidigt rekursivt kallar varandra. I allmänhet kommer dessa att vara flera rekursioner, när regler genereras kombinerar flera regler. Detta kan göras utan ömsesidig rekursion, genom att ha separata funktioner för varje genereringsregel, men genom att anropa en kontrollfunktion, eller genom att bearbeta hela grammatiken i en funktion.

Ömsesidig rekursion kan också användas för att implementera en tillståndsmaskin med en funktion för varje tillstånd och en enda rekursion per tillståndsändring. Detta kräver svansrekursionsoptimering om antalet tillstånd är stort eller obegränsat. Detta tillvägagångssätt kan användas som en enkel form av kooperativ multitasking . Ett liknande tillvägagångssätt för multitasking använder koroutiner som anropar varandra, där istället för att avbrytas genom att anropa en annan procedur, anropar en coroutine en annan, men avbryts inte, utan fortsätter exekveringen när den anropade koroutinen återkommer. Detta gör att enskilda koroutiner kan spara tillstånd utan att behöva skicka parametrar eller spara delade variabler.

Det finns också algoritmer som naturligt har två faser, såsom minimax (min och max), och dessa kan implementeras genom att skapa en separat ömsesidigt rekursiv funktion för varje fas, även om de också kan kombineras till en enda direkt rekursiv funktion.

Matematiska funktioner

Inom matematik är Hofstadter-sekvenserna manliga och kvinnliga ett exempel på ett par sekvenser av heltal som är ömsesidigt rekursiva.

Fraktaler kan beräknas (med den precision som krävs) med hjälp av rekursiva funktioner. Detta kan ibland göras mer elegant med ömsesidigt rekursiva siffror. Sierpinski-kurvan är ett bra exempel.

Prevalens

Ömsesidig rekursion används ofta i funktionell programmering och används ofta i program skrivna på Lisp , Scheme , ML och andra liknande språk . På språk som Prolog är ömsesidig rekursion nästan oundviklig.

Vissa programmeringsstilar avskräcker ömsesidig rekursion, och hävdar att det är svårt att skilja mellan villkor som kommer att returnera ett svar från villkor som kommer att få koden att loopa (kör för evigt utan att returnera ett svar). Peter Norvig påpekade det som ändå borde undvikas. Han säger [7] :

Om du har två ömsesidigt rekursiva funktioner som ändrar tillståndet för ett objekt, försök att flytta nästan all funktionalitet till en av dessa funktioner. Annars är det mer sannolikt att du slutar med kodduplicering.

Terminologi

Ömsesidig rekursion är också känd som indirekt rekursion , till skillnad från direkt rekursion när en funktion anropar sig själv direkt. Detta är bara en skillnad i betoning, inte en skillnad i tillvägagångssätt - "indirekt rekursion" betonar användningen av en individuell funktion, medan "ömsesidig rekursion" betonar användningen av en uppsättning funktioner snarare än en enskild individuell funktion. Till exempel, om f kallar sig själv, är det en direkt rekursion. Om f anropar g och sedan g anropar f, vilket i sin tur anropar g igen , bara ur f synvinkel , har f indirekt rekursion. Ur g- funktionens synvinkel har den också indirekt rekursion. Men från synvinkeln av uppsättningen funktioner f och g har vi ömsesidig rekursion av varandra. På samma sätt kan en uppsättning av tre eller flera funktioner anropa varandra ömsesidigt.

Reduktion till direkt rekursion

Matematiskt är en uppsättning ömsesidigt rekursiva funktioner primitivt rekursiva , vilket kan bevisas med bakåtrekursion [8] , för vilken en funktion F är konstruerad som räknar upp värdena för individuella rekursiva funktioner i interfolierad ordning: och ömsesidig rekursion skrivs om som en primitiv rekursion.

Varje ömsesidig rekursion mellan två procedurer kan reduceras till direkt rekursion genom att infoga koden för en procedur i den andra. Om det bara finns en plats där proceduren anropar en annan kan detta göras direkt, men om det finns flera sådana platser kan kodduplicering krävas. När det gäller stackanvändning fyller två ömsesidigt rekursiva procedurer stacken med en sekvens av ABABAB...-anrop, och inbäddning av procedure B i A resulterar i direkt rekursion (AB)(AB)(AB)...

Alternativt kan valfritt antal procedurer slås samman till en enda procedur som tar som argument en märkt union (eller algebraisk datatyp ) som lagrar information om proceduren som anropas och dess argument. Den sammansatta proceduren väljer en gren baserat på argumenten och exekverar lämplig kod, och använder sedan direkt rekursion för att anropa sig själv med lämpliga argument. Detta tillvägagångssätt kan ses som en trunkerad version av uteslutningen av funktioner [9] . Denna sammanslagning av funktioner kan vara användbar när vissa funktioner kan anropas med extern kod, så att det inte är möjligt att kapsla en procedur i en annan. Sådan kod måste konverteras så att proceduranrop görs genom att sammanfoga argument till en "märkt union" enligt beskrivningen ovan. Ett annat alternativ är att använda en inslagningsprocedur.

Se även

Anteckningar

  1. ↑ Rubio-Sánchez, Urquiza-Fuentes, Pareja-Flores, 2008 , sid. 235-239.
  2. ↑ Harper, 2005 , " Datumtyper ".
  3. ↑ Hutton, 2007 , 6.5 Ömsesidig rekursion, s. 53–55 .
  4. ↑ " Mutual Tail-Recursion Archived 10 April 2016 at the Wayback Machine " och " Tail-Recursive Functions Archived 10 April 2016 at the Wayback Machine ", en handledning om programmeringsfunktioner i ATS Arkiverad 27 december 2017 på Wayback Machine . Hongwei Xi, 2010
  5. ↑ Harper, 2005 , " Datatyper ".
  6. ↑ Harvey, Wright, 1999 , V. Abstraktion: 18. Trees: Mutual Recursion, pp. 310–313 .
  7. ↑ Att lösa varje Sudoku-pussel . Hämtad 13 januari 2017. Arkiverad från originalet 15 november 2020.
  8. ↑ " ömsesidig rekursion Arkiverad 21 juni 2018 på Wayback Machine " PlanetMath
  9. ↑ Reynolds, John (augusti 1972). "Definitionstolkar för högre ordningsprogrammeringsspråk" (PDF) . Handlingar från ACMs årliga konferens . Boston, Massachusetts. pp. 717-740. Arkiverad 29 juni 2011 på Wayback Machine

Litteratur

  • Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes, Cristóbal Pareja-Flores. ACM SIGCSE Bulletin. - ACM, 2008. - T. 40. - S. 235-239.
  • Robert Harper. Programmering i Standard ML (Arbetsutkast av 17 MAJ 2005.). — Carnegie Mellon University, 2005.
  • Brian Harvey, Matthew Wright. Simply Scheme: Introduktion av datavetenskap. - MIT Press, 1999. - ISBN 978-0-26208281-5 .
  • Graham Hutton. Programmering i Haskell. - Cambridge University Press, 2007. - ISBN 978-0-52169269-4 .

Länkar