C/C++-Algorithmen

Rekursion und Aufrufstapel in C und C++

In dieser Lektion berechnest du die Fakultät mit einer rekursiven Funktion und lernst die Abbruchbedingung und den Speicherbedarf der Rekursion kennen.

Einführung

Rekursion ist die Technik, ein Problem zu lösen, indem man es auf ein kleineres Problem derselben Art zurückführt. Jede rekursive Funktion braucht eine Abbruchbedingung (base case), und jeder Aufruf muss ihr näherkommen, sonst ruft das Programm die Funktion endlos auf.

Wichtige Punkte

Teste mit leeren Eingaben, einem einzigen Element, doppelten Werten und bereits sortierten Daten.
Zuerst richtig machen, dann optimieren.
Bevorzuge in echtem Code die fertigen Funktionen der Standardbibliothek.

So funktioniert es

Klicke auf Schritt, um jedem Aufruf zu folgen. Neue Aufrufe landen auf dem Aufrufstapel, und jeder gibt seinen Wert an den Aufrufer zurück.

Codebeispiele in C und C++

Code ausführen →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Ergebnis der Ausführung

C++

Code ausführen →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Ergebnis der Ausführung

C und C++ im Vergleich

Die Funktion factorial gibt 1 zurück, wenn number kleiner als 2 ist, das ist die Abbruchbedingung, und sonst number * factorial(number - 1). Jeder Funktionsaufruf belegt zusätzlichen Platz auf dem Aufrufstapel (call stack), deshalb braucht der Algorithmus O(n) Zeit und O(n) Stapelspeicher. Die C++-Version markiert die Funktion als constexpr, sodass der Wert schon beim Kompilieren berechnet werden kann. Bei großen Eingaben solltest du die Eingabe prüfen und meist eine Schleife statt Rekursion verwenden.

Schleifen, Zeiger, Längen und Zwischenpuffer werden ausdrücklich ausgeschrieben.

C++

Iteratoren und Standardalgorithmen trennen die Verarbeitung von der Art, wie die Daten gespeichert sind.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

Spiele jeden Vergleich auf Papier durch.
Teste mit doppelten Werten und mit sehr großen und sehr kleinen Werten.
Miss die Laufzeit deines Codes und vergleiche sie mit der Standardbibliothek.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges