Als rekursiv wird eine Funktion bezeichnet, die sich selbst aufruft.
Eine rekursive Funktion wird abgekürzt als Rekursion benannt.
Als Scope wird ein virtueller Raum bezeichnet in dem bestimmte Speicherzugriffe gestattet sind.
Wenn eine Variable deklariert wird, können nur Objekte in einem definierten Raum auf diese zugreifen. Deklaration meint dabei, dass sie in die Existenz geholt werden. Die Regeln dazu können von Programmiersprache zur Programmiersprache verschieden sein.
Eine der grundlegenden Prinzipien/Paradigmen ist eigentlich, dass der Zugriff auf eine Variable nur in der Funktion gestattet ist, in der sie deklariert wurde. Dies ist das L, local, von Pythons Scope-Regel-Set LEGB.
a = 1
b = 2
def fun1():
x = a
x += y # Error
def fun2():
y = 2
fun1()
def main():
fun2()
c = a + b
z = x + y # Error
p = m + n # Error
m = 1
n = 2
Der hier aufgeführte Code, soll dies noch einmal beispielhaft darstellen. In der Funktion main() werden c und z deklariert und initialisiert. Zumindest wird es versucht und für c wird es keine Probleme geben, den die Variablen a und b stehen global zur Verfügung, da sie räumlich und zeitlich vor der Referenzierung deklariert wurden. z hingegen wird bei der Initialisierung einen Fehler generieren, da x und y in diesem Raum nicht existieren. Es gibt nichts, worauf sich bezogen werden kann, trotz der zeitlich vorausgegangen Existenz von x und z. Der Raum, in dem sie existierten, war jedoch nicht zugänglich. Bei der Initialisierung von p kommte zu einer Fehlermeldung, da m und n zwar ich richtigen Raum existieren werden, es aber noch nicht tun.
Innerhalb der fun1() gibt es mit der Deklaration und Initialisierung von x kein Problem, aber der Versuch y zu addieren scheitert wieder am Raum, in dem y existiert. Dies ist ausschließlich innerhalb der Funktion fun2() der Fall.
Um in das Problem einzuführen, werden zwei Funktionen gegenübergestellt, die einen fundamentalen Unterschied in der Behandlung von verschiedenen Datentypen in Python darstellen sollen.
def assign_array(as_array):
aa = as_array
print("aa ", aa)
print("as_array", as_array)
aa.append(len(as_array))
print("aa ", aa)
print("as_array", as_array)
return
def assign_int(as_int):
ai = as_int
print("ai ", ai)
print("as_int", as_int)
ai += as_int
print("ai ", ai)
print("as_int", as_int)
return
print("assign_array")
assign_array([0])
print()
print("assign_int")
assign_int(1)
Die Ausgabe dieser Funktionen zeigt die Ungleichbehandlung deutlich auf.
assign_array
aa [0]
as_array [0]
aa [0, 1]
as_array [0, 1]
assign_int
ai 1
as_int 1
ai 2
as_int 1
Im Fall von aa und as_array wird lediglich die Referenz auf eine Speicheradresse übergeben, wohingegen ai, aus der Vergleichsfunktion, bei der Deklaration einen eigenen Speicherplatz bekommt.
Dies findet in einem Scope statt, sodass die Frage aufgeworfen wird, wie sich dies auf Rekursionen auswirkt.
def recursion_basic_append_separate(level, rec_array):
if len(rec_array) > 4:
print("peak", level, rec_array)
return
else:
print(" ", level, rec_array)
rec_array.append(len(rec_array))
recursion_basic_append_separate(level + 1, rec_array)
print("back", level, rec_array)
return
def recursion_basic_append_in_call(level, rec_array):
if len(rec_array) > 4:
print("peak", level, rec_array)
return
else:
print(" ", level, rec_array)
recursion_basic_append_in_call(level + 1, rec_array + [len(rec_array)])
print("back", level, rec_array)
return
print("recursion_basic_append_separate()")
recursion_basic_append_separate(0, [0])
print()
print("recursion_basic_append_in_call()")
recursion_basic_append_in_call(0, [0])
Die Ausgabe dieser Funktionen zeigt ein interessantes Phänomen.
recursion_basic_append_separate()
0 [0]
1 [0, 1]
2 [0, 1, 2]
3 [0, 1, 2, 3]
peak 4 [0, 1, 2, 3, 4]
back 3 [0, 1, 2, 3, 4]
back 2 [0, 1, 2, 3, 4]
back 1 [0, 1, 2, 3, 4]
back 0 [0, 1, 2, 3, 4]
recursion_basic_append_in_call()
0 [0]
1 [0, 1]
2 [0, 1, 2]
3 [0, 1, 2, 3]
peak 4 [0, 1, 2, 3, 4]
back 3 [0, 1, 2, 3]
back 2 [0, 1, 2]
back 1 [0, 1]
back 0 [0]
Da es in Phyton keine Pointer, Speicheradressenverweise, gibt, sondern Referenzen auf Objekte im Speicher, passieren hier seltsames.
Der gleiche Aufbau, mit der Funktion id().
def recursion_basic_append_separate(level, rec_array):
if len(rec_array) > 4:
print("peak", level, rec_array, id(rec_array))
return
else:
print(" ", level, rec_array, id(rec_array))
rec_array.append(len(rec_array))
recursion_basic_append_separate(level + 1, rec_array)
print("back", level, rec_array, id(rec_array))
return
def recursion_basic_append_in_call(level, rec_array):
if len(rec_array) > 4:
print("peak", level, rec_array, id(rec_array))
return
else:
print(" ", level, rec_array, id(rec_array))
recursion_basic_append_in_call(level + 1, rec_array + [len(rec_array)])
print("back", level, rec_array, id(rec_array))
return
print("recursion_basic_append_separate()")
recursion_basic_append_separate(0, [0])
print()
print("recursion_basic_append_in_call()")
recursion_basic_append_in_call(0, [0])
Die dazugehörige Ausgabe:
recursion_basic_append_separate()
0 [0] 2085266528512
1 [0, 1] 2085266528512
2 [0, 1, 2] 2085266528512
3 [0, 1, 2, 3] 2085266528512
peak 4 [0, 1, 2, 3, 4] 2085266528512
back 3 [0, 1, 2, 3, 4] 2085266528512
back 2 [0, 1, 2, 3, 4] 2085266528512
back 1 [0, 1, 2, 3, 4] 2085266528512
back 0 [0, 1, 2, 3, 4] 2085266528512
recursion_basic_append_in_call()
0 [0] 2085266528512
1 [0, 1] 2085270223040
2 [0, 1, 2] 2085270223168
3 [0, 1, 2, 3] 2085270223232
peak 4 [0, 1, 2, 3, 4] 2085270223360
back 3 [0, 1, 2, 3] 2085270223232
back 2 [0, 1, 2] 2085270223168
back 1 [0, 1] 2085270223040
back 0 [0] 2085266528512
Die Ausgabe wurde um die Ausgabe der Referenz-ID erweitert. Zu erkennen ist, dass diese sich in recursion_basic_append_separate() nicht ändert und in recursion_basic_append_in_call() ebenenweise schon.
Dies deutet darauf hin, dass die Veränderung des Arrays während des Funktionsaufrufs ein neues Objekt generiert.
Ob die Erweiterung des Arrays mit rec_array.append(len(rec_array)) oder rec_array += [len(rec_array)] in der Funktion recursion_basic_append_separate() realisiert wird, ändert an den Ausgaben nichts.
Durch das Auslagern der Array-Erweiterung in eine andere Funktion lässt sich ebenfalls ein jedes mal ein neues Objekt generieren.
def extra_function(ef_rec_array):
return ef_rec_array + [len(ef_rec_array)]
def recursion_basic_append_separate_extra_function(level, rec_array):
if len(rec_array) > 4:
print("peak", level, rec_array, id(rec_array))
return
else:
print(" ", level, rec_array, id(rec_array))
rec_array = extra_function(rec_array)
recursion_basic_append_separate_extra_function(level + 1, rec_array)
print("back", level, rec_array, id(rec_array))
return
print("recursion_basic_append_separate_extra_function()")
recursion_basic_append_separate_extra_function(0, [0])
Die Ausgabe ist:
recursion_basic_append_separate_extra_function()
0 [0] 2442783520576
1 [0, 1] 2442783520768
2 [0, 1, 2] 2442783520704
3 [0, 1, 2, 3] 2442783520896
peak 4 [0, 1, 2, 3, 4] 2442780217728
back 3 [0, 1, 2, 3, 4] 2442780217728
back 2 [0, 1, 2, 3] 2442783520896
back 1 [0, 1, 2] 2442783520704
back 0 [0, 1] 2442783520768
Es fällt bei den als back markierten IDs auf, dass diese nicht auf den Ebenen übereinstimmen, was zu erwarten ist, da die Erweiterung des Arrays vor dem Aufruf der Rekursion und zwischen den beiden print()s liegt.
Wird extra_function() in
def extra_function(ef_rec_array):
ef_rec_array.append(len(ef_rec_array))
return ef_rec_array
geändert, ist das Ergebnis wieder:
recursion_basic_append_separate_extra_function()
0 [0] 2808000706368
1 [0, 1] 2808000706368
2 [0, 1, 2] 2808000706368
3 [0, 1, 2, 3] 2808000706368
peak 4 [0, 1, 2, 3, 4] 2808000706368
back 3 [0, 1, 2, 3, 4] 2808000706368
back 2 [0, 1, 2, 3, 4] 2808000706368
back 1 [0, 1, 2, 3, 4] 2808000706368
back 0 [0, 1, 2, 3, 4] 2808000706368
Das Auslagern in andere Funktionen ändert, erwartungsgemäß, nichts.
Wie verhält sich dies verhält, wenn ein Array Eintrag für Eintrag übertragen wird, wird im folgenden Beispiel betrachtet.
def recursion_copy_by_element_append_separate(level, rec_array):
ra = []
for r in rec_array:
ra.append(r)
ra = rec_array
if len(ra) > 4:
print("peak", level, ra, id(ra))
return
else:
print(" ", level, ra, id(ra))
ra.append(len(ra))
recursion_copy_by_element_append_separate(level + 1, ra)
print("back", level, ra, id(rec_array))
return
def recursion_copy_by_element_append_in_call(level, rec_array):
ra = []
for r in rec_array:
ra.append(r)
if len(ra) > 4:
print("peak", level, ra, id(ra))
return
else:
print(" ", level, ra, id(ra))
recursion_copy_by_element_append_in_call(level + 1, ra + [len(ra)])
print("back", level, ra, id(ra))
return
print("recursion_copy_by_element_append_separate()")
recursion_copy_by_element_append_separate(0, [0])
print()
print("recursion_copy_by_element_append_in_call()")
recursion_copy_by_element_append_in_call(0, [0])
Das Resultat.
recursion_copy_by_element_append_separate()
0 [0] 1821868366080
1 [0, 1] 1821868366080
2 [0, 1, 2] 1821868366080
3 [0, 1, 2, 3] 1821868366080
peak 4 [0, 1, 2, 3, 4] 1821868366080
back 3 [0, 1, 2, 3, 4] 1821868366080
back 2 [0, 1, 2, 3, 4] 1821868366080
back 1 [0, 1, 2, 3, 4] 1821868366080
back 0 [0, 1, 2, 3, 4] 1821868366080
recursion_copy_by_element_append_in_call()
0 [0] 1821871601280
1 [0, 1] 1821871601408
2 [0, 1, 2] 1821871601600
3 [0, 1, 2, 3] 1821871601664
peak 4 [0, 1, 2, 3, 4] 1821871601856
back 3 [0, 1, 2, 3] 1821871601664
back 2 [0, 1, 2] 1821871601600
back 1 [0, 1] 1821871601408
back 0 [0] 1821871601280
Diese Situation ist überraschend, da ein neues Array deklariert wird und Integer für Integer angefügt werden.
Sind in Python Strings Char-Arrays? Was eine seltsame Frage ist, da in Python kein Char existiert, sondern lediglich ein String mit einer Länge von 1 ist.
Die richtige Frage ist: verhalten sich containerisierte/sequenzielle Datentypen unterschiedlich, je nach Subtyp?
def recursion_chars_append_separate(level, chars):
if len(chars) > 4:
print("peak", level, chars)
return
else:
print(" ", level, chars)
chars.append('*')
recursion_chars_append_separate(level + 1, chars)
print("back", level, chars)
return
def recursion_chars_append_in_call(level, chars):
if len(chars) > 4:
print("peak", level, chars)
return
else:
print(" ", level, chars)
recursion_chars_append_in_call(level + 1, chars + ['*'])
print("back", level, chars)
return
def recursion_strings_append_separate(level, strings):
if len(strings) > 4:
print("peak", level, strings)
return
else:
print(" ", level, strings)
strings += '*'
recursion_strings_append_separate(level + 1, strings)
print("back", level, strings)
return
def recursion_strings_append_in_call(level, strings):
if len(strings) > 4:
print("peak", level, strings)
return
else:
print(" ", level, strings)
recursion_strings_append_in_call(level + 1, strings + '*')
print("back", level, strings)
return
print("recursion_chars_append_separate()")
recursion_chars_append_separate(0, ['-'])
print()
print("recursion_chars_append_in_call()")
recursion_chars_append_in_call(0, ['-'])
print()
print("recursion_strings_append_separate()")
recursion_strings_append_separate(0, "-")
print()
print("recursion_strings_append_in_call()")
recursion_strings_append_in_call(0, "-")
Das Resultat.
recursion_chars_append_separate()
0 ['-']
1 ['-', '*']
2 ['-', '*', '*']
3 ['-', '*', '*', '*']
peak 4 ['-', '*', '*', '*', '*']
back 3 ['-', '*', '*', '*', '*']
back 2 ['-', '*', '*', '*', '*']
back 1 ['-', '*', '*', '*', '*']
back 0 ['-', '*', '*', '*', '*']
recursion_chars_append_in_call()
0 ['-']
1 ['-', '*']
2 ['-', '*', '*']
3 ['-', '*', '*', '*']
peak 4 ['-', '*', '*', '*', '*']
back 3 ['-', '*', '*', '*']
back 2 ['-', '*', '*']
back 1 ['-', '*']
back 0 ['-']
recursion_strings_append_separate()
0 -
1 -*
2 -**
3 -***
peak 4 -****
back 3 -****
back 2 -***
back 1 -**
back 0 -*
recursion_strings_append_in_call()
0 -
1 -*
2 -**
3 -***
peak 4 -****
back 3 -***
back 2 -**
back 1 -*
back 0 -
Ja. Ein String verhält sich wie ein Integer-Objekt. Ein "Char-Array", wie die getesteten Integer-Array-Objekte. Es ist somit nicht möglich eine Unterscheidung zwischen elementaren und sequenziellen/zusammengesetzten Datentypen in diesem Kontext zu finden.
Wie ändert sich die Referenz-ID, wenn der Datentyp sich ändert?
def type_changes():
x = 1
print(id(x))
x = "string"
print(id(x))
x = False
print(id(x))
x = [3.4, 5.6]
print(id(x))
return
print("type_changes()")
type_changes()
Das Resultat.
type_changes()
140708461676984
140708461732712
140708460876400
2315544589952
Welcher Weg, das Array im localen Scope zu halten funktioniert, zeigt folgender Code.
def recursion_copy_function_append_separate(level, rec_array):
ra = rec_array.copy()
if len(ra) > 4:
print("peak", level, ra, id(ra))
return
else:
print(" ", level, ra, id(ra))
ra.append(len(ra))
recursion_copy_function_append_separate(level + 1, ra)
print("back", level, ra, id(ra))
return
def recursion_copy_function_append_in_call(level, rec_array):
ra = rec_array.copy()
if len(ra) > 4:
print("peak", level, ra, id(ra))
return
else:
print(" ", level, ra, id(ra))
recursion_copy_function_append_in_call(level + 1, ra + [len(ra)])
print("back", level, ra, id(ra))
return
print("recursion_copy_function_append_separate()")
recursion_copy_function_append_separate(0, [0])
print()
print("recursion_copy_function_append_in_call()")
recursion_copy_function_append_in_call(0, [0])
Die Ausgabe:
recursion_copy_function_append_separate()
0 [0] 1821868366080
1 [0, 1] 1821871601408
2 [0, 1, 2] 1821871601472
3 [0, 1, 2, 3] 1821871601600
peak 4 [0, 1, 2, 3, 4] 1821868364160
back 3 [0, 1, 2, 3, 4] 1821871601600
back 2 [0, 1, 2, 3] 1821871601472
back 1 [0, 1, 2] 1821871601408
back 0 [0, 1] 1821868366080
recursion_copy_function_append_in_call()
0 [0] 1821871601280
1 [0, 1] 1821871601408
2 [0, 1, 2] 1821871601600
3 [0, 1, 2, 3] 1821871601664
peak 4 [0, 1, 2, 3, 4] 1821871601856
back 3 [0, 1, 2, 3] 1821871601664
back 2 [0, 1, 2] 1821871601600
back 1 [0, 1] 1821871601408
back 0 [0] 1821871601280
Der sicherste Weg, ein Array in einer Rekursion zu verwalten, scheint durch eine copy()-, besser eine deepcopy()-Funktion gewährleistet zu werden.
Abweichungen davon müssen im Vorfeld genau analysiert werden, um keiner Objekt-Verwirrung zu erliegen.