Rekursion

Bei der Rekursion (englisch recursion) ruft sich eine Methode selbst auf. Jeder rekursive Algorithmus braucht zwei Teile:

• den Basisfall (englisch base case), in dem ohne weiteren Aufruf ein Ergebnis feststeht, und
• den Rekursionsschritt (englisch recursive case), der das Problem verkleinert und sich selbst aufruft.

int fakultaet(int pN) {
    if (pN <= 1) {          // Basisfall
        return 1;
    }
    return pN * fakultaet(pN - 1);   // Rekursionsschritt
}

Jeder noch nicht zurückgekehrte Aufruf belegt einen Kellerrahmen. Fehlt der Basisfall oder wird er nie erreicht, läuft der Kellerstapel voll – es gibt einen Stapelüberlauf.