WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / Java

Rekursion und Aufrufstack

Rekursion und Aufrufstack: Rekursion entsteht, wenn eine Methode sich direkt oder indirekt aufruft; jeder Aufruf besitzt einen Stack-Frame, daher braucht der Algorithmus Basisfall und Fortschritt.

Version: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime

Syntax

recursion

Rekursion entsteht, wenn eine Methode sich direkt oder indirekt aufruft; jeder Aufruf besitzt einen Stack-Frame, daher braucht der Algorithmus Basisfall und Fortschritt.

Nutze sie für begrenzte Bäume und Teile-und-herrsche; ersetze eine tiefe lineare Traversierung durch Iteration mit Deque.

Java garantiert keine Endrekursionsoptimierung, sodass korrekte, aber tiefe Rekursion mit StackOverflowError enden kann.

Leere Eingaben müssen den Basisfall erreichen; ein zyklischer Graph benötigt eine visited-Menge, sonst endet die Rekursion nicht.

Zwei Basisfälle beenden die Aufrufe: factorial(5) gibt 120 aus, der rekursive euklidische gcd(48,18) gibt 6 aus.

Beispiele

public class Main {
    static int factorial(int n) {
        return n <= 1 ? 1 : n * factorial(n - 1);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(gcd(48, 18));
    }
}

Ergebnis

120
6

Zwei Basisfälle beenden die Aufrufe: factorial(5) gibt 120 aus, der rekursive euklidische gcd(48,18) gibt 6 aus.

Quellen