Python-Rekursion

[Jr M. (maxie21)]

Untersuchen Sie zunächst den Code:

# Below is a recursive function that inserts an element
# at the bottom of a stack.
def insertAtBottom(stack, item):
    if isEmpty(stack):
        push(stack, item)
    else:
        temp = pop(stack)
        insertAtBottom(stack, item)
        push(stack, temp)
# Below is the function that reverses the given stack
# using insertAtBottom()

def reverse(stack):
    if not isEmpty(stack):
        temp = pop(stack)
        reverse(stack)
        insertAtBottom(stack, temp)

Da die aufgerufene Funktion keinen neuen Wert an die aufrufende Funktion 
zurückgibt, scheint es, dass die Funktion reverse Stack als globale 
Variable verwendet. Ist das nicht eine schlechte Methode, um Rekursion 
zu implementieren? Ist es nicht besser, die Verwendung globaler 
Variablen im Stack zu vermeiden?
Ich bin mir nicht sicher, ob ich verstehe, wie man Rekursion in Python 
verwendet. Ich habe den Python-Code zum Umkehren eines Stacks nur mit 
Rekursion von dieser Seite 
https://www.scaler.com/topics/python/recursion-in-python/ kopiert.
Wie würden wir diesen Code außerdem so ändern, dass jede Instanz der 
aufgerufenen Funktion ihre eigene Stack-Kopie hat?

[Εrnst B. (ernst)]

Und wo bist du bei deiner Hausaufgabe steckengeblieben?

Kannst du genug Python, um zu erklären, was das Wort "stack" in dieser 
Zeile bedeutet:

def reverse(stack):

[Joachim S. (oyo)]

Jr M. schrieb:
> Da die aufgerufene Funktion keinen neuen Wert an die aufrufende Funktion
> zurückgibt, scheint es, dass die Funktion reverse Stack als globale
> Variable verwendet. Ist das nicht eine schlechte Methode, um Rekursion
> zu implementieren? Ist es nicht besser, die Verwendung globaler
> Variablen im Stack zu vermeiden?

stack ist hier keine globale Variable. Was Du vielleicht eigentlich 
meinst, ist, dass die beiden Funktionen stack nicht "out-of-place", 
sondern "in-place" verändern. Sprich: Wenn Du bspw. der Funktion 
reverse() einen stack übergibst, dann hast Du nach Aufruf der Funktion 
reverse() nicht zwei stacks (einmal in der ursprünglichen, einmal in 
umgekehrter Reihenfolge) - sondern die stack-Instanz, die Du an die 
Funktion übergeben hast, hat nach dem Aufruf exakt die umgekehrte 
Reihenfolge wie vorher.

Rekursiv ist der Algorithmus aber trotzdem, das hat damit nichts zu tun.
Wenn Du möchtest, dass das Ganze stattdessen out-of-place geschehen soll 
(also Du nicht stack selbst verändern, sondern eine veränderte Kopie 
haben willst), dann ist das einfachste: Den beiden Funktionen nicht 
stack selbst übergeben, sondern eine Kopie von stack.

[Xanthippos (xanthippos)]

Vielleicht entsteht die Verwirrung, weil man Rekursion normalerweise im 
Zusammenhang mit Funktionaler Programmierung findet.

Dort ist der der zentrale Grundsatz: niemals irgend welche Daten 
verändern, immer die geänderten Daten als Funktionswert zurückliefern.

Die Python Anhänger sehen das nicht so dogmatisch.

[Rick (rick)]

Um Rekursion zu verstehen, muß man jemanden kennen, der Rekursion 
verstanden hat...

[Xanthippos (xanthippos)]

Nein, du musst nur jemanden kennen, der jemanden kennt, den er fragen 
kann.

Erinnerst du dich noch an Gödel Escher Bach?

Der Dschinn hatte es auch nicht Verstanden. Sagte "Einen Augenblick". In 
1/2 Augenblick fragte er seinen übergeordneten Dschinn. Der wiederum 
fragte in 1/4 Augenblick seinen übergeordneten Dschinn. Der fragte in 
1/8 Augenblick seinen Übergeordneten. 1/16 Augenblick, 1/32, 1/64... und 
so weiter bis in alle Unendlichkeit.

Innerhalb von einem Augenblick hatte der ursprüngliche Dschinn die 
Antwort. Obwohl es von den unendlich vielen Dschinns kein einziger 
verstanden hatte.