staging.inyokaproject.org

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?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 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)
        inserAtBottom(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)
        inserAtBottom(stack, temp)

Ich bin mir nicht sicher, ob ich verstehe, wie man Rekursion in Python verwendet. Ich habe den Python-Code zum Umkehren eines Stapels nur mit Rekursion von hier kopiert.

Wie würden wir diesen Code außerdem so ändern, dass jede Instanz der aufgerufenen Funktion ihre eigene Stack-Kopie hat?

Die Variable stack wird da einfach nur durchgereicht - da ist keine globale Variable im Spiel.

Ich vermute die Verwirrung stammt daher, wie Python-Objekte funktionieren - stack ist der Name für ein Python-Object (das kannst du dir wie ein Pointer auf ein Objekt in C vorstellen), der an die Funktion übergeben wird. Wenn man id() nutzt, um sich die Identität des Objekts anzusehen, wird das hoffentlich klarer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

stack = []
print(id(stack))

def add_element(l):
    print(id(l))
    l.append('Element')
    print(id(l))

add_element(stack)
print(stack)
print(id(stack))

Wichtig ist zu wissen, dass bei neuen Zuweisungen die Identität wechselt - z.B.:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

x = 0
print(id(x))

def inc(n):
    print(id(n))
    n += 1
    print(id(n))

inc(x)
print(x)
print(id(x))

Python hat auch keine so strengen Regeln mit Borrow-Checker wie z.B. Rust, wo man die Variable stack explizit aus der Funktion zurückgeben müsste, um sie weiterhin nutzen zu können.

kimberly schrieb:

Wie würden wir diesen Code außerdem so ändern, dass jede Instanz der aufgerufenen Funktion ihre eigene Stack-Kopie hat?

https://docs.python.org/3/faq/programming.html#how-do-i-copy-an-object-in-python erläutert, wie du eine Kopie machen kannst. Du müsstest dann eine Kopie von stack an die Methoden übergeben und in der Aufrufenden Funktion den Wert von stack durch den Rückgabewert der Funktionen ersetzen - eine Kopie des Stacks für jeden Funktionsaufruf hat den Nachteil, dass das Zeit kostet und nichts bringt, weil man - so wie das Ganze aufgebaut ist - den manipulierten Stack weiternutzen will.

Hallo,

Ich bin mir nicht sicher, ob ich verstehe, wie man Rekursion in Python verwendet.

Die allgemeinere Antwort lautet: am besten gar nicht.

Grund: natürlich kann Python Rekursion. Ein einfaches Beispiel, was es bergeweise im Netz gibt, ist z.B. ein rekursiv implementierte Fibonacci Funktion. Aber: Python hat null Optimierungen für Rekursion, weil man in Python eigentlich nach Möglichkeit alles iterativ macht. Bis Python 3.10 hatte Python auch ein relativ niedriges Rekursion Limit von 1000, mit Python 3.11 ist das aufgrund einer Änderung am Code von Python deutlich nach oben gesetzt worden. Ist halt aber immer noch null optimiert und dadurch relativ lahm.

Gruß, noisefloor

noisefloor schrieb:

Python hat null Optimierungen für Rekursion, weil man in Python eigentlich nach Möglichkeit alles iterativ macht. Bis Python 3.10 hatte Python auch ein relativ niedriges Rekursion Limit von 1000, mit Python 3.11 ist das aufgrund einer Änderung am Code von Python deutlich nach oben gesetzt worden. Ist halt aber immer noch null optimiert und dadurch relativ lahm.

Ich würde sogar so weit gehen zu sagen, dass Rekursion in allen Sprachen problematisch ist / nicht benutzt werden sollte, die dafür keine Optimierungen eingebaut haben. Die Stackframes fressen einfach zu viel von dem begrenzten Stackspeicher, wenn das Problem größer ist als kleine Beispiele.

Bei Fibonacci kommt noch hinzu, dass der naive rekursive Algorithmus extrem ineffizient ist, weil er ständig Dinge neu berechnet, die schon berechnet worden sind. ☺

rklm schrieb:

Bei Fibonacci kommt noch hinzu, dass der naive rekursive Algorithmus extrem ineffizient ist, weil er ständig Dinge neu berechnet, die schon berechnet worden sind. ☺

Dem Problem kann man mit Memoisation begegnen: https://docs.python.org/3/library/functools.html#functools.cache

seahawk1986 schrieb:

rklm schrieb:

Bei Fibonacci kommt noch hinzu, dass der naive rekursive Algorithmus extrem ineffizient ist, weil er ständig Dinge neu berechnet, die schon berechnet worden sind. ☺

Dem Problem kann man mit Memoisation begegnen: https://docs.python.org/3/library/functools.html#functools.cache

Ich weiß, aber das macht es auch nicht besser (allerdings schneller). Iterativ ist einfach die schlaueste Lösung in diesem Fall.

Hallo,

man in der Schule oder Uni Programmieren mit Python lernt läuft einem sicherlich auch mal Rekursion über den Weg. Gehört ja nun mal zum Wissen rund um Programmierung dazu. Nur scheinen leider immer mal wieder Lehrer und Dozenten zu vergessen darauf hinzuweisen, dass1 Python + Rekursion "in the wild" keine gute Idee ist, weil ineffizient. Klar kann man das z.B. mit Memoisierung ein bisschen pimpen, was aber IMHO nicht die grundsätzliche nicht vorhandene Optimierung auf Rekursion wett macht.

Gruß, noisefloor

rklm schrieb:

seahawk1986 schrieb:

rklm schrieb:

Bei Fibonacci kommt noch hinzu, dass der naive rekursive Algorithmus extrem ineffizient ist, weil er ständig Dinge neu berechnet, die schon berechnet worden sind. ☺

Dem Problem kann man mit Memoisation begegnen: https://docs.python.org/3/library/functools.html#functools.cache

Ich weiß, aber das macht es auch nicht besser (allerdings schneller). Iterativ ist einfach die schlaueste Lösung in diesem Fall.

Wenn man es richtig macht, braucht man weder Memoisation noch Iteration, Democode Scala:

1
2
3
4
5
6
7
8

def fib (n: Int) : Int = {
  def go (acc1: Int, acc2: Int, n: Int): Int = {
    if (n == 0) acc1 else
      go (acc2 + acc1, acc1, n - 1) 
  }
  if (n <= 1) 0 else 
  go (1, 0, n-2) 
}

Hallo,

Wenn man es richtig macht, braucht man weder Memoisation noch Iteration, Democode Scala:

Es geht aber um Python und nicht im Scala... Wie man es anders / ggf. besser in anderen Sprachen macht hat nix mit der Ausgangsfrage des TE zu tun.

Gruß, noisefloor

Ich kann zwar kein Python, aber von unten nach oben statt von oben nach unten kann man auch in Python zählen.

So sieht's in Bash aus, wenn Du Scala nicht verstehst:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

_fib () { 
lo=$1
hi=$2
max=$3
if ((max == 0)) 
then
    echo $hi
else
    _fib $hi $((lo+hi)) $((--max))
fi 
}

fib () { 
  _fib 1 1 $1
} 

Hallo,

darum geht es doch nicht. Du kannst den Code gerne noch in X beliebigen anderen Programmiersprachen showcasen - bringt dem TE aber nichts, weil der Python verwenden und verstehen will oder muss. Das sich eine Fibunaccisequenez, die übrigens auch nichts mit der Ausgangsfrage zu tun hat, sondern wurde nur als erwähntes Beispiel für eine typisches Beispiel aus dem Lernumfeld genannt. D.h. deine Codbeispiele haben auch mit der Ausgangsfrage des TEs nichts zu tun.

Gruß, noisefloor

noisefloor schrieb:

Hallo,

darum geht es doch nicht. Du kannst den Code gerne noch in X beliebigen anderen Programmiersprachen showcasen - bringt dem TE aber nichts, weil der Python verwenden und verstehen will oder muss.

Was dem TE etwas bringt oder nicht soll der selbst sagen, wenn er will.

Jmd. schrieb:

Es geht aber um Python und nicht im Scala.

Im Beispiel ging es eben nicht um Scala, sondern darum, wie man die Fibonaccizahlen von unten ohne Wiederholung rekursiv berechnet, und das geht auch in Python. Weil ich kein Python kann habe ich es in Scala gezeigt, und weil nicht begriffen wurde, dass das keine scalaeigene Besonderheit ist, sondern sprachagnostisch, habe ich es noch mal in Bash gezeigt.

Wie man es anders / ggf. besser in anderen Sprachen macht hat nix mit der Ausgangsfrage des TE zu tun.

Deswegen war es auch keine Antwort auf die Ausgangsfrage.

Das sich eine Fibunaccisequenez, die übrigens auch nichts mit der Ausgangsfrage zu tun hat, sondern wurde nur als erwähntes Beispiel für eine typisches Beispiel aus dem Lernumfeld genannt. D.h. deine Codbeispiele haben auch mit der Ausgangsfrage des TEs nichts zu tun.

Deine Einwürfe haben nichts mit meinen Codebeispielen zu tun, die das typische Fibonaccibeispiel aus dem Lernumfeld thematisieren und zeigen, wie man es ohne memoization lösen kann, solange das Ergebnis unter 10^18 bleibt. Diese Technik lässt sich auch auf manch anderen Algorithmus, wie etwa die Fakultät übertragen und relativiert die pauschale Kritik an rekursiven Funktionen.