0 Daumen
40 Aufrufe

Aufgabe:

Könnte mir jemand das Thema Rekursion erklären? Ich komme da einfach nicht so ganz hinter trotz x Tutorials und Beiträge.

Beispiel 1: Fakultät:

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

Wenn ich die Fakultät von 4! berechnen möchte:

1. Aufruf: Ich lande nicht im Rekursionsanker (if-Abfrage) sondern im Else-Zweig und dann gehts so weiter:

return: 4 * fac(3)

return: 3 * fac(2)

return: 2* fac(1)

Und nun hakts bei mir: Jetzt greift ja der Rekursionsanker if n == 1. Es wird 1 zurückgegeben (Wohin?) Und was passiert dann? Nun soll ja der Weg "zurückgegangen" werden wenn ich das recht verstanden habe, aber ich verstehe einfach nicht wie und warum.


Und auch wenn es vermutlich mit meinem Wissensstand sinnlos ist, sich gleich ans nächst größere Problem zu setzen:

Wie läuft das in der Fibonacci-Funktion ab? Da werden ja dann auch noch die Funktionen addiert.

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

Würde mich freuen, wenn mir das jemand sehr einfach erklären könnte. Ich habe es schon mit dem Debugger versucht nachzuvollziehen, print-statements eingefügt und und und... Irgendwie ist der Groschen noch nicht gefallen.

von

1 Antwort

+1 Daumen
Es wird 1 zurückgegeben (Wohin?)

In dem Ausdruck 2* fac(1) wird fac(1) durch 1 ersetzt.

Ergebnis ist 2. Rückgabewert von fac(2) ist also 2.

3 * fac(2)

In dem Ausdruck 3* fac(2) wird fac(2) durch 2 ersetzt.

Ergebnis ist 6. Rückgabewert von fac(3) ist also 6.

4 * fac(3)

In dem Ausdruck 4* fac(3) wird fac(3) durch 6 ersetzt.

Ergebnis ist 24. Rückgabewert von fac(4) ist also 24.

Und so weiter.

Wenn ich die Fakultät von 4! berechnen möchte:

Dann musst du fac(fac(4)) aufrufen.

Wenn du die Fakultät von 4 berechnen möchtest, dann musst du fac(4) aufrufen.

Auch wenn du 4! berechnen möchtest, musst du fac(4) aufrufen.

von 3,3 k

Hmm.. Ich glaube so langsam komme ich dahinter.. Zumindest was die Fakultäts-Berechnung betrifft.


Aber bei den Fibonacci-Zahlen stehe ich noch auf dem Schlauch. In welcher Reihenfolge wird dort gearbeitet?

Bsp. Ich will die 7. Fibonacci-Zahl ( 13 )

Wird nun erst fib(n-1) durchgearbeitet und dann fib(n-2) oder läuft das Parallel oder wie kann ich mir das vorstellen?

Wird nun erst fib(n-1) durchgearbeitet und dann fib(n-2)

In Python ist das so, siehe 6.16. Evaluation order.

In anderen Programmiersprachen ist das eventuell anders, einige Programmiersprachen machen überhaupt keine Zusicherung, welcher Summand zuerst ausgewertet wird.

oder läuft das Parallel

Auch das ist bestimmt in einigen Programmiersprachen möglich.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community