Slutlig rekursion

En rekursiv funktion f är svansrekursiv ( engelsk svansrekursiv , inte heller terminalrekursiv , iterativ rekursiv , repetitiv rekursiv ) om den rekursiva funktionsanropet är den sista åtgärden för beräkning av f . Fördelen med denna funktionsdefinition är att inget ytterligare lagringsutrymme krävs för att hantera rekursionen.

Automatisk borttagning av terminalfunktionssamtal

Vid den naiva behandlingen av en rekursiv funktion ökar minnesutrymmesförbrukningen linjärt med rekursionsdjupet, eftersom vid varje funktion anropas minnesutrymme för att registrera den aktuella fortsättningen av programflödet och funktionsparametrarna (t.ex. för att spara returadressen och den aktuella stackramen på samtalsstacken ). Dessutom kan ytterligare lagringsutrymme reserveras för att lagra funktions-lokala variabler medan den anropade funktionen bearbetas. I fallet med ett terminalfunktionssamtal krävs de värden som är lagrade i minnesområdet reserverat för den anropande funktionen endast för parameteröverföring till den terminalt anropade funktionen, så att detta minnesområde kan återanvändas. Detta innebär att slutrekursiva funktioner kan konverteras automatiskt (till exempel som en del av ett optimeringssteg för kompilatorn ) till iterativa funktioner vars minneskonsumtion under bearbetning är oberoende av rekursionsdjupet. Under konverteringen ersätts samtalen till terminalfunktionen med lämpliga hoppinstruktioner ( eliminering av svanssamtal )

Vissa programmeringsspråk som Scheme kräver automatisk omvandling av slutrekursiva funktioner till iterativa funktioner som en del av deras språkdefinition. Andra programmeringsspråk som C , C ++ och C # eller Java kräver inte denna konvertering, men tillåter det som en optimering för respektive språkimplementering. Som en optimering kan denna teknik ofta hittas i kompilatorer för funktionella programmeringsspråk , eftersom den rekursiva / slut-rekursiva formuleringen när man använder en funktionell programmeringsstil är särskilt frekvent för många algoritmer och därför ges sådana formuleringar särskild uppmärksamhet i samband med programmet. optimering vid kompilering av en kompilator.

Det automatiska utbytet av funktionsanrop med hoppinstruktioner med återanvändning av den aktuella stackramen gör det svårt att spåra ett program under felanalys , eftersom samtalsstacken inte helt återspeglar samtalssekvensen för funktionerna när ett pågående program avbryts vid en brytpunkt .

Explicit slutrekursion

Programmeringsspråket Clojure ger ett uttryckligt samtal recurför slutrekursion. Fördelen med detta är att kompilatorn känner igen när samtalet inte görs från slutpositionen och meddelar programmeraren om detta.

Tillämplighet och generalisering

Tillämpningen av tekniken för att ersätta terminalfunktionssamtal med hopp är inte begränsad till terminalrekursiva funktioner. Schemat kräver till exempel exekvering av terminalfunktioner med konstant minnesutrymme ( korrekt svansrekursion ), till exempel för två funktioner som anropar varandra terminalt.

Med övergången till fortsättningspassande stil kan programmen i princip omformas på ett sådant sätt att alla funktionssamtal ersätts av terminalanrop. För att göra detta måste dock alla anropade funktioner omvandlas på ett sådant sätt att de tar en fortsättning som en parameter, som de sedan uttryckligen aktiverar i slutet genom att överföra funktionsresultatet för körning av den ytterligare programkörningen. Vid körning av ett program som har transformerats på detta sätt krävs sedan konstant lagringsutrymme för att lagra aktiveringsposterna (till exempel i samtalsstacken), men det lagringsutrymme som krävs för att lagra fortsättningarna är inte begränsat. Som ett resultat av denna omformning begränsas det möjliga rekursionsdjupet för en rutin av det tillgängliga minnesutrymmet för lagring av fortsättningarna istället för av storleken på samtalsstacken.

Exempel

Den rekursiva funktionssumman ges , som beräknar summan av de första n naturliga siffrorna :

 sum(n)
   if n=0
     return 0
   else
     return n + sum(n-1)

Eftersom det inte är det rekursiva funktionsanropet utan tillägget som utgör den sista åtgärden är det inte en slutlig rekursiv funktion. Beräkningen av sum(3)skulle således innehålla följande steg:

sum(3) = 3 + sum(2)
 sum(2) = 2 + sum(1)
  sum(1) = 1 + sum(0)
   sum(0) = 0
  sum(1) = 1 + 0 = 1
 sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6

I det här fallet kan det dock omvandlas till en slutlig rekursiv representation.

 sum(n)
   return add_sum (0, n)

 add_sum(m, n)
   if n=0
     return m
   else
     return add_sum (m+n, n-1)

Den slutliga rekursiva hjälpfunktionen add_sumfår två parametrar moch nreturnerar summan av moch summan av de första nnaturliga siffrorna som resultatet . Samtalet ger add_sum (0, n)således önskat resultat, summan av de första nnaturliga siffrorna. Medan den slutliga rekursionen pågår samlas add_summellanresultaten i mparametern. I denna slutliga rekursiva formulering skulle beräkningen sum(3)innehålla följande steg:

sum(3) = add_sum(0, 3)
       = add_sum(3, 2)
       = add_sum(5, 1)
       = add_sum(6, 0)
       = 6

Under omvandlingen användes den associerande lagen implicit för att lägga till naturliga tal. Den ursprungliga definitionen av sum(n)beräknad sum(3)som

3 + (2 + (1 + 0))

Den transformerade formuleringen beräknar samma värde som

((0 + 3) + 2) + 1

Liksom alla primitiva rekursiva funktioner kan den slutliga rekursionen representeras av iteration .

 sum(n)
    m := 0

    while (n > 0) do
      m   := m + n
      n   := n - 1
    end-while
    return m

Rekursiva såväl som iterativa lösningar representerar vanligtvis en direkt implementering av ett problem som har analyserats steg för steg. Utrymmesbesparingar och läsbarhet kostar kostnadstiden. Det är därför ofta värt att leta efter mer effektiva algoritmer. Den bästa algoritmen för beräkning av exempelfallet är mest känd från " Gaussisk skolhistoria ":

 sum(n) = (n*(n+1)) / 2

Som ett exempel på slutlig rekursion med flera inblandade funktioner, här är två funktioner evenoch för oddatt avgöra om ett givet naturligt tal är jämnt eller udda.

 even(n)
   if n=0
     return true
   else
     return odd(n-1)

 odd(n)
   if n=0
     return false
   else
     return even(n-1)

De två funktionerna ringer varandra terminalt. Taget individuellt är ingen av de två funktionerna sista rekursiva.

generalisering

I allmänhet är en funktion f slutrekursiv om den kan definieras på följande sätt:

${\ displaystyle f (x) = {\ begin {case} s (x), & {\ mbox {if}} R (x) \\ f (r (x)), & {\ mbox {annars}} \ \\ slut {cases}}}$

Här är r och s alla funktioner som inte definieras med hjälp av f och R är avslutningstillståndet.

Se även

• Rymdkomplexitet

Individuella bevis

1. ↑ Harold Abelson, Gerald Jay Sussman och Julie Sussman: linjär rekursion och Iteration ( Memento av den ursprungliga från September 3, 2006 i Internet Archive ) Info: Den arkiv länk automatiskt in och ännu inte kontrollerats. Kontrollera original- och arkivlänken enligt instruktionerna och ta bort detta meddelande. . I: Struktur och tolkning av datorprogram . Andra upplagan, The MIT Press 1996, ISBN 0-262-51087-1 @ 1@ 2Mall: Webachiv / IABot / mitpress.mit.edu
2. ↑ recur - clojure.core | ClojureDocs - Gemenskapsdriven Clojure-dokumentation och exempel. I: clojuredocs.org. Hämtad 18 januari 2017 . 
3. ^ Richard Kelsey, William Clinger, Jonathan Rees et al.: Revised ⁵ Report on the Algorithmic Language Scheme . I: Högre ordning och symbolisk beräkning . 11, nr 1, augusti 1998, s. 7-105. doi : 10.1023 / A: 1010051815785 .
4. ↑ William Clinger: Korrekt svans rekursion och yteffektivitet ( Memento av den ursprungliga från 30 oktober 2015 i Internet Archive ) Info: Den arkiv länk infördes automatiskt och har ännu inte kontrollerats. Kontrollera original- och arkivlänken enligt instruktionerna och ta bort detta meddelande. (PDF; 240 kB), Proceedings of the 1998 ACM Conference on Programming Language Design and Implementation, juni 1998, s. 174-185 @ 1@ 2Mall: Webachiv / IABot / www.cesura17.net
5. ^ Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes: Essentials of Programming Languages . Andra upplagan, MIT Press 2001, ISBN 0262062178