Rekursion am Beispiel von Listen

[Back]    [Liste]

Die Rekursion von Listen basiert im Wesentlichen auf Funktionen, die in Python als Bibliothek zur Verfügung stehen. Es handelt es sich hier um funktionale Ansätze, die von anderen Sprachen, wie zum Beispiel Haskell oder Miranda uebernommen wurden.

Einfache Rekursionen, wie die Fibonaccifolge

01 def fib (n): 
02 if   n == 0   : return 0
03 elif n == 1   : return 1
04 else          : return (fib (n-1) + fib (n-2))

oder die Ermittlung der Quersumme einer Zahl stellen sich wie folgt dar.

01 def quer (n): 
02 if   n < 10 : return n
03 else        : return ((n % 10) + quer (n / 10))

Um ein komplexes Listemodul, welches Standardfunktionen bereitstellt zu schaffen, ist eine Erweiterung der sogenannten built in Funktionen notwendig. Einen möglichen Aufbau für eine derartige Erweiterung stellt folgende Spezifikation dar.

[Listenmodul ] [Implementierung]

Implementieren Sie die grundlegenden Methoden entsprechend der Spezifikation. Testen Sie diese Methoden. Mit Hilfe von head, tail und cons lässt sich relativ einfach eine komplexe Rekursionsmethode, implementieren. Als Beispiel sei hier das Loeschen eines Elementes aus einer Liste dargestellt. Der rekursive Abstieg erfolgt bis zu der zu loeschenden Stelle. Dort wird der Kopf rekursiv nicht mehr aufgerufen, sondern mit dem Schwanz der Liste der Abstieg weiter ausgeführt. Den Terminationsfall stellt hier die leere Liste dar. Der anschließende rekursive Aufstieg liefert die entsprechend der Spezifikation veränderte Liste.

01 def delete (x, list): 
02 if    list      == [] : return []
03 elif  hd (list) == x  : return delete (x, tl(list))
04 else                  : return cons (hd(list), delete (x, tl(list)))