Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:callstack_rekursion:start [13.01.2022 12:51] – [Dataillierte Betrachtung des Call-Stacks bei der Rekursion] sbel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:callstack_rekursion:start [11.12.2023 15:51] (aktuell) – Marco Kuemmel
@@ Zeile 23: / Zeile 23: @@
 <code>
 fak_rekursiv(int n):
-  wenn n=1:
+  wenn n=1 oder n=0:
     return 1
   sonst:
@@ Zeile 42: / Zeile 42: @@
 | ''fak_rekursiv(1)'' wird aus dem vorhergehenden Aufruf heraus aufgerufen.\\ Auf dem Stack wird Speicher für diesen Aufruf reserviert.\\ Die Rücksprungadresse befindet sich wiederum **im vorigen Aufruf** der rekursiven Methode selbst.\\  **Jetzt tritt der Basisfall ein!**|       {{ .:fak003.drawio.png |}}                |
 |\\ ||
-|Die ist der erste Aufruf, der vollständig abgeschlossen ist.\\ Es wird kein neuer Aufruf von ''fak_rekursiv'' auf den Call-Stack gelegt, sondern\\ der Aufruf von ''fak_rekursiv(1)'' endet damit, dass ''1'' an die\\ aufrufende Stelle zurückgegeben wird und die zum Aufruf gehörenden\\ Daten vom Stack entfernt werden. | {{ .:fak004.drawio.png |}}  |
+|Dies ist der erste Aufruf, der vollständig abgeschlossen ist.\\ Es wird kein neuer Aufruf von ''fak_rekursiv'' auf den Call-Stack gelegt, sondern\\ der Aufruf von ''fak_rekursiv(1)'' endet damit, dass ''1'' an die\\ aufrufende Stelle zurückgegeben wird und die zum Aufruf gehörenden\\ Daten vom Stack entfernt werden. | {{ .:fak004.drawio.png |}}  |
 |\\ ||
-|Damit hat der Aufruf von ''fak_rekursiv(2)'' alle Informationen,\\ um abgeschlossen zu werden: \\ der Ausdruck ''n*fak_rekursiv(n-1)'' kann jetzt zu ''2*1'' ausgewertet und an die\\ aufrufende Stelle zurückgegeben werden.\\ Die zum Aufruf gehörenden\\ Daten werden vom Stack entfernt. | {{ .:fak005.drawio.png |}}  |
+|Damit hat der Aufruf von ''fak_rekursiv(2)'' alle Informationen,\\ um abgeschlossen zu werden: \\ Der Ausdruck ''n*fak_rekursiv(n-1)'' kann jetzt zu ''2*1'' ausgewertet und an die\\ aufrufende Stelle zurückgegeben werden.\\ Die zum Aufruf gehörenden\\ Daten werden vom Stack entfernt. | {{ .:fak005.drawio.png |}}  |
+|\\ ||
+|Jetzt hat auch der Aufruf von ''fak_rekursiv(3)'' alle Informationen,\\ um abgeschlossen zu werden: \\ Der Ausdruck ''n*fak_rekursiv(n-2)'' kann jetzt zu ''3*2'' ausgewertet \\ und an die aufrufende Stelle zurückgegeben werden. \\ Die zum Aufruf gehörenden Daten werden vom Stack entfernt. \\ **Der Call-Stack ist leer, der Aufruf der Methode beendet.** | {{ .:fak006.drawio.png |}}  |
+===== Zusammenfassung =====
+<callout type="warning" icon="false">
+  * **Rekursion** bedeutet, dass eine Funktion/Methode sich selbst aufruft.
+  * Alle rekursiven Funktionen haben eine Fallunterscheidung: den **Basisfall** und den **Rekursionsfall**.
+  * Die Funktionsaufrufe werden auf dem Aufruf-Stack gespeichert, dabei wird dieser immer größer bis der Basisfall eintritt. Anschließend wird der Stack von oben nach unten "abgearbeitet", bis er leer ist und damit der Aufruf der rekursiven Methode endet.
+  * Der Aufruf-Stack kann unter Umständen sehr groß werden und sehr viel Arbeitsspeicher belegen.
+</callout>