Kleiner Rekursions-Trick


Das Thema Endrekursion hatte ich schon einmal behandelt. Zur Erinnerung, eine naive Implementierung der Fakultät wie diese hier…

//Variante 1 - nicht endrekursiv
def fac1(n:Int):BigInt =
  if (n <= 1) 1 else fac1(n-1) * n

… ist nicht endrekursiv, da der rekursive Aufruf nicht die letzte Operation der Methode ist, und würde dementsprechend irgendwann zu einem Stackoverflow führen. Eine einfache Lösung besteht darin, einen Akkumulator einzuführen. Der Code sieht dann etwa so aus:

//Variante 2 - endrekursiv
def fac2(n:Int):BigInt = {
  @tailrec def loop(k:Int, acc:BigInt):BigInt =
     if (k <= 1) acc
     else loop(k-1, acc * k)
  loop(n,1)
}

Nun ist das ziemlich langatmig, und ich habe eine bessere Formulierung gefunden:

//Variante 3 - auch endrekursiv
@tailrec def fac3(n:Int, acc:BigInt = 1):BigInt =
   if(n <= 1) acc else fac3(n-1, acc*n)

Besser, nicht wahr? Statt in einer separaten lokalen Methode gibt man den Akkumulator sofort mit. Der Clou ist, dass er als Default-Argument übergeben wird, also bei einem externen Aufruf wie fac3(42) nicht angegeben werden braucht (und auch nicht angegeben werden soll). Natürlich wird damit die Methoden-Signatur etwas verwirrender, und für eine externe API sollte man doch lieber auf Variante 2 zurückgreifen. Für Code, der hinter den Kulissen werkelt, sehe ich das aber nicht so problematisch.

Advertisements

2 Gedanken zu “Kleiner Rekursions-Trick

  1. Ich habe noch nicht gesehen, gelesen oder ausprobiert, was scaladoc mit Defaultargumenten macht, aber würde denken, dass ordentlich dokumentiert die Methode so wie sie ist auch in ein API gehört.

    Methoden, die man für sich so, und den Rest der Welt anders schreibt, erregen meinen Widerwillen. Wenn dieser Stil gut ist, und zum Muster taugt, dann wird man ja ähnliche Methodensignaturen produzieren, und folglich diese auch verstehen.

  2. Wie ich schon geschrieben habe, würde ich das nicht in einer öffentlichen API verwenden, weil es keine Absicherung gegen eine Fehlbenutzung gibt. Aber ich sehe nicht, was in einer lokalen oder privaten Methode gegen diese Technik spricht. Es ist allgemein so, dass im Vergleich zur öffentlichen API manche „versteckte“ Methode komplizierter zu bedienen ist, bestimmmte Annahmen macht u.s.w. Wenn ich z.B. den GGT berechne, sollte die „öffentliche“ Version keine Annahme über Reihenfolge und Vorzeichen der Argumente machen. Benötige ich den GGT nur intern, ist es oft ausreichend, einfach vorauszusetzen, dass das erste Argument größer ist als das zweite, und dass beide positiv sind. Wenn ich später eine „sichere“ Version benötige, kann ich zu deren Implementierung immer noch die „unsichere“ benutzen. Mit dem Rekursions-Trick sehe ich das ähnlich. Ein Default-Argument, dass man nicht überschreiben darf, ist für einen Benutzer gefährlich und verwirrend. Von jemanden, der an den Eingeweiden meiner Klasse herumbasteln will, kann ich dagegen erwarten, dass er mit so etwas rechnet.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s