NPS3E3: Ackermann-Funktion - Warum Rekursion schnell an ihre Grenzen kommt

In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Die Ackermann-Funktion ist ein kleines, aber berühmtes Beispiel aus der theoretischen Informatik. Sie sieht harmlos aus, wächst aber extrem schnell und zwingt Programme sehr früh in tiefe Rekursion.

Warum ist sie so bekannt? Weil sie zeigt, dass es Funktionen gibt, die zwar klar definiert sind, aber für normale Rechner und normale Datentypen sehr schnell unpraktisch werden.

In diesem Artikel lernst du, wie die Ackermann-Funktion definiert ist, warum sie so schnell eskaliert und wie du sie in Java umsetzt. Dabei nutzen wir sie als Übung, um Abbruchbedingungen, Rekursionstiefe und Grenzen von int, long und dem Call-Stack zu verstehen.

Problemstellung

Implementiere die Ackermann-Funktion A(m, n) für nichtnegative ganze Zahlen m und n. Die Definition ist rekursiv:

• Wenn m == 0, dann A(m, n) = n + 1
• Wenn m > 0 und n == 0, dann A(m, n) = A(m - 1, 1)
• Wenn m > 0 und n > 0, dann A(m, n) = A(m - 1, A(m, n - 1))

Constraints (praktisch für unsere Java-Demos):

• Nur kleine Eingaben, z.B. m bis 3 und n bis 10 (oft deutlich weniger).
• Es gibt sehr schnell StackOverflowError durch tiefe Rekursion.
• Die Ergebnisse wachsen so schnell, dass int und long früh überlaufen können.

Mini-Beispiel (klein und nachvollziehbar):

1. A(0, 3) = 4 (weil n + 1)
2. A(1, 2) = A(0, A(1, 1))
3. A(1, 1) = A(0, A(1, 0))
4. A(1, 0) = A(0, 1) = 2
5. Damit A(1, 1) = A(0, 2) = 3 und A(1, 2) = A(0, 3) = 4

Die Idee dahinter

Das Kernkonzept hier ist tiefe Rekursion und damit verbundene theoretische Grenzen. Die Ackermann-Funktion ist absichtlich so gebaut, dass sie sich verschachtelt selbst aufruft: Ein Rekursionsaufruf erzeugt den Parameter für den nächsten Rekursionsaufruf.

Das macht zwei Dinge deutlich:

• Die Anzahl der Aufrufe wächst extrem schnell, selbst bei kleinen Eingaben.
• Der Call-Stack wird sehr tief, bis Java mit StackOverflowError abbricht.

Kurze Visualisierung, wie sich Aufrufe stapeln können:

• A(3, 2) braucht A(3, 1)
• A(3, 1) braucht A(3, 0)
• A(3, 0) wird zu A(2, 1)
• und so weiter, aber mit immer mehr Verschachtelung durch A(m - 1, A(m, n - 1))

Schritt für Schritt zur Lösung

1. Signatur festlegen: Wir starten mit long ackermann(int m, long n), weil int schnell überläuft.
2. Eingaben prüfen: m und n müssen nichtnegativ sein, sonst ist die Definition hier nicht gemeint.
3. Abbruchbedingung 1: Wenn m == 0, gib n + 1 zurück. Das ist der wichtigste Stopp.
4. Abbruchbedingung 2: Wenn n == 0 und m > 0, rufe A(m - 1, 1) auf.
5. Rekursiver Fall: Sonst (also m > 0 und n > 0) berechne erst A(m, n - 1), dann nutze das Ergebnis als Parameter für A(m - 1, ...).
6. Nur kleine Demos: Baue in main kleine Beispiele ein und gib die Ergebnisse mit System.out.println aus.

Java-Implementierung (Variante A: straightforward)

public class AckermannStraightforward {

  public static void main(String[] args) {
    System.out.println("A(0, 3) = " + ackermann(0, 3));
    System.out.println("A(1, 2) = " + ackermann(1, 2));
    System.out.println("A(2, 2) = " + ackermann(2, 2));
    System.out.println("A(3, 4) = " + ackermann(3, 4));
  }

  public static long ackermann(int m, long n) {
    if (m < 0 || n < 0) {
      throw new IllegalArgumentException("m and n must be non-negative");
    }

    if (m == 0) {
      return n + 1;
    }

    if (n == 0) {
      return ackermann(m - 1, 1);
    }

    return ackermann(m - 1, ackermann(m, n - 1));
  }
}

Das ist die Definition fast 1:1 in Java. Die Abbruchbedingung m == 0 ist klar sichtbar, und die zwei anderen Fälle folgen direkt daraus. Nachteil: Schon bei moderaten Werten bekommst du sehr viele Aufrufe und oft einen StackOverflowError.

Merke: Diese Variante ist gut zum Lernen und zum Verstehen, aber nicht zum Rechnen mit größeren Eingaben.

Java-Implementierung (Variante B: Alternative oder Verbesserung)

import java.util.ArrayDeque; 
import java.util.Deque;

public class AckermannIterative {

  public static void main(String[] args) {
    System.out.println("A(0, 3) = " + ackermannIterative(0, 3));
    System.out.println("A(1, 2) = " + ackermannIterative(1, 2));
    System.out.println("A(2, 2) = " + ackermannIterative(2, 2));
    System.out.println("A(3, 4) = " + ackermannIterative(3, 4));

    // Vorsicht: Auch iterativ kann es sehr lange dauern oder riesige Werte erzeugen.
    // System.out.println("A(3, 10) = " + ackermannIterative(3, 10));
  }

  public static long ackermannIterative(int m, long n) {
    if (m < 0 || n < 0) {
      throw new IllegalArgumentException("m and n must be non-negative");
    }

    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(m);

    long currentN = n;

    while (!stack.isEmpty()) {
      int currentM = stack.pop();

      if (currentM == 0) {
        currentN = currentN + 1;
        continue;
      }

      if (currentN == 0) {
        stack.push(currentM - 1);
        currentN = 1;
        continue;
      }

      // A(m, n) = A(m - 1, A(m, n - 1))
      // Wir "verschieben" die Arbeit auf den Stack:
      // erst A(m, n - 1), dann A(m - 1, Ergebnis)
      stack.push(currentM - 1);
      stack.push(currentM);
      currentN = currentN - 1;
    }

    return currentN;
  }
}

Hier ersetzen wir die System-Rekursion durch einen eigenen Stack (ArrayDeque). Das verhindert in vielen Fällen den StackOverflowError, weil nicht mehr der Java-Call-Stack tief wird, sondern unsere Datenstruktur.

Wichtig: Das löst nicht das eigentliche Wachstumsproblem. Die Laufzeit wächst weiterhin extrem schnell, und die Werte können long trotzdem sprengen.

Beispiel: Eingabe und Ausgabe

Diese Beispiele sind absichtlich klein:

• Eingabe m=0, n=3 Output 4
• Eingabe m=1, n=2 Output 4
• Eingabe m=2, n=2 Output 7

Noch ein Beispiel, das schon zeigt, wie schnell es größer wird:

• Eingabe m=3, n=4 Output 125

Typische Fehler

• Falsche Abbruchbedingung: m == 0 muss zuerst sauber behandelt werden, sonst läuft die Rekursion unkontrolliert weiter.
• Negative Eingaben ignorieren: Ohne Check kann es zu endloser Rekursion oder unlogischen Ergebnissen kommen. Nutze z.B. IllegalArgumentException.
• Parameter vertauscht: Aus A(m - 1, A(m, n - 1)) wird schnell versehentlich A(m, A(m - 1, n - 1)) oder ähnlicher Unsinn.
• Überlauf bei Datentypen: Selbst long reicht nur für kleine Werte. Wenn das Ergebnis plötzlich negativ wird, ist das ein Hinweis auf Overflow.
• Zu große Testwerte: A(4, 1) oder größer ist oft schon eine schlechte Idee für eine Demo. Es kann sehr lange laufen oder direkt abbrechen.
• StackOverflowError falsch interpretiert: Das ist kein "Java ist kaputt", sondern ein Zeichen, dass deine Rekursionstiefe zu groß wurde.
• Iterativ = schnell denken: Die iterative Variante spart Call-Stack, aber nicht die explodierende Anzahl an Schritten.

Fazit

Mit der Ackermann-Funktion lernst du, warum Rekursion nicht nur eine Syntaxfrage ist, sondern echte Grenzen hat. Du hast gesehen, wie wichtig klare Abbruchbedingungen sind und warum tiefe Rekursion in Java schnell zum StackOverflowError führt. Du hast ausserdem eine Alternative kennengelernt: eine iterative Simulation mit eigenem Stack. Das ist ein guter Trick, wenn man Rekursion technisch vermeiden will, auch wenn die Funktion selbst trotzdem sehr schnell unpraktisch wird.