Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung |
| faecher:informatik:oberstufe:algorithmen:rekursion:callstack_rekursion:start [13.01.2022 12:38] – [Dataillierte Betrachtung des Call-Stacks bei der Rekursion] sbel | faecher:informatik:oberstufe:algorithmen:rekursion:callstack_rekursion:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 |
|---|
| ====== Der Call-Stack und die Rekursion ====== | |
| |
| Ein populäres Beispiel für rekursive Algorithmen ist die Fakultätsfunktion: | |
| |
| <code> | |
| 5! = 5*4*3*2*1 | |
| fakultaet(5) = 120 | |
| fakultaet(3) = 3*2*1 = 6 | |
| </code> | |
| |
| ---- | |
| {{:aufgabe.png?nolink |}} | |
| === (A1) Iterativ === | |
| |
| Implementiere in BlueJ eine iterative Version der Fakultätsfunktion, die als Argument die Zahl entgegennimmt, deren Fakultät berechnet werden soll. | |
| |
| ---- | |
| {{:aufgabe.png?nolink |}} | |
| === (A2) Rekursiv === | |
| |
| Implementiere anhand des folgenden Pseudocodes eine rekursive Version ''fak_rekursiv''. | |
| |
| <code> | |
| fak_rekursiv(int n): | |
| wenn n=1: | |
| return 1 | |
| sonst: | |
| return n*fak_rekursiv(n-1) | |
| </code> | |
| |
| * Was ist der Rekursionsfall, was der Basisfall? | |
| * Teste deine rekursive Methode | |
| |
| ===== Dataillierte Betrachtung des Call-Stacks bei der Rekursion ===== | |
| |
| ^ Was passiert ^ Wie sieht der Stack aus? ^ | |
| |\\ || | |
| | ''fak_rekursiv(3)'' wird aufgerufen.\\ Auf dem Stack wird Speicher für diesen Aufruf reserviert. Es gibt keine Rücksprungadresse.\\ Innerhalb dieses Aufrufs wird ''fak_rekursiv(2)'' (nächster Schtritt) aufgerufen,\\ da die Fallunterscheidung nicht zum Basisfall\\ führt sondern zum Rekursionsfall. | {{ .:fak001.drawio.png |}} | | |
| |\\ || | |
| | ''fak_rekursiv(2)'' wird aus dem vorhergehenden Aufruf heraus aufgerufen.\\ Auf dem Stack wird Speicher für diesen Aufruf reserviert: Wichtig: Jeder Aufruf hat seinen eigenen\\ Speicherbereich für Variablen, d.h. jeder Aufruf\\ von ''fak_rekursiv'' hat sein eigenes ''n'' auf die die anderen Aufrufe nicht zugreifen können.\\ Die Rücksprungadresse befindet sich jetzt **im vorigen Aufruf** der rekursiven Methode selbst.\\ Das ist anders, als beim ersten Beispiel für den Call-Stack!\\ Da erneut der Rekursionsfall eintritt, wird aus diesem Aufruf heraus ''fak_rekursiv(1)'' aufgerufen.| {{ .:fak002.drawio.png |}} | | |
| |\\ || | |
| | ''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 |}} | | |