Fachkonzept - Liste als rekursive Datenstruktur

Liste als rekursive Datenstruktur

Eine Liste ist entweder eine leere Liste, oder besteht aus einem ersten Element und einer (Rest-)Liste.

Die Struktur von Listen kann somit rekursiv beschrieben werden.

Diese rekursive Struktur ist die Grundlage vieler rekursiver Algorithmen zur Verarbeitung von Listen.

Entwicklung rekursiver Algorithmen zur Verarbeitung von Listen

Die Entwicklung rekursiver Algorithmen zur Verarbeitung von Listen soll anhand eines Beispiels verdeutlicht werden.

Beispiel: Es soll gezählt werden, wie oft ein Element in einer Liste vorkommt.

Wir betrachten zunächst konkrete Fälle und entwickeln für diese Fälle (rekursive) Problemreduktionsschritte:

anzahl('b', []) -> 
    0

anzahl('b', ['b', 'b', 'd', 'a', 'c', 'b']) ->
    1 + anzahl('b', ['b', 'd', 'a', 'c', 'b'])

anzahl('b', ['a', 'b', 'b', 'd', 'a', 'c', 'b']) ->
    anzahl('b', ['b', 'b', 'd', 'a', 'c', 'b'])

Der erste Problemreduktionsschritt betrifft den Rekursionsanfang. Hier kann man direkt die Lösung angeben. Die beiden anderen Problemreduktionsschritte sind rekursiv. Hier wird das Problem auf ein strukturgleiches, aber verkleinertes Problem reduziert. Die Verkleinerung des Problems erfolgt dadurch, dass die zu verarbeitende Liste kürzer wird. Mit Hilfe solcher Problemreduktionsschritte lässt sich die gesuchte Anzahl bestimmen, wie die folgende Reduktionskette zeigt.

anzahl('b', ['a', 'b', 'd', 'a', 'b']) -> 
anzahl('b', ['b', 'd', 'a', 'b']) ->
1 + anzahl('b', ['d', 'a', 'b']) ->
1 + anzahl('b', ['a', 'b']) ->
1 + anzahl('b', ['b']) ->
1 + (1 + anzahl('b', [])) ->
1 + (1 + 0) ->
2 

Folgende Problemreduktionsstrategie liegt der gezeigten rekursiven Problemlösung zu Grunde:

Betrachte zunächst den Fall einer leeren Liste und gib die Lösung für diesen Fall direkt an.

Betrachte dann den Fall einer nicht-leeren Liste. Zerlege eine solche Liste in ein erstes Element und eine Restliste. Bearbeite die Restliste analog zur Ausgangsliste.

Die konkreten Problemreduktionsschritte werden jetzt zu einem Algorithmus / Programm verallgemeinert.

def anzahl(element, liste):
    if len(liste) == 0:
        return 0
    else:
        if liste[0] == element:
            return (1 + anzahl(element, liste[1:]))
        else:
            return anzahl(element, liste[1:])

Ein Test bestätigt das oben bereits per Reduktionskette ermittelte Ergebnis.

>>> anzahl('b', ['a', 'b', 'd', 'a', 'b'])
2