# 4.5 Call Stack Quelle: https://inf.zone/lectures/4-memory/short-4-5-call-stack/ ## Video [Video ansehen (1080p)](https://videos.inf.zone/4dfb4f13b6385003/short-4-5-call-stack-1080p.mp4) · [Video (720p)](https://videos.inf.zone/4dfb4f13b6385003/short-4-5-call-stack-720p.mp4) · [Video (480p)](https://videos.inf.zone/4dfb4f13b6385003/short-4-5-call-stack-480p.mp4) · [Video auf YouTube](https://youtu.be/3oBz_CvekXE) ## Hinweise zu diesem Video **Korrekturen** Die Korrekturen betreffen das Video. In den Folien zum Herunterladen sind sie eingearbeitet, soweit sie die Folien betreffen. - Folien 4 bis 16: Die Funktion fact hat nur den Basisfall n == 1; für n = 0 ruft sie sich ohne Ende selbst auf. Richtig ist der Basisfall „if (n <= 1) return 1;“, wie im Short 3.5 beschrieben. Für die gezeigte Rechnung fact(5) ändert sich nichts. ## Material - [Folien](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf) - Folien und Transkript: unten auf dieser Seite ## Folien und Transkript *Folientext aus den PDF-Folien, darunter jeweils der gesprochene Text des Videos. Der gesprochene Text ist maschinell transkribiert und nachkorrigiert, kann aber noch Fehler enthalten; im Video sprechen abwechselnd Prof und eine AI-Figur, die Sprecherwechsel sind nicht markiert. Die Zuordnung zu den Folien ist ungefähr. Die Zeitangaben verlinken auf die Stelle im Video (YouTube). Maßgeblich sind Video und Folien.* ### Folie 1 — Call Stack [Folie 1 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=1) #### Transkript **[Video 00:00–00:30](https://www.youtube.com/watch?v=3oBz_CvekXE&t=0)** Dies ist Inf-Einf-B. Heute der Call Stack. Ah, da bist du ja. Bereit für unsere Vorlesung über den Call Stack? Natürlich. Wobei ich mich frage, ob sich die Studierenden von unserem Video über dynamische Speicherallokation schon genug erholt haben. Ja, ein bisschen mehr Vertrauen in unsere Studierenden finde ich jetzt schon angebracht. Außerdem haben wir den Call Stack ja schon kurz im Video zur Rekursion angeschnitten. Und so kompliziert wird es heute ja gar nicht. In Ordnung. **[Video 00:30–01:08](https://www.youtube.com/watch?v=3oBz_CvekXE&t=30)** Also heute werden wir uns genauer ansehen, wie der Call Stack funktioniert. Im Video über Rekursion mag es vielleicht magisch ausgesehen haben, wie Funktionen aufeinander warten und ihre Daten weitergeben. ### Folie 2 [Folie 2 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=2) Wenn Sie eine Funktion aufrufen, reserviert das System für diese Funktion Speicherplatz im StackSpeichersegment. Diese Speicherbereiche nennen wir häufig Stack Frames oder Funktionsrahmen. Es können mehrere Stack Frames gleichzeitig im Speicher existieren. Wenn main() die Funktion move() aufruft, welche dann direction() aufruft, gibt es für die drei Funktionen je einen Stack Frame. #### Transkript **[Video 00:30–01:08](https://www.youtube.com/watch?v=3oBz_CvekXE&t=30)** Heute werden wir diesen Mechanismus im Detail betrachten. Lassen Sie uns zunächst die grundlegende Funktionsweise des Call Stacks betrachten. Wenn Sie eine Funktion aufrufen, passiert im Hintergrund mehr, als man zunächst vermuten würde. Das System reserviert automatisch einen bestimmten Bereich im Speicher, sozusagen einen Arbeitsbereich für die aufgerufene Funktion. Diese Speicherbereiche bezeichnen wir als Stack Frames oder Funktionsrahmen. Wenn Sie zum Beispiel in Ihrer Funktion einige Variablen deklarieren, wird in diesem Frame der entsprechende Platz dafür reserviert. **[Video 01:08–01:32](https://www.youtube.com/watch?v=3oBz_CvekXE&t=68)** bei drei Integern beispielsweise drei Vier-Byte-Blöcke plus zusätzlicher Platz für Berechnungen. Ein wichtiger Aspekt ist, dass mehrere solcher Frames gleichzeitig existieren können. Nehmen wir ein Beispiel: Wenn die main-Funktion eine Funktion move aufruft und diese wiederum direction aufruft, dann existieren zu diesem Zeitpunkt drei Frames gleichzeitig im Speicher. Die Anordnung dieser Frames folgt einem sehr klaren Prinzip: Sie werden wie in einem Stapel, eben einem Stack ### Folie 3 — Der Call Stack [Folie 3 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=3) Diese Frames liegen im Stack-Segment und werden in einer Stack-Datenstruktur gespeichert. Der Frame der zuletzt aufgerufenen Funktion liegt immer „oben“ auf dem Stack. Wenn eine neue Funktion aufgerufen wird, wird ein neuer Frame auf den Stack gepusht – er wird zum aktiven Frame. Wenn eine Funktion ihre Arbeit beendet, wird ihr Frame vom Stack gepoppt, und der Frame direkt darunter wird zum neuen aktiven Frame an der Spitze des Stacks. Die vorherige Funktion setzt ihre Arbeit dann genau dort fort, wo sie durch den Funktionsaufruf unterbrochen wurde. #### Transkript **[Video 01:32–02:12](https://www.youtube.com/watch?v=3oBz_CvekXE&t=92)** übereinander geschichtet. Der Frame der Funktion, die als Letztes aufgerufen wurde, liegt dabei immer ganz oben. Wird eine neue Funktion aufgerufen, passieren zwei Dinge: Ein neuer Frame wird oben auf den Stack gelegt, man sagt auch gepusht und wird damit automatisch zum aktiven Frame. Der vorherige Frame liegt dann im Speicher darunter, also an einer höheren Adresse im Stackbereich. Wenn eine Funktion fertig ist, das sei es durch Return oder durch Erreichen des Funktionsendes, wird ihr Frame vom Stack entfernt. Im Englischen sagt man zum Herunternehmen von einem Element vom Stack auch pop, also man poppt das Element vom Stack. Das ist quasi das Gegenteil vom Drauflegen, also dem Pushen. Also der Frame, der darunter lag, wird jetzt wieder zum neuen aktiven Frame an der Spitze des Stacks. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Die Funktion, zu der zurückgekehrt wurde, setzt dann ihre Arbeit exakt an der Stelle fort, an der sie die andere Funktion aufgerufen hatte. Ja, das erinnert mich an meine eigene Studienzeit und die Arbeit mit Lochkarten. Die musste man ja auch stapeln. Da war alles noch viel expliziter als heute, wo man noch ähnliche Sachen verwendet, aber gar nichts mehr sieht und daher gar nicht so gut verstehen kann. Moment mal. ### Folie 4 [Folie 4 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=4) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Also nach meinen Berechnungen müsstest du dafür mindestens Hey, du hast mich reingelegt. ### Folie 5 [Folie 5 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=5) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Konnte ich nicht widerstehen. ### Folie 6 [Folie 6 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=6) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Lass uns lieber ein konkretes Beispiel anschauen. ### Folie 7 [Folie 7 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=7) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(3) fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Gerne. ### Folie 8 — fact(2) [Folie 8 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=8) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(3) fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Im nächsten Beispiel werden wir sehen, wie der Stack bei der Berechnung einer Fakultät arbeitet. ### Folie 9 — fact(1) [Folie 9 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=9) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(2) fact(3) fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:12–02:50](https://www.youtube.com/watch?v=3oBz_CvekXE&t=132)** Schauen wir uns ein konkretes Beispiel an. ### Folie 10 — fact(2) [Folie 10 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=10) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(3) fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:50–02:58](https://www.youtube.com/watch?v=3oBz_CvekXE&t=170)** Die Berechnung der Fakultät. ### Folie 11 [Folie 11 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=11) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(3) fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:50–02:58](https://www.youtube.com/watch?v=3oBz_CvekXE&t=170)** Sie erinnern sich vielleicht an unser Video über Rekursion. ### Folie 12 [Folie 12 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=12) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(4) fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:50–02:58](https://www.youtube.com/watch?v=3oBz_CvekXE&t=170)** Der Code ist relativ überschaubar. ### Folie 13 [Folie 13 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=13) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` fact(5) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:50–02:58](https://www.youtube.com/watch?v=3oBz_CvekXE&t=170)** Eine Funktion fact. ### Folie 14 [Folie 14 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=14) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` main Call Stack #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 15 [Folie 15 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=15) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` printf(…) main Call Stack #### Transkript > Zuordnung unsicher: wenige gemeinsame Textmerkmale; anhand der benachbarten Folien eingeordnet. **[Video 02:58–03:29](https://www.youtube.com/watch?v=3oBz_CvekXE&t=178)** die für n gleich eins eine eins zurückgibt und ansonsten n mit fact von n minus eins multipliziert. ### Folie 16 [Folie 16 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=16) ```c int fact(int n) { if (n <= 1) return 1; else return n * fact(n-1); } int main(void) { printf("%i\n", fact(5)); } ``` main Call Stack #### Transkript *Kein Transkriptabschnitt eindeutig dieser Folie zugeordnet. Möglicherweise eine Aufbau-/Grafikfolie oder eine Abweichung zwischen PDF und Video.* ### Folie 17 — Der Call Stack speichert [Folie 17 als PDF](https://inf.zone/download/lectures/4-memory/4.5-call-stack.pdf#page=17) Nur der oberste Frame Frames für jede aktive Funktion im Programm. auf dem Stack ist zu einem Zeitpunkt aktiv. Jeder Frame enthält den kompletten Zustand einer Frames werden beim Funktionsaufruf gepusht Funktionsausführung. und bei return gepoppt. Der Stack wächst von Ein rekursiver Aufruf erzeugt mehrere Frames hohen zu niedrigen Speicheradressen. derselben Funktion. > Bildinhalte sind nicht transkribiert; siehe Originalfolie. #### Transkript **[Video 02:58–03:29](https://www.youtube.com/watch?v=3oBz_CvekXE&t=178)** Zu Beginn haben wir nur den Frame der main-Funktion auf dem Stack, wie Sie in der Visualisierung sehen können. main wird als erstes ausgeführt und ist damit der erste Frame auf unserem Stack. Ja, vielleicht noch ein wichtiger Hinweis zur Visualisierung: Der Stack wächst in der Realität von höheren zu niedrigeren Speicheradressen. Die höheren Adressen sind im Bild aber natürlich unten, die niedrigeren oben. Genau. Das bedeutet, jeder neue Frame wird tatsächlich bei einer niedrigeren Speicheradresse angelegt als der vorherige. **[Video 03:29–04:01](https://www.youtube.com/watch?v=3oBz_CvekXE&t=209)** Lassen Sie uns Schritt für Schritt verfolgen, was als nächstes passiert. Der erste Schritt in unserer main-Funktion ist der Aufruf von printf. printf benötigt allerdings einen Wert als Argument, den es ausgeben soll. Dieser Wert soll durch den Aufruf von fact fünf berechnet werden. Das bedeutet, printf kann seine Arbeit noch nicht beenden, da es erst auf das Ergebnis von fact warten muss. Anders gesagt: Erst müssen alle Argumente ausgewertet sein und dann können wir in die Funktion erst reinspringen. Dann schauen wir uns an, wie fact fünf auf den Stack kommt. Jetzt wird fact fünf aufgerufen. Ein neuer Frame wird auf den Stack gelegt. **[Video 04:01–04:23](https://www.youtube.com/watch?v=3oBz_CvekXE&t=241)** In diesem Frame wird n den Wert fünf haben. Als erstes wird in der Funktion geprüft, ob n gleich eins ist. Da fünf nicht gleich eins ist, geht es in den else-Zweig. Dort sehen wir, dass wir n also fünf mit fact von n minus eins also fact von vier multiplizieren müssen. Das bedeutet aber, dass unser aktueller fact fünf Frame auch noch nicht fertig werden kann. Er muss erst auf das Ergebnis von fact vier warten. **[Video 04:23–04:55](https://www.youtube.com/watch?v=3oBz_CvekXE&t=263)** Ein weiterer Frame wird oben ins Stack gelegt, diesmal für fact vier. Sie sehen das Muster: Jeder neue Frame kommt mit einer niedrigeren Speicheradresse oben drauf. Wieder durchlaufen wir die gleiche Logik: Ist n gleich eins? Nein, vier ist nicht eins, also müssen wir wieder in den else-Zweig und fact von n minus eins aufrufen. Diesmal also fact von drei. Das rekursive Muster wird hier sehr deutlich. Jeder Frame wartet auf das Ergebnis des nächsten fact-Aufrufs, der einen neuen Frame erzeugt. Die Frames sammeln sich auf dem Stack an, bis wir endlich einen Fall erreichen, der sofort zurückgeben kann, wenn n dann eben gleich eins ist. **[Video 04:55–05:25](https://www.youtube.com/watch?v=3oBz_CvekXE&t=295)** Der Prozess setzt sich fort. fact drei wird auf den Stack gelegt, wieder wird geprüft: Ist n gleich eins? Nein, also brauchen wir fact zwei. Beachten Sie, wie sich der Stack immer weiter aufbaut. Jeder Frame enthält dabei seinen eigenen Wert von n und wartet darauf, diesen mit dem Ergebnis der nächsten fact-Berechnung zu multiplizieren. Im Speicher bewegen wir uns mit jedem Frame zu immer niedrigeren Adressen. Der Speicher, den der Stack belegt, wird dabei immer größer. Was übrigens auch erklärt, warum eine zu tiefe Rekursion zum gefürchteten Stack Overflow führen kann, oder? **[Video 05:25–05:58](https://www.youtube.com/watch?v=3oBz_CvekXE&t=325)** Irgendwann ist der Speicherbereich, den das Programm für den Stack vom Betriebssystem zugeteilt bekommen hat, halt einfach erschöpft. Jetzt kommt fact zwei auf den Stack. Sie ahnen es bereits. Auch hier ist n noch nicht eins, also wird noch ein weiterer Aufruf nötig sein. Was besonders interessant ist, obwohl es sich immer um die gleiche Funktion fact handelt, existieren mehrere unabhängige Frames dieser Funktion gleichzeitig auf dem Stack. Jeder mit seinem eigenen Kontext. Das ist übrigens auch der Grund, warum rekursive Funktionen oft mehr Speicher brauchen als ihre iterativen Gegenstücke. Die ganzen Zwischenwerte, die müssen ja auch die ganze Zeit im Speicher stehen, auf dem Stack. **[Video 05:58–06:34](https://www.youtube.com/watch?v=3oBz_CvekXE&t=358)** Bis die Rekursion irgendwann endlich den Basisfall erreicht. Endlich erreichen wir fact 1. Hier haben wir den Basisfall unserer Rekursion erreicht. Die Bedingung n gleich gleich 1 ist zum ersten Mal erfüllt. Mit diesem Aufruf erreicht unser Stack seine maximale Tiefe für diese Berechnung. Jetzt beginnt der interessante Teil. Das Auflösen des Stacks. Da wir bei n gleich 1 angekommen sind, können wir direkt den Wert 1 zurückgeben. Damit kann der erste Frame seine Arbeit beenden und wird vom Stack entfernt werden. Nach dem Zurückgeben der 1 wird der Frame von fact 1 vom Stack entfernt. Nun wird fact 2 wieder zum aktiven Frame. Dieser Frame hat noch die Information gespeichert, dass n gleich 2 ist. **[Video 06:34–07:08](https://www.youtube.com/watch?v=3oBz_CvekXE&t=394)** und kann jetzt endlich die Multiplikation zwei mal eins durchführen. Dies ist der Beginn der Kettenreaktion, die alle unsere wartenden Berechnungen auflösen wird. fact zwei wird zwei zurückgeben. Mit diesem Wert kann fact drei dann drei mal zwei berechnen. fact vier wird vier mal sechs berechnen und fact fünf wird schließlich fünf mal vierundzwanzig berechnen, was uns zum Endergebnis hundertzwanzig führt. Der letzte fact-Frame wird vom Stack entfernt. printf erhält nun endlich den Wert hundertzwanzig, den es ausgeben kann. printf beendet seine Arbeit, nachdem es den Wert ausgegeben hat. Der printf-Frame wird vom Stack entfernt und wir kehren zum main-Frame zurück. **[Video 07:08–07:27](https://www.youtube.com/watch?v=3oBz_CvekXE&t=428)** Damit ist unsere Berechnung vollständig abgeschlossen und wir haben gesehen, wie der Stack das Management der rekursiven Aufrufe ermöglicht hat. Damit sind wir für heute fertig. Wir haben gesehen, wie der Call Stack die Magie der Rekursion möglich macht. Jeder Frame bewahrt seinen Zustand, bis er seine Berechnung abschließen kann. Moment mal, keine drei extra Minuten heute? **[Video 07:27–07:56](https://www.youtube.com/watch?v=3oBz_CvekXE&t=447)** Nein, ausnahmsweise nicht. Ich dachte mir, nach all den Frames, die wir gestapelt haben, könnten unsere Studierenden eine Pause vertragen. Oh, wie rücksichtsvoll von ihr. Tja, selbst ich lerne dazu. Auch wenn ich zugeben muss, dass ich noch mindestens drei weitere interessante Aspekte des Call Stacks. Danke an alle fürs Zuhören. Wir sehen uns dann beim nächsten Mal. Bis bald. Aber ich wollte. Dies war Inf-Einf-B.