Wie funktioniert Rekursion(Python)?

Ich versuche gerade zu verstehen, wie Rekursion funktioniert und bin dann auf die Fakultät gestoßen, die man ja rekursiv programmieren kann. Ich verstehe irgendwie nicht, wieso das überhaupt funktioniert, also ich kann dem Programm nicht wirklich folgen. Bei Iteration weiß ich genau was das Programm macht, aber bei Rekursion, weiß ich nicht mal wieso das funktioniert. Ich habe jetzt mal die Fakultätsfunktion programmiert:

def factorial(n):
    if n == 1:
        return 1
    else:
        b = nfactorial(n-1) print(b) return b 

Das Programm gibt mir jetzt durch das "Print" so Zwischenergebnisse und ich kann nicht nachvollziehen, wieso es(z.B. bei Fak(4)) zuerst 12, dann12* 3 und erst zuletzt 1234 berechnet und nicht andersrum. Ich weiß, dass laut Definition Rekursion so funktioniert, also mit Rückeinsetzung, aber am Programm kann ich das nirgendwo erkennen.

LG

Answer 1

[tavkomann]

Auch wenn die iterative Variante zwar meistens effizienter ist, ist die rekursive Variante häufig naheliegender, weil sie eng an die Mathematik anknüpft. Bestimmt kennst du mathematische Funktionen bisher so:

f(x) = 5x²

Dies ist die explizite Darstellung der Funktion. Es gibt aber Fälle, in denen es ziemlich schwierig oder gar unmöglich ist, eine explizite Funktion aufzustellen. In diesen Fällen ist die rekursive Darstellung der Funktion intuitiver. Beispiel Fibonacci:

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)

Hierbei kann man nicht für ein beliebiges n direkt den Wert berechnen, sondern muss den Vorgänger des Folgenglieds kennen. Somit muss es also auch einen Anfang geben, den Rekursionsanfang. Dies sind Werte, die einfach definiert worden sind. Über Rekursionsschritte können die weiteren Werte berechnet werden. Beispiel:

f(5) =             f(n-1)             +             f(n-2)
     =             f(4)               +             f(3)
     =     f(3)      +      f(2)      +          f(2) + f(1)
     = f(2) + f(1)   +       1        +             1 + 1
     =  1   +  1     +       1        +             1 + 1
     =  5

Ich habe versucht, das etwas übersichtlicher aufzuschreiben. Wie du siehst, können wir die einzelnen Werte nicht berechnen, setzen für f(5) also gemäß der Formel f(4) + f(3) ein. Diese beide Werte kennen wir ebenfalls nicht, weshalb wir auch auf beide einzeln nochmals die Formel anwenden. Dies tun wir solange, bis alle Werte bekannt sind. In diesem Fall sind nur f(1) und f(2) bekannt, also müssen wir die Formel solange anwenden, bis der Term nur noch aus diesen beiden Funktionswerten zusammengesetzt ist.

Vor der Entwicklung einer Python-Funktion ist es also sinnvoll, sich den Rekursionsanfang bzw. die Rekursionsbedingungen sowie den Term zur Berechnung weiterer Glieder klar zu machen. Im Anschluss ist die Entwicklung einer solchen Funktion nämlich ziemlich einfach und geht nach einem strengen Schema:

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

Nun wenden wir dies auch auf die Fakultätsfunktion an:

f(1) = 1
f(n) = n * f(n-1)

Setzen wir diese Formeln in unser Programm ein, so ergibt sich:

def fak(n):
    if (n == 1):
        return 1
    else:
        return n * fak(n-1)

Es ist immer dasselbe Prinzip: Rekursionsanfang bestimmen, Term für weitere Glieder bestimmen und in Python-Funktion einsetzen.

Du hast nun fak(4) als Beispiel angesprochen, also gehen wir mal in das Programm hinein:

• fak(4) --> Wir landen im else-Teil, also wird jetzt erst einmal fak(n-1) = fak(3) aufgerufen. Das Ergebnis wird mit n = 4 multipliziert.
• fak(3) --> Wir landen wieder im else-Teil, also wird nun fak(2) aufgerufen und das Ergebnis mit n = 3 multipliziert.
• fak(2) --> Wir landen wieder im else-Teil, also wird nun fak(1) aufgerufen und das Ergebnis mit n = 2 multipliziert.
• fak(1) --> Gibt 1 zurück.
• fak(2) --> Gibt also n * fak(1) = 2 * 1 = 2 zurück
• fak(3) --> Gibt also n * fak(2) = 3 * 2 = 6 zurück
• fak(4) --> Gibt also n * fak(2) = 4 * 6 = 24 zurück
• fak(5) --> Gibt also n * fak(4) = 5 * 24 = 120 zurück. Dies ist das finale Ergebnis.

Betrachte auch folgende Darstellung, die den Ablauf Schritt für Schritt darstellt:

fak(5) = 5 * fak(4)

fak(5) = 5 * fak(4)
             fak(4) = 4 * fak(3)

fak(5) = 5 * fak(4)
             fak(4) = 4 * fak(3)
                          fak(3) = 3 * fak(2)



fak(5) = 5 * fak(4)
             fak(4) = 4 * fak(3)
                          fak(3) = 3 * fak(2)
                                       fak(2) = 2 * fak(1)

fak(5) = 5 * fak(4)
             fak(4) = 4 * fak(3)
                          fak(3) = 3 * fak(2)
                                       fak(2) = 2 * fak(1)
                                                    fak(1) = 1

fak(5) = 5 * fak(4)
             fak(4) = 4 * fak(3)
                          fak(3) = 3 * fak(2)
                                       fak(2) = 2 * 1 = 2

fak(5) = 5 * fak(4)
             fak(4) = 4 * fak(3)
                          fak(3) = 3 * 2 = 6

fak(5) = 5 * fak(4)
             fak(4) = 4 * 6 = 24

fak(5) = 5 * 24 = 120

Ich hoffe, das war einigermaßen verständlich. Melde dich gerne bei weiteren Fragen.

Comments

[Kingworld]

Wird also immer das, was ich als erstes aufrufe immer zuletzt bearbeitet ? In dem Fall rufe ich Fak(4) zuerst auf, und erst im nachhinein Fak(3), Fak(2),... aber es wird sozusagen von unten nach oben bearbeitet. Ist das bei rekursiven Funktionen immer so ? Und nochmal bzgl. des Schemas: Ich gucke mir also immer an, wann ich bei der Funktion sozusagen auf eine konkrete Zahl treffe. Und das n bei dem die Funktion diesen konstanten Wert erreicht setze ich immer als Rekursionsanfang. Und beim Rekursionsschritt gebe ich die Formel an, nach der sich mein Wert berechnen soll oder?

[regex9]

@Kingworld

Wird also immer das, was ich als erstes aufrufe immer zuletzt bearbeitet ?

Ganz genau genommen, nein. Die Reihenfolge der Methodenaufrufe ist wie gewohnt.

Vergleiche mit diesem Programm:

def calculate(operator, number1, number2):
  number = 0
  if operator == "+":
    number = add(number1, number2)
  elif operator == "-":
    number = subtract(number1, number2)
  print number
  
def add(number1, number2):
  return number1 + number2

def subtract(number1, number2):
  return number1 - number2

def main():
  calculate("+", 2, 3)

main()

Der Programmfluss wird folgendermaßen laufen:

1. Aufruf von main
2. Aufruf von calculate
3. Aufruf von add
4. Aufruf von print
5. Abarbeitung des restlichen Codes in main (nichts vorhanden)
6. Abarbeitung des restlichen Codes im globalen Kontext (nichts vorhanden)

Bei einer rekursiven Funktion ist es nicht anders, einzig ein Kontext selben Aufbaus wird stets neu aufgerufen. Das ist alles. Bei der Methode zur Berechnung der Fakultät beispielsweise hüpft der Programmfluss immer wieder in die gleiche Funktion hinein und arbeitet mit dem Vorergebnis, welches via Parameter übergeben wurde, weiter.

Wenn der Kontext abgearbeitet wurde, welcher von seinem äußeren aufgerufen wurde, dann springt der Programmfluss wieder nach oben (gibt womöglich die erarbeiteten Ergebnisse via return mit) und es geht weiter.

Ich gucke mir also immer an, wann ich bei der Funktion sozusagen auf eine konkrete Zahl treffe.

Du schaust bei einer rekursiven Funktion, wann die Abbruchbedingung erfüllt wird. Die muss nicht durch den Zustand einer Zahl repräsentiert werden, du könntest bspw. auch einen boolschen Typ nutzen:

execute(run):
  if run:
    run = checkIfContinue()
    execute(run)

execute(True)

Hier läuft die Rekursion nur so lange, wie die Variable run wahr ist. Die Funktion checkIfContinue könnte nun bspw. eine Zufallszahl generieren, die bestimmt, ob run folgend auf wahr oder falsch gesetzt wird. Wenn hier immer ein wahres Ergebnis berechnet wird, hast du eine klassische Endlosschleife geschaffen.

Ein anderes Beispiel, wenn du über eine Baumstruktur laufen möchtest:

traverse(root):
  for node in root.children:
    traverse(node)
  print root.name

Die Laufzeit dieser Rekursion definiert sich darüber, ob der übergebene Knoten des Baumes noch über einen Kindknoten verfügt oder nicht. Wenn ja, wird die Funktion für jeden dieser Kinder aufgerufen. Jeder Kindknoten überprüft erneut für sich, ob er Kinder beinhaltet oder nicht.

Und das n bei dem die Funktion diesen konstanten Wert erreicht setze ich immer als Rekursionsanfang.

Der Rekursionsanfang definiert den Teil, an dem die Rekursion - also der Lauf von unten nach oben, beginnt oder anders, wenn die Abbruchbedingung erfüllt wurde. Wenn deine Rekursion bei n = 3 starten soll, definierst du die Abbruchbedingung so, dass bei n = 3 die Funktion nicht erneut von sich selbst aufgerufen wird.

Siehe dazu auch dieses Bild aus Wikipedia zum Beispiel der Summenbildung, wo die Zahl 0 logischerweise den Punkt definiert, von dem die Rechnung beginnen soll.

Und beim Rekursionsschritt gebe ich die Formel an, nach der sich mein Wert berechnen soll oder?

Ja.

Zusammengefasst für die Fakultätsberechnung:

def fak(n):
  # Abbruchbedingung
  if (n == 1):
    # Rekursionsanfang
    return 1 
          
  # Rekursionsschritt
  return n * fak(n-1)
        
fak(5)

[Kingworld]

@regex9

Danke für die ausführliche Antwort

Answer 2

[KarlRanseierIII]

Andere haben schon viel dazu geschrieben. Was Du (IMHO) verstehen mußt:

Zunächst folgt ein rekursiver Abstieg, dabei wird der Istzustand auf dem Stack abgelegt. MAn legt also ab, daß factorial mit n aufgerufen wurde. Ich verkürze auf f(n).

Es wird also abgelegt: f(n), f(n-1), f(n-2), ... f(n-x)

Das sind die Funktionsaufrufe der Reihe nach, solange bis x=n ist, denn dann wurde f(1) aufgerufen. Als oberstes auf der Ablage liegt nun die Notiz, daß ich mit f(2) noch nicht fertig war, ich muß also hinter dem Aufruf von f(1) weitermachen, f(1) ist 1 und diesen multipliziere ich mit 2, da ich noch f(2) abarbeite und gebe nun die 2 zurück.

Nun liegt auf meinem Stapel noch f(3), dieses hat als Rückgabe von f(2) eine 2 erhalten und multipliziert mit 3 und gibt diese zurück. usw. usf.

In Deinem Code fehlt die Multiplikation, von daher müßte er n Einsen ausgeben.

Aufgrund der Struktur empfiehlt es sich übrigens immer die Abbruchbedingung am Anfang der Funktion zu prüfen, weil diese den Abstieg terminiert. Dadurch wird es leserlicher.

Answer 3

[MissMaple42]

Bei der Rekrusion ruft die Funktion sich selber auf. Das ganze geschieht so lange, bis die Abbruchbedingung erfüllt ist.

In deinem Fall steht die Aufgabe nach dem Funktionsaufruf. Wenn du z.B. factorial(4) berechnest wird intern 4* factorial(3) aufgerufen. Da die Ausgabe nach dem Funktionsaufruf kommt, wird zu erst 4*factorial(3) berechnet. Erst wenn diese Berechnung abgeschlossen ist, erfolgt die Ausgabe.

Um das besser zu verstehen solltest du mal "Computer spielen" und das ganze an einem Beispiel durchrechnen. Nimm z.B. das Beispiel Fak(4):

Wenn du das machst, solltest du auch erkennen, wann welcher Wert ausgegeben wird

Answer 4

[ETechnikerfx]

Bei der Rekursion ruft die Funktion sich selbst auf, bis die Rekursionsbedingung erfüllt ist. In deinem Falle ruft sich die Funktion factorial im else zweig erneut auf. Dies erfolgt im Code vor der Ausgabe mit print, womit der print nach dem ausführen der funktion erfolgt. Als erstes wird das print der letzten Funktion ausgegeben, welche im else zweig die funktion mit dem parameter 1 aufruft, also mit n = 2.