Rekursion kapieren

[Kevin0101]

Hallo

ich zerbreche mir gerade den Kopf darüber wie genau rekursive Funktionen funktionieren, vllt kanns mir ja hier jemand für doofe erklären. Habe schon allerlei Videos gesehen und im Netz gestöbert aber irgendwie wills nicht klick machen...

Als Beispiel die Fibonacci-Zahlen rekursiv:

Code: Alles auswählen

def fib (n):
    if n<2:
        return n
    else:
        return (fib(n-1) + fib(n-2))

Wenn ich nun z.b die 5. Fibonacci Zahl berechnen möchte, läuft die Funktion ja so ab:
fib(4)+ fib(3)
Dann wird für die beiden wieder die Funktion aufgerufen also für fib(4): fib(3) + fib(2)
und für fib(3): fib(2) + fib(1) usw...

Bis dann irgendwann der Rekursionsanker "greift".

Was ich nicht kapiere ist: WARUM "wickelt" sich die Funktion dann wieder auf?
Also WIESO werden die Teilergebnisse dann folgerichtig zusammenaddiert um aufs Ergebnis zu kommen?

Habe irgendwo gelesen, dass die Teilergebnisse intern in einer LIFO-Struktur im Speicher abgelegt werden (wenn ich das richtig verstanden habe), aber damit komm ich auch nicht so richtig weiter...

Kann mir das jemand für ganz Doofe erklären?

Danke im Voraus!

[/me]

Also WIESO werden die Teilergebnisse dann folgerichtig zusammenaddiert um aufs Ergebnis zu kommen?

Das hier steht in deinem Codebeispiel

Code: Alles auswählen

        return fib(n-1) + fib(n-2)

Das ist die Addition. Was fehlt dir da noch?

[/me]

Wenn ich nun z.b die 5. Fibonacci Zahl berechnen möchte, läuft die Funktion ja so ab:
fib(4)+ fib(3)
Dann wird für die beiden wieder die Funktion aufgerufen also für fib(4): fib(3) + fib(2)
und für fib(3): fib(2) + fib(1) usw...

Nicht, dass hier schon ein Missverständnis auftritt. Du schreibst "Dann wird für die beiden wieder die Funktion aufgerufen". "Dann" klingt so nach "Danach" und diese Interpretation wäre falsch. Der Aufruf für z.B. fib(4) läuft prinzipiell in folgender Reihenfolge ab.

Code: Alles auswählen

fib(4)
  fib(3)
    fib(2)
	  fib(1) -> 1
	  +
	  fib(0) -> 1
	  = 2
	+
	fib(1) -> 1
	= 3
  +
  fib(2)
    fib(1) -> 1
	+
	fib(0) -> 1
	= 2
  = 5

[Buchfink]

@Kevin0101

hast Du denn schon mal mit einem Debugger gearbeitet?
Wenn ich Code nicht sofort verstehe, setze ich einfach mal Haltepunkte und schaue wo ich im Debugger so lang laufe. Dann kann man auch sehen, wo er wieder "rausspringt" etc.

[rogerb]

@Kevin0101,

zusätzlich zu den genannten Vorschlägen, nämlich die verschachtelten Funktionsaufrufe einfach mal aufzuschreiben und auch mit dem Debugger zu arbeiten noch ein paar Anmerkungen:

Was ich nicht kapiere ist: WARUM "wickelt" sich die Funktion dann wieder auf?

Vielleicht kann man den Code etwas auseinanderziehen um es deutlicher zu machen:

Code: Alles auswählen

def fib (n):
    # Rekursionsanker
    if n<2:
        return n

    # Rekursionsschritt
    n_minus_one = fib(n-1)
    n_minus_two = fib(n-2)
    return n_minus_one + n_minus_two

Denn das "wieder aufwickeln" geschieht dadurch, dass beim "return" wieder an die Stelle zurückgesprungen wird, von wo die Funktion aufgerufen wurde. Bei jedem Aufruf der Funktion werden die lokalen Variablen auf einem Stack (oder FIFO) zwischen gespeichert, um beim Rücksprung wieder zur Verfügung zu stehen.

Ein Problem rekursiv zu lösen, bedeutet es in immer kleinere Teilprobleme zu zerstückeln bis es eine triviale Lösung gibt:

Ich weiß nicht was die Fibonaccizahl von 5 ist, aber ich weiß, dass es die Summe der der Fibonaccizahl von 3 und 4 ist. Ich weiß nicht was die Fibonaccizahl von 4 ist, aber ich weiß, dass es die Summe der Fibonaccizahl von 2 und 3 ist, ich weiß nicht ... usw. bis zum trivialen Fall: Die Fibonaccizahl von 1 ist 1 und die Fibonaccizahl von 0 ist 0.
Jetzt habe ich alles was ich brauche und kann das ganze rückwärts durch einfache Summierung der Zwischenergebnisse wieder aufrollen. Das schöne ist, dass ich mir die Zwischenergebnisse nicht zu merken brauche, da sie automatisch auf dem Stack abgelegt werden.

[Kevin0101]

Ich bin glaube ich ein hoffnungsloser Fall...

Trotzdem schonmal danke für eure Bemühungen!!!

Mit dem Debugger habe ich es natürlich auch schon versucht aber half mir leider auch nicht so richtig..



Ich habe mal meinen "geistigen Breakpoint" im Baum eingezeichnet.. Da greift ja der Rekursionsanker das erste mal, richtig?
fib(1) sind 1. Soweit klar.

Und ab da steck ich fest.
Wo und warum (in welcher Zeile) gehts dann weiter?

Einen "step weiter" ist n dann ja plötzlich 2 ??

Irgendwie schafft mich Thema.. Könnte mir vllt jemand ab da das Ganze step-by-step erklären?

Edit:
Oder um mein Problem noch verständlicher zu machen:
https://www.youtube.com/watch?v=zg-ddPbzcKM
Hier ist das "auswickeln" der Funktion super erklärt und auch wie es sich am ENDE wieder zusammensetzt, aber leider nicht Wann und Wie welcher Zwischenschritt gemacht wird. Oder ich habs auch da nicht ganz kapiert....

[nezzcarth]

Ich bin glaube ich ein hoffnungsloser Fall...

Das glaube ich nicht – aber ich glaube, du machst es dir vielleicht zu schwer, bzw. versuchst mehr zu verstehen, als du müsstest. Bei Rekursion ist es m. M. n. einfacher, es zuerst konzeptuell zu verstehen. Wenn man dann unbedingt will, kann man sich damit befassen, wie wo wann, in der konkreten Programmiersprachenimplementierung, die man gerade verwendet, was genau passiert

Funktionen sind:
1. Ein Stück-Code, das Parameter bekommen kann und einen Wert zurück liefert.
2. Ein Stück-Code, zu dem beim dessen Aufruf – bildlich gesprochen – gesprungen wird und nach dessen Ausführung wieder an den Ausgangspunkt zurückgesprungen wird. Statt des Funktionsaufrufs steht dort dann aber – ebenfalls wieder bildlich gesprochen – das Ergebnis der Funktion.

Letzteres war damals, als ich als Schüler das erste mal Rekursion kennengelernt habe, mein Denkfehler. Als kleinen Trick kann man sich die Summen-Bildung auch noch als Funktion vorstellen, die zwei Zahlen bekommt und das Ergebnis zurückgibt. Dann hat man vom Konzept für den einfachen Fall x=3 so etwas dort stehen:

Code: Alles auswählen

sum(fib(2), fib(1)) # sum bildet die Summe der beiden Argumente. Da man aber mit Funktionen schlecht rechnen kann, müssen diese zuerst von Links nach rechts und von innen nach außen aufgelöst, also aufgerufen werden
sum(1, fib(1)) # fib(2) wurde evaluiert und (von der Idee her) das Ergebnis dort eingefügt. Jetzt geht es weiter mit fib(1)
sum(1, 1) # fib(1) wurde ebenfalls evaluiert und das Ergebnis eingesetzt. Jetzt stehen da zwei Ganzzahlen aus denen sum nun die Summe bilden kann.
2

Das kann man nun für fib(4) fortführen:

Code: Alles auswählen

sum(fib(3), fib(2)) # Aus fib(3) wird fib f(2) + fib(1)
sum(sum(fib(2), fib(1)), fib(2))) # fib(3) können wir hier von oben übernehmen. Das sind wieder dieselben Schritte, nur diesmal "eingebettet".
sum(sum(1, fib(1)), fib(2))
sum(sum(1, 1), fib(2))
sum(2, fib(2))
sum(2, 1)
3

(Ich hoffe da hat sich kein Fehler eingeschlichen … )

[snafu]

Hilfreich ist natürlich auch, erstmal die Fibonacci-Folge im Sinne der rekursiven Verarbeitung wirklich zu verstehen. Gerade im Bereich < 5 zu wissen, welche 1 oder 2 woher kommt und wie sich das zusammenfügt, fällt nicht jedem leicht.

Und ansonsten muss man sich einen Cursor vorstellen, der vor jedem Ausdruck steht und solange auflöst bis etwas ohne weitere "Handlungsanweisung" rauskommt, hier also die 1. Erst dann kann der nebenstehende Ausdruck verarbeitet werden. Für die Operationen auf den tieferen Ebenen wird bei jedem Funktionsaufruf jeweils ein neuer Cursor erschaffen, der wieder von links nach rechts den Ausdruck abgrast und sein Ergebnis zum Aufrufer gibt. So gesehen sorgt gar nicht mal der "Ober-Cursor" für die komplette Auflösung, sondern er stößt lediglich seinen nächsten Helfer an. Das Prinzip der Definitionen, die zu neuen Definitionen führen, wurde ja schon angesprochen.

[narpfel]

Vielleicht auch hilfreich zum Verständnis: Python Tutor mit einer Visualisierung der Fibonacci-Funktion.

[Kevin0101]

Yeees! Ich habs endlich kapiert...

Ich habe mir dafür mal jeden Funktionsaufruf komplett aufgemalt
Dann hats eeeeeeeeeendlich Klick gemacht.

Uffff! Das war meine bisher härteste Nuss beim Programmieren lernen. Obwohls einem hinterher wieder alles komplett logisch und easy vorkommt..

Ich denke ich bleib dann aber in der Praxis trotzdem lieber bei den iterativen Varianten

Nochmal vielen dank an alle !

[rogerb]

Herzlichen Glückwunsch!

Da ich das Thema interessant fand, hab ich mal eine Visualisierung erzeugen lassen:

Code: Alles auswählen

import inspect


def call_stack_depth(stack, function_name):
    return sum(1 for frame_info in stack() if frame_info.function == function_name)


def output(string, depth):
    filler = "|   " * depth
    print(f"{filler}{string}")


def visualize(function):
    def wrapper(*args, **kwargs):
        depth = call_stack_depth(inspect.stack, function.__name__)
        output(f"+ {function.__name__}{args}", depth)
        output("|", depth)
        value = function(*args, **kwargs)
        output(f"{value} <- {function.__name__}{args}", depth)
        output("", depth)
        return value

    return wrapper


@visualize
def fib(n):
    if n < 2:
        return n

    return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    fib(5)

"""
Ausgabe:

+ fib(5,)
|
|   + fib(4,)
|   |
|   |   + fib(3,)
|   |   |
|   |   |   + fib(2,)
|   |   |   |
|   |   |   |   + fib(1,)
|   |   |   |   |
|   |   |   |   1 <- fib(1,)
|   |   |   |
|   |   |   |   + fib(0,)
|   |   |   |   |
|   |   |   |   0 <- fib(0,)
|   |   |   |
|   |   |   1 <- fib(2,)
|   |   |
|   |   |   + fib(1,)
|   |   |   |
|   |   |   1 <- fib(1,)
|   |   |
|   |   2 <- fib(3,)
|   |
|   |   + fib(2,)
|   |   |
|   |   |   + fib(1,)
|   |   |   |
|   |   |   1 <- fib(1,)
|   |   |
|   |   |   + fib(0,)
|   |   |   |
|   |   |   0 <- fib(0,)
|   |   |
|   |   1 <- fib(2,)
|   |
|   3 <- fib(4,)
|
|   + fib(3,)
|   |
|   |   + fib(2,)
|   |   |
|   |   |   + fib(1,)
|   |   |   |
|   |   |   1 <- fib(1,)
|   |   |
|   |   |   + fib(0,)
|   |   |   |
|   |   |   0 <- fib(0,)
|   |   |
|   |   1 <- fib(2,)
|   |
|   |   + fib(1,)
|   |   |
|   |   1 <- fib(1,)
|   |
|   2 <- fib(3,)
|
5 <- fib(5,)
"""

Das könnte in begrenztem Maße auch mit anderen rekursiven Algorithmen funktionieren.