Tail Recursion

Mein erster Eintrag in diesem Blog soll sich mit dem Thema Tail Recursion beschäftigen, da ich in letzter Zeit häufig bemerke, dass es ein Thema ist, mit dem viele Programmierer noch nicht wirklich vertraut sind.

Was ist Tail Recursion eigentlich?

Tail Recursion ist eine Form der Rekursion, in der kein Stack aufgebaut werden muss. In diesem Artikel möchte ich darauf eingehen, warum Tail Recursion benutzt werden sollte und wie man Iterationen und normale Rekursionen in Tail Recursion umgebaut werden können.


Warum ist Tail Recursion besser als eine Iteration?

In den meisten Fällen lassen sich Rekursionen einfacher lesen und schreiben als Iterationen. Einige Sprachen verzichten auch vollkommen auf Schleifen, z.B. rein funktionale Sprachen, in denen es keine mutable States gibt, sich somit also auch keine Abbruchkriterien sinnvoll nutzen lassen.

Wie funktioniert Tail Recursion?

Wie bereits erwähnt wird bei einer Tail Recursion kein Stack aufgebaut, was daran liegt, dass der letzte Ausdruck der Funktion nur der Rekursionsaufruf ist. Weitere Aufrufe müssen vor dem Rekursionsauruf ausgeführt werden. Ein kleines Beispiel in Scala sollte das verdeutlichen:

Die erste Funktion ist nicht Tail Recursive, da der letzte Aufruf die Addition von i und dem Rekursionsaufruf ist.

def rec(i: Int): Int = if(i <= 0) 0 else rec(i-1) + i;

Die Funktion lässt sich einfach in eine Tail Recursive Variante abändern, in dem man das Ergebnis einfach als Parameter mitschleift und zum Schluss zurückgibt. Um eine Manipulation dieses Parameters zu verhindern schreiben wir uns einfach einen Helper, der von außen nicht sichtbar ist.

def tailrec(i: Int) = {
  def helper(i: Int,j: Int): Int = if(i<=0) j else helper(i-1, j+i)
  helper(i,0)
}

Noch deutlicher wird es, wenn man die erste Funktion in Clojure schreibt, da man hier sehr schön sieht, dass der letzte Aufruf die Addition ist:

(defn rec
  ([i]
    (if (<= i 0) 
      0 
      (+ i (rek (- i 1)))
    )))

Der Vollständigkeit halber auch noch einml die Tail Recursion in Clojure:

(defn tailrec
  ([i]
    (defn helper
      ([i j]
        (if (<= i 0)
          j
          (recur (- i 1) (+ j i)))))
    (helper i 0)))

Und wie sieht das im Programm aus?

Statt die Funktion noch einmal aufzurufen werden bei einer Tail Recursion nur die Parameter geändert und dann zum Anfang der Funktion gesprungen, was auch der Grund dafür ist, dass kein Stack aufgebaut wird.



Ich hoffe meine Ausführung ist einigermaßen verständlich. Für Kritik und Lob bin ich immer gerne zu haben ;-)