Tiefe Verschachtelung? Rekursive Funktion!#
Übergang in Runde 2: Wir gehen durch eine tief verschachtelte Liste durch. Wir machen das Schritt für Schritt. Ohne es zu merken, versteht man (hoffentlich) die Idee der Rekursion.
Didaktische Überlegungen ausführlicher siehe Didaktik zum Notebook Rekursion.
Die Spielsituation#
Der Wert eines Objekts sei so gegeben:
Der Wert einer Zahl ist die Zahl selbst.
Der Wert eines Strings ist die Länge des Strings.
Der Wert einer Liste ist die Summe der Werte der einzelnen Listenelemente.
Beispiele:
Zahl = 3.1415
Wert_Zahl = Zahl
Wert_Zahl
3.1415
String = "Hallo"
Wert_String = len(String)
Wert_String
5
Liste = [1, 2, 3]
Listensumme = 0
for x in Liste:
Listensumme += x
Wert_Liste = Listensumme
Wert_Liste
6
Typ des Listenelements automatisch erkennen#
Wie berechnen wir den Wert einer Liste, wenn die Listenelemente keine Zahlen sind?
Liste = [3, 2, 1, "los!"]
Listensumme = 0
for x in Liste:
if isinstance(x, (int, float)):
Listensumme += x
elif isinstance(x, str):
Listensumme += len(x)
Wert_Liste = Listensumme
Wert_Liste
10
Und was tun wir, wenn das Listenelement selbst eine Liste ist?
Liste = [ 1, [2, 3, 4] ]
Listensumme = 0
# durch die Liste mit x durchgehen
for x in Liste:
if isinstance(x, (int, float)):
Listensumme += x
elif isinstance(x, str):
Listensumme += len(x)
elif isinstance(x, list):
# durch die Liste x mit x2 durchgehen
for x2 in x:
if isinstance(x2, (int, float)):
Listensumme += x2
elif isinstance(x2, str):
Listensumme += len(x2)
Wert_Liste = Listensumme
Wert_Liste
10
Verschachtelung: oh je!#
Was tun wir, wenn das Listenelement selbst eine Liste ist … das eine Liste enthält?
Liste = [ 1, [2, [ 3, 4 ] ] ]
Listensumme = 0
# durch die Liste mit x durchgehen
for x in Liste:
if isinstance(x, (int, float)):
Listensumme += x
elif isinstance(x, str):
Listensumme += len(x)
elif isinstance(x, list):
# durch die Liste x mit x2 durchgehen
for x2 in x:
if isinstance(x2, (int, float)):
Listensumme += x2
elif isinstance(x2, str):
Listensumme += len(x2)
elif isinstance(x2, list):
# durch die Liste x2 mit x3 durchgehen
for x3 in x2:
if isinstance(x3, (int, float)):
Listensumme += x3
elif isinstance(x3, str):
Listensumme += len(x3)
elif isinstance(x3, list):
# durch die Liste x3 mit x4 durchgehen
for x4 in x3:
if isinstance(x4, (int, float)):
Listensumme += x4
elif isinstance(x4, str):
Listensumme += len(x4)
# u.s.w.
Wert_Liste = Listensumme
Wert_Liste
10
Wir sehen schon: So geht das nicht weiter. Denn wir wissen nicht, wie tief eine Liste verschachtelt ist. So ist z.B. der Wert der Liste [[[[[[ 42 ]]]]]] auch nur 42. Wie gehen wir da vor?
Funktionalität in einer Funktion kapseln!#
Immer dann, wenn Code kopiert wird, überlegt man sich, ob das nicht besser auch mit einer Funktion geht?
Wir definieren eine Funktion Wert():
def Wert(x):
"""Gibt den "Wert" eines Objektes zurück:
* Der Wert einer Zahl ist die Zahl selbst.
* Der Wert eines Strings ist die Länge des Strings.
* Der Wert einer Liste ist die Summe der Werte der einzelnen Listenelemente."""
print( f"außen: {x=}")
if isinstance(x, (int, float) ):
return x
# ist x ein String? Wir geben die Länge zurück.
elif isinstance(x, str):
return len(x)
# ist x eine Liste? Wir gehen durch die Liste durch und addieren die Werte der Listenelemente
elif isinstance(x, list):
# Listensumme erst mal 0
Listensumme = 0
for x2 in x:
print(f" innen: {x2=}")
try:
Listensumme += x2 # BESSSER MACHEN: funktioniert so bisher nur mit Zahlen
except:
Listensumme = [ "EXCEPTION" ]
return Listensumme
# ist nl etwas anderes, das wir nicht erkennen?
else:
# fehlertolerant, aber ggf. auch gefährlich:
# Wir fangen das mit einem harmlosen Default-Wert ab, und schreiben ggf. eine Warnung.
print(f"WARNUNG: Weiß nicht, was ich damit anfangen soll:\n {x}\n (type(): {type(x)}).\nGebe 0 zurück." )
return 0
# sicherer und penibel: Wir geben None zurück.
# Dann erfährt die aufrufende Instanz wenigstens, dass etwas nicht stimmt,
# und kann ggf. einen Fehler abfangen.
# return None
# oder wir werfen selbst einen Fehler:
# raise TypeError
Wir probieren es aus:
Wert( 1 )
außen: x=1
1
Wert( [1, 2, 3] )
außen: x=[1, 2, 3]
innen: x2=1
innen: x2=2
innen: x2=3
6
Wert( {1,2,3} ) # ein Set
außen: x={1, 2, 3}
WARNUNG: Weiß nicht, was ich damit anfangen soll:
{1, 2, 3}
(type(): <class 'set'>).
Gebe 0 zurück.
0
Und auch die folgende Zeile geht bisher noch nicht, wirft bei BESSER MACHEN einen Fehler:
Wert( [1, "[2, 3]" ] )
außen: x=[1, '[2, 3]']
innen: x2=1
innen: x2='[2, 3]'
['EXCEPTION']
Aber die Lösung ist einfach, und wir kennen sie schon: Wir müssen in der Zeile BESSSER MACHEN einfach den Wert() des Listenelementes berechnen, den wir zur Listensumme addieren ;-)
def Wert(x, verbose = 0):
if verbose >= 2:
print( f"{x=}")
if isinstance(x, (int, float) ):
return x
elif isinstance(x, str):
return len(x)
elif isinstance(x, list):
Listensumme = 0
for x2 in x:
# Die folgende Zeile funktioniert mit allen Typen von x2, die wir schon kennen:
Listensumme += Wert(x2, verbose = verbose ) # BESSSER MACHEN? Nein, so ist es gut!
return Listensumme
# alles andere kennen wir nicht, wir geben den Wert 0 zurück
else:
return 0
Wir probieren es aus:
Wert( [1, [2, 3] ] )
6
Wert( [ ["Hallo", "Welt"], ["Grüß", "Gott"] ] )
17
Wert( [[[ [[[[[[[[42]]]]]]]] ]]], verbose = 2 )
x=[[[[[[[[[[[42]]]]]]]]]]]
x=[[[[[[[[[[42]]]]]]]]]]
x=[[[[[[[[[42]]]]]]]]]
x=[[[[[[[[42]]]]]]]]
x=[[[[[[[42]]]]]]]
x=[[[[[[42]]]]]]
x=[[[[[42]]]]]
x=[[[[42]]]]
x=[[[42]]]
x=[[42]]
x=[42]
x=42
42
Was passiert hier?
Der Algorithmus, der den Rückgabewert unserer Funktion Wert() berechnet, ruft unsere Funktion Wert() mit einem vereinfachten Teil der ursprünglichen Problemstellung neu auf. Der Hinweis, wie das geht, war schon ganz oben in der Spezifikation von Wert enthalten, wir zitieren:
„Der Wert einer Liste ist die Summe der Werte der einzelnen Listenelemente.“
Bei der Codierung machen wir das so:
Wir definieren eine Funktion
Wert()und verwenden in der Definition der Funktion dabei diese Funktion schon so, als ob sie schon definiert wäre.
In unserer Lösung erlauben ein beliebiges Objekt beim Aufruf von Wert(), und fragen dann seinen Typ ab. Insbesondere dürfen wir statt einer Zahl auch einen String oder eine Liste (oder allgemeiner: irgend etwas, aus dem wir einen Zahlenwert erzeugen können) übergeben.
Beißt sich hier nicht die Katze in den Schwanz? Ja, das tut sie. Aber der Schwanz wird kürzer, und so löst sich das Problem von selbst: Das ist Rekursion!
Spontan 2023-11-03: Die Urform aller Rekursionen#
3! … 3 * 2! … 3 * 2 * 1!
def fakultaet(x):
print( f"Ich bin hier: {x=}")
if x <= 1:
return 1
else:
return x * fakultaet( x-1 )
fakultaet(3)
Ich bin hier: x=3
Ich bin hier: x=2
Ich bin hier: x=1
6
Aufgabe#
Erweiterung: Was machen wir, wenn wir auf ein Dict stoßen? Dann interessieren uns nicht die Keys, sondern nur die Values.
Bitte obige Funktion entsprechend erweitern!
Begruessungen_dict = {
"EN": ["Hello"],
"BY": [ "Servus"],
"RU": "Привет",
"Nerd": ["Hallo", "Welt"] }
Begruessungen_list = list(Begruessungen_dict.values())
Begruessungen_list
[['Hello'], ['Servus'], 'Привет', ['Hallo', 'Welt']]
Wert( Begruessungen_list )
26
Wert( Begruessungen_dict )
0