Python 3 - Lernen und professionell anwenden

201

7.2

Vertiefung: Rekursive Funktionen für Sequenzen

7.2 Vertiefung: Rekursive Funktionen für Sequenzen

Slicing ist für die Verarbeitung von Sequenzen sehr wichtig. Insbesondere gibt es viele ele-

gante und kurze rekursive Algorithmen, die Slicing verwenden.

7.2.1 Rekursives Summieren

Das erste Beispiel ist eine rekursive Funktion, die die Summe der Elemente einer Liste von

Zahlen berechnet:

Die Lösungsidee ist folgende Überlegung.

쐽 Eine leere Zahlenliste hat die Summe null.

쐽 Ansonsten ist die Summe gleich der ersten Zahl plus der Summe der restlichen Zahlen

der Liste. Beispiel:

summe ([1, 2, 3]) = 1 + summe([2, 3])

In Zeile #1 befindet sich ein rekursiver Aufruf der Funktion summe(). Als Parameter wird

der Rest der Liste ohne das erste Element übergeben.

7.2.2 Rekursive Suche

Ein in der Praxis häufig auftretendes Problem ist die Suche nach einem bestimmten Ele-

ment in einer Sequenz. Für einfache Suchaufgaben kann natürlich der

in-Operator verwen-

det werden. Wenn

s eine Sequenz ist, liefert der Ausdruck a in s genau dann den Wert

True (WAHR), wenn a ein Element von s ist, und False sonst. Beispiel:

>>> b

4

>>> def summe(liste):

if len(liste) == 0:

r e tur n 0

else:

return liste[0] + summe(liste[1:]) #1

>>> summe([2, 4, 6, 8, 10])

30

>>> summe([])

0

>>> 2 in (3, 34, 5)

False

>>> 5 in (3, 34, 5)

True

Kapitel 7

Sequenzen, Mengen und Generatoren

202

Es gibt aber auch komplexere Suchaufgaben, die nicht mit dem in-Operator oder anderen

vorgegebenen Funktionen gelöst werden können. Sie haben folgende allgemeine Form:

»Suche in einer Sequenz

s alle Elemente, die eine bestimmte Eigenschaft haben.«

Die Grundidee eines rekursiven Suchalgorithmus lautet folgendermaßen:

쐽 Wenn die Sequenz s nur aus einem Element a besteht, prüfe, ob a die geforderte Eigen-

schaft besitzt. Falls ja, gib die Liste

[a] zurück, sonst gib eine leere Liste [] zurück.

쐽 Wenn die Sequenz s aus mehreren Elementen besteht, zerteile s in zwei etwa gleich große

Teile

s1 und s2 und wende den Suchalgorithmus auf beide Teile an. Das Suchergebnis für

s ist die Konkatenation (Aneinanderhängung) der Suchergebnisse für s1 und s2.

In der Informatik nennt man diese algorithmische Idee auch »teile und herrsche« (divide

and conquer), nach dem berühmten Ausspruch des römischen Feldherrn Julius Caesar.

Als Programmbeispiel diene die folgende Funktion, die aus einer Liste von Telefonnum-

mern alle Telefonnummern mit einer bestimmten Vorwahl heraussucht.

Erläuterung:

#1: Elementarer Fall: Die Liste num besteht nur aus einem einzigen Element num[0]. Dieses

enthält eine Telefonnummer in Form eines Strings. Es wird geprüft, ob der Slice

num[0]

[:len(vorwahl)]

– also der vordere Teilstring, der in der Länge der vorgegebenen Vorwahl

entspricht – gleich der Vorwahl ist.

#2: Im Fall, dass die Nummernliste num mehr als ein Element enthält, wird die Liste in der

Mitte aufgeteilt. Das heißt, es werden zwei Slices gebildet. Die Grenze ist der Index

len(num)/2. Die Funktion suche() wird rekursiv auf beide Teile angewendet.

Beispielaufruf:

>>> def suche(num, vorwahl):

if len(num) == 1:

if num[0][:len(vorwahl)]== vorwahl: #1

r etu r n nu m

e l se:

r etu r n []

e l s e :

return suche(num[:len(num)/2], vorwahl)+\

suche(num[len(num)/2:], vorwahl) #2

>>> nummernliste=['0223 788834',

'0201 566722',

'0224 66898',

'0201 899933',

'0208 33987']

>>> print(suche(nummernliste, '0201'))

['0201 566722', '0201 899933']