18. Rekursion

Die rekursive Struktur der inneren Klasse Node legt nahe, die Methoden equals und copy (alternativ) rekursiv zu implementieren:

def equals(that: ExtQ[E]) =

nodeEquals(this.ältester,

that.asInstanceOf[ExtListQ[E]].ältester)

private def nodeEquals(erster: Option[Node[E]],

zweiter: Option[Node[E]]): Boolean =

erster == None && zweiter == None || // beide Listen zu Ende, oder [1]

erster != None && zweiter != None && // keine der Listen zu Ende, und

erster.get.wert == zweiter.get.wert && // Inhalte gleich, und

nodeEquals(erster.get.verbindung, zweiter.get.verbindung)

def copy(q: ExtQ[E]) = {

val that = q.asInstanceOf[ExtListQ2[E]]

this.ältester = nodeCopy(that.ältester)

this.jüngster =

if (this.ältester == None)

None

else

lastNode(this.ältester) }

private def nodeCopy(quelle: Option[Node[E]]): Option[Node[E]] =

if (quelle == None) // Liste zu Ende

None

else

Some(new Node[E](quelle.get.wert,

nodeCopy(quelle.get.verbindung)))

private def lastNode(node: Option[Node[E]]): Option[Node[E]] =

// require node != None

if (node.get.verbindung == None)

node

else

lastNode(node.get.verbindung);

Dieser Algorithmus ist etwas ineffektiv, weil verkettete die Liste nach ihrer Erzeugung nochmals durchlaufen werden muss, um den jüngsten Knoten (lastNode()) zu finden. In einem weniger eleganten Programm kann dies erspart bleiben:

private var jung: Option[Node[E]] = None

private def nodeCopy(quelle: Option[Node[E]]) =

if (quelle == None)

None

else {

val neu = Some(new Node[E](quelle.get.wert,

nodeCopy(quelle.get.verbindung)))

if (jung == None && neu != None) // jüngster Knoten

jung = neu;

neu }

Jetzt kann in copy der Knoten jüngster ohne Durchlauf ermittelt werden:

this.jüngster = jung;

Mit Hilfe von Objektdiagrammen kann nun der Auf- und Abbau des Stapels im Zuge der rekursiven Aufrufe demonstriert werden.

Auch mit der Reihungstechnik ist es möglich, equals und copy rekursiv zu implementieren. So kann gezeigt werden, dass Rekursion immer eine Alternative zu Wiederholungen (for bzw. while) ist – die Entscheidung ist eine Abwägung zwischen Einfachheit/Verständlichkeit und Effizienz des Algorithmus.

[1] && bindet stärker als ||; ferner berechnet || (bzw. &&) seinen rechten Operanden nicht, wenn der linke true (bzw. false) ergibt

Version: 5. Dezember 2010