Deutsch
Menü

Was ist Rekursion?

Aufruf einer Funktion durch sich selbst als Teil ihrer eigenen Verarbeitung. Das Problem wird in kleinere Probleme derselben Form zerlegt, und die Aufrufe enden bei einem Fall, der nicht weiter zerlegt wird (dem Basisfall). Jeder Aufruf belegt Stack-Speicher, daher läuft der Stack bei zu tiefer Rekursion über. Endrekursion, bei der der rekursive Aufruf das Letzte ist, was die Funktion tut, lässt sich in eine Schleife umwandeln.

Japanische Bezeichnung: 再帰

„Rekursion“ kommt in 10 Übungsfragen aus 7 Themen vor, z. B. Linker, Loader und ausführbare Formate, Datenstrukturen und Algorithmen, CPU und Architektur.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Rekursion

Was geschieht unter Linux u. a. im Allgemeinen, wenn eine zu tiefe Rekursion die Obergrenze des Stacks überschreitet?

  1. ADas Programm berührt die hinter dem Stack liegende, für Zugriffe gesperrte Guard Page und wird abnormal beendet
  2. BDas Betriebssystem lagert den Stack automatisch auf die Festplatte aus, sodass beliebig tief rekursiert werden kann
  3. CAlte Stack-Frames werden automatisch gelöscht, und die Berechnung wird korrekt fortgesetzt
Antwort und Erläuterung anzeigen

Antwort: A. Das Programm berührt die hinter dem Stack liegende, für Zugriffe gesperrte Guard Page und wird abnormal beendet

Der Stack hat eine Obergrenze, hinter der eine für Zugriffe gesperrte Guard Page liegt. Erreicht der Stack bei zu tiefer Rekursion diese, tritt ein Seitenfehler auf, und das Betriebssystem beendet das Programm (Segmentation Fault). Der Vorteil der Guard Page ist, dass das Programm gestoppt werden kann, bevor andere Daten zerstört werden. Dasselbe passiert bei großen Arrays als lokalen Variablen; große Daten legt man daher sicherer auf dem Heap ab.

„Rekursion“ in den Erläuterungen

Fragen mit „Rekursion“ (10)

  1. Was geschieht unter Linux u. a. im Allgemeinen, wenn eine zu tiefe Rekursion die Obergrenze des Stacks überschreitet?
  2. Welcher Bereich wird beim Aufruf einer Subroutine (Funktion) üblicherweise genutzt, um Rücksprungadresse usw. vorübergehend zu sichern?
  3. Welche Wirkung hat es, wenn auf den letzten rekursiven Aufruf der obigen Funktion die Tail-Call-Optimierung angewendet wird?
  4. Wo liegt während der Ausführung eine in einer C-Funktion deklarierte lokale Variable ohne static (automatische Variable)?
  5. Welcher Vorteil ergibt sich daraus, Heap und Stack eines Prozesses mit einem großen freien Bereich dazwischen in entgegengesetzte Richtungen wachsen zu lassen?
  6. Was ist bei einem kleinen Mikrocontroller ohne MMU im Hinblick auf übermäßige Stack-Nutzung zu beachten?
  7. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  8. Eine Funktion f(x, y) ist definiert als „ist y gleich 0, gib x zurück; andernfalls gib f(y, x mod y) zurück“. Welchen Rückgabewert liefert der Aufruf f(84, 36), und wie oft wird f aufgerufen, den ersten Aufruf eingeschlossen?
  9. ÷ ist die Division; wird das Ergebnis einer ganzzahligen Variablen (auch einem Funktionsargument) zugewiesen, wird der Nachkommaanteil abgeschnitten. Wie oft wird pow einschließlich des ersten Aufrufs aufgerufen, wenn die folgende Funktion pow als pow(2, 10) aufgerufen wird?
  10. int habe 32 Bit (Maximalwert 2147483647). Was ist das größte n, für das die obige Funktion fact(n) die Fakultät von n ohne Überlauf korrekt zurückgibt?

Verwandte Begriffe

Stack (Stapelspeicher) Heap Stack-Frame Rückgabewert Seitenfehler (Page Fault) Rücksprungadresse Stackpointer Argument Variable Mikrocontroller

Zur Glossarübersicht