Gensidig rekursion

I matematik og programmering er gensidig rekursion en form for rekursion , hvor to matematiske eller programobjekter, såsom funktioner eller datatyper, er defineret i forhold til hinanden [1] . Gensidig rekursion er almindelig i funktionel programmering og i nogle problemområder såsom den rekursive descent-metode , hvor datatyper naturligt er gensidigt rekursive, hvilket ikke er almindeligt på andre områder.

Eksempler

Datatyper

Det vigtigste eksempel på data, der kan defineres ved hjælp af gensidig rekursion, er et træ , som kan defineres i form af en skov (en liste over træer). I symbolsk form:

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

Skov f består af en liste over træer, mens træ t består af et par - værdi v og skov f (børn). Denne definition er elegant og nem at arbejde med, fordi træet er udtrykt i enkle vendinger - en liste med én type og et par af to typer. Denne datatype er velegnet til mange træalgoritmer, der behandler værdier på én måde og håndterer forgrening på en anden måde.

Denne gensidigt rekursive definition kan konverteres til en enkelt rekursiv definition ved hjælp af den indbyggede skovdefinition: t: v [t[1], ..., t[k]]. Træet t er et par - værdien v og en liste over træer (børn). Denne definition er mere kompakt, men ikke alt er rent her - et træ er et par - en værdi af en type og en liste af en anden type, som vil kræve afvikling til definitionen ovenfor.

I Standard ML kan træ- og skovdatatyper defineres gensidigt rekursivt som følger, hvis tomme træer er tilladt [2] :

datatype ' et træ = Tomt | Node af ' a * ' en skov og ' en skov = Nul | Ulemper ved ' et træ * ' en skov

Computerfunktioner

Ligesom algoritmer på rekursive datatyper kan defineres af rekursive funktioner, kan algoritmer på gensidigt rekursive datastrukturer naturligvis defineres af gensidigt rekursive funktioner. Velkendte eksempler inkluderer træalgoritmer og den rekursive descent-metode . Som i tilfældet med direkte rekursion er halerekursionsoptimering nødvendig, hvis rekursionsdybden er stor eller slet ikke begrænset. Bemærk, at halerekursionsoptimering generelt (hvis den kaldte funktion ikke er den samme som den oprindelige funktion, som i halerekursion) kan være sværere at implementere end i tilfældet med halerekursionsoptimering og en effektiv implementering af gensidig halerekursion er muligvis ikke tilgængelig på sprog, der kun optimerer haleopkald. I sprog som Pascal , der kræver objektdefinitioner, før et objekt kan bruges, kræver gensidigt rekursive funktioner en fremadrettet erklæring .

Som med direkte rekursive funktioner kan indpakningsfunktioner med gensidigt rekursive funktioner defineret som indlejrede funktioner omfang være nyttige, hvis de understøttes. Dette er især nyttigt til at dele data mellem flere funktioner uden at sende parametre.

Grundlæggende eksempler

Et standardeksempel på gensidig rekursion, som ganske vist er et kunstigt trick, afgør, om et tal er lige eller ej, ved at definere to separate funktioner, der kalder hinanden og nedsætter tallet ved hvert opkald [3] . På C:

bool is_even ( unsigned int n ) { hvis ( n == 0 ) returnere sandt ; andet returner er_ulige ( n - 1 ); } bool is_odd ( usigned int n ) { hvis ( n == 0 ) returnere falsk ; andet returner er_lige ( n - 1 ); }

Disse funktioner er baseret på den observation, at spørgsmålet "4 er lige?" svarer til spørgsmålet "3 er ulige?", hvilket igen svarer til spørgsmålet "2 er lige", og så videre op til 0. Eksemplet viser gensidig enhedsrekursion , som let kan erstattes af en sløjfe. I dette eksempel er de gensidige rekursion-kald tail-kald , og det er ønskeligt at optimere tail-kaldene, således at eksekvering sker på et konstant stack-rum. I C vil funktioner kræve O ( n ) stakplads, medmindre man bruger hop (goto) i stedet for funktionskald [4] . Eksemplet kan konverteres til en enkelt rekursiv funktion is_even. I dette tilfælde is_oddkan bruges inline og vil kalde is_even, men is_evenvil kun kalde sig selv.

Et eksempel fra en mere generel klasse af eksempler, træalgoritmen, kan dekomponeres i en værdioperation og en grenoperation, og kan derefter opdeles i to gensidigt rekursive funktioner, en af funktionerne opererer på træet og kalder skovfunktionen , den anden arbejder med skoven og kalder funktionen for træet for hvert element i skoven. På Python-sprog:

def f_træ ( træ ): f_værdi ( træ . værdi ) f_skov ( træ . børn ) def f_skov ( skov ): for træ i skoven : f_træ ( træ )

I dette tilfælde kalder træfunktionen skovfunktionen ved hjælp af enkelt rekursion, men skovfunktionen bruger multipel rekursion på træet .

Ved at bruge datatyperne beskrevet ovenfor i Standard ML , kan træstørrelsen (antal kanter) beregnes ved hjælp af følgende gensidigt rekursive funktioner [5] :

sjov størrelse_træ Tomt = 0 | size_tree ( Node (_, f )) = 1 + size_forest f og size_forest Nul = 0 | størrelse_skov ( Ulemper ( t , f' )) = størrelse_træ t + størrelse_skov f'

Et mere detaljeret skemaeksempel , der tæller antallet af blade i et træ [6] :

( definer ( tælleblade træ ) ( hvis ( blade? træ ) 1 ( tælle blade-i-skov ( børnetræ ) ))) ( definer ( tæl-blade-i- skov ) ( hvis ( null? skov ) 0 ( + ( tæl-blade ( bilskov )) ( tæl-blade-i-skov ( cdr skov ) ) ) ))

Disse eksempler reduceres let til en enkelt rekursiv funktion ved at indlejre skovfunktionen i træfunktionen, hvilket ofte gøres i praksis.

Mere avancerede eksempler

Mere komplekse eksempler er eksempler på rekursiv afstamning , som kan implementeres på en naturlig måde ved at give én funktion for hver generativ regel i grammatikken, som så gensidigt rekursivt kalder hinanden. Generelt vil disse være multiple rekursioner, når generering af regler kombinerer flere regler. Dette kan gøres uden gensidig rekursion, ved at have separate funktioner for hver genereringsregel, men ved at kalde én kontrolfunktion, eller ved at behandle hele grammatikken i én funktion.

Gensidig rekursion kan også bruges til at implementere en tilstandsmaskine med én funktion for hver tilstand og en enkelt rekursion pr. tilstandsændring. Dette kræver halerekursionsoptimering, hvis antallet af tilstande er stort eller ubegrænset. Denne tilgang kan bruges som en simpel form for samarbejdende multitasking . En lignende tilgang til multitasking bruger coroutiner , der kalder hinanden, hvor i stedet for at blive afbrudt ved at kalde en anden procedure, kalder en coroutine en anden, men bliver ikke afbrudt, men fortsætter eksekveringen, når den kaldte coroutine vender tilbage. Dette gør det muligt for individuelle koroutiner at gemme tilstand uden at skulle sende parametre eller gemme delte variabler.

Der er også algoritmer, der naturligt har to faser, såsom minimax (min og max), og disse kan implementeres ved at skabe en separat gensidigt rekursiv funktion for hver fase, selvom de også kan kombineres til en enkelt direkte rekursiv funktion.

Matematiske funktioner

I matematik er de mandlige og kvindelige Hofstadter-sekvenser et eksempel på et par sekvenser af heltal, der er gensidigt rekursive.

Fraktaler kan beregnes (til den nødvendige præcision) ved hjælp af rekursive funktioner. Dette kan nogle gange gøres mere elegant med gensidigt rekursive tal. Sierpinski-kurven er et godt eksempel.

Prævalens

Gensidig rekursion er meget brugt i funktionel programmering og bruges ofte i programmer skrevet på Lisp , Scheme , ML og andre lignende sprog . På sprog som Prolog er gensidig rekursion næsten uundgåelig.

Nogle programmeringsstile fraråder gensidig rekursion, idet de argumenterer for, at det er vanskeligt at skelne mellem forhold, der vil returnere et svar fra forhold, der vil få koden til at løkke (køre for evigt uden at returnere et svar). Peter Norvig det udviklingsmønster, der alligevel burde undgås. Han udtaler [7] :

Hvis du har to gensidigt rekursive funktioner, der ændrer et objekts tilstand, så prøv at flytte næsten al funktionaliteten til en af disse funktioner. Ellers er der større sandsynlighed for, at du ender med kodeduplikering.

Terminologi

Gensidig rekursion er også kendt som indirekte rekursion , i modsætning til direkte rekursion , når en funktion kalder sig selv direkte. Dette er blot en vægtforskel, ikke en forskel i tilgang – "indirekte rekursion" understreger brugen af en individuel funktion, mens "gensidig rekursion" understreger brugen af et sæt funktioner frem for en enkelt individuel funktion. For eksempel, hvis f kalder sig selv, er det en direkte rekursion. Hvis f kalder g og derefter g kalder f, som igen kalder g igen, alene set fra fs synspunkt , har f indirekte rekursion. Fra g- funktionens synspunkt har den også indirekte rekursion. Men fra synspunktet af sættet af funktioner f og g har vi gensidig rekursion af hinanden. På samme måde kan et sæt af tre eller flere funktioner kalde hinanden gensidigt.

Reduktion til direkte rekursion

Matematisk er et sæt af gensidigt rekursive funktioner primitivt rekursive , hvilket kan bevises ved hjælp af baglæns rekursion [8] , for hvilken en funktion F er konstrueret , der opregner værdierne af individuelle rekursive funktioner i interleaved rækkefølge: og gensidig rekursion er omskrevet som en primitiv rekursion. $F=f_{1}(0),f_{2}(0),f_{1}(1),f_{2}(1),\dots ,$

Enhver gensidig rekursion mellem to procedurer kan reduceres til direkte rekursion ved at indsætte koden for den ene procedure i den anden. Hvis der kun er et sted, hvor proceduren kalder et andet, kan dette gøres direkte, men hvis der er flere sådanne steder, kan det være nødvendigt at kopiere kode. Med hensyn til stakbrug fylder to gensidigt rekursive procedurer stakken med en sekvens af ABABAB...-kald, og indlejring af procedure B i A resulterer i direkte rekursion (AB)(AB)(AB)...

Alternativt kan et hvilket som helst antal procedurer slås sammen til en enkelt procedure, der tager som argument en mærket union (eller algebraisk datatype ), der gemmer information om den procedure, der kaldes, og dens argumenter. Den samlede procedure vælger en gren baseret på argumenterne og udfører den relevante kode og bruger derefter direkte rekursion til at kalde sig selv med de relevante argumenter. Denne tilgang kan ses som en trunkeret version af udelukkelsen af funktioner [9] . Denne sammenlægning af funktioner kan være nyttig, når nogle funktioner kan kaldes af ekstern kode, således at det ikke er muligt at indlejre en procedure i en anden. En sådan kode skal konverteres, så procedurekald foretages ved at sammenkæde argumenter til en "mærket union" som beskrevet ovenfor. En anden mulighed er at bruge en indpakningsprocedure.

Se også

rekursiv funktion
Cyklisk afhængighed

Noter

↑ Rubio-Sánchez, Urquiza-Fuentes, Pareja-Flores, 2008 , s. 235-239.
↑ Harper, 2005 , " Datotyper ".
↑ Hutton, 2007 , 6.5 Gensidig rekursion, pp. 53-55 .
↑ " Mutual Tail-Recursion Archived 10 April 2016 at the Wayback Machine " og " Tail-Recursive Functions Archived 10 April 2016 at the Wayback Machine ", En vejledning om programmeringsfunktioner i ATS Arkiveret 27. december 2017 på Wayback Machine . Hongwei Xi, 2010
↑ Harper, 2005 , " Datatyper ".
↑ Harvey, Wright, 1999 , V. Abstraktion: 18. Trees: Mutual Recursion, pp. 310-313 .
↑ Løsning af alle Sudoku-puslespil . Hentet 13. januar 2017. Arkiveret fra originalen 15. november 2020. (ubestemt)
↑ " gensidig rekursion Arkiveret 21. juni 2018 på Wayback Machine " PlanetMath
↑ Reynolds, John (august 1972). "Definitionstolke til programmeringssprog af højere orden" (PDF) . Forhandlinger fra ACM's årlige konference . Boston, Massachusetts. pp. 717-740. Arkiveret 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 (Arbejdsudkast af 17. MAJ 2005.). — Carnegie Mellon University, 2005.
Brian Harvey, Matthew Wright. Simply Scheme: Introduktion af datalogi. - MIT Press, 1999. - ISBN 978-0-26208281-5 .
Graham Hutton. Programmering i Haskell. - Cambridge University Press, 2007. - ISBN 978-0-52169269-4 .