0Pricing
Coding Interview Prep · Lektion

Anker- und rekursive Elemente

Die zweiteilige Struktur einer rekursiven CTE und die Funktionsweise ihrer Beendigung

Anker- und rekursive Elemente ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Warum rekursive CTEs vorkommen

Wenn ein Interviewer Ihnen ein Organigramm, eine Stückliste oder einen Kategorienbaum vorlegt und nach allen Nachfahren fragt, prüft er, ob Sie zu einer rekursiven CTE greifen. Einfache Joins können nur eine feste Anzahl von Ebenen durchlaufen; Rekursion kann eine beliebige Tiefe durchlaufen.

Die entscheidende Formulierung in einer Frage lautet "bis zu beliebiger Tiefe" oder "ganz nach unten". Das ist Ihr Signal. In dieser Lektion lernen Sie die zweiteilige Struktur kennen, die jede rekursive CTE gemeinsam hat: den Ankerteil und den rekursiven Teil.

Das zweiteilige Grundgerüst

Eine rekursive CTE enthält immer das Schlüsselwort WITH RECURSIVE (Postgres, SQLite, MySQL 8+; SQL Server lässt RECURSIVE weg) und einen aus zwei Abfragen bestehenden Rumpf, die mit UNION ALL verbunden werden:

  • Ankerteil — die Startzeilen, wird einmal ausgeführt.
  • Rekursiver Teil — verweist auf den Namen der CTE selbst, wird wiederholt ausgeführt.

Merken Sie sich dieses Grundgerüst; Interviewer lassen Sie es gern aus dem Kopf schreiben.

WITH RECURSIVE cte AS (
    -- anchor member
    SELECT ...
    UNION ALL
    -- recursive member
    SELECT ... FROM cte JOIN ...
)
SELECT * FROM cte;

Was der Ankerteil macht

Der Ankerteil ist eine gewöhnliche Abfrage ohne Verweis auf die CTE. Er erzeugt die Startzeilen — den Ausgangspunkt auf Ebene null. Bei einem Organigramm ist das normalerweise der CEO (die Zeile, deren Vorgesetzter NULL ist); bei einer Zahlenreihe ist es die erste Zahl.

Der Ankerteil wird genau einmal ausgeführt. Seine Ausgabe wird als erster Zeilenblock in den rekursiven Schritt eingespeist.

-- Anchor: the top of the hierarchy
SELECT id, name, manager_id, 1 AS depth
FROM employees
WHERE manager_id IS NULL

Was der rekursive Teil macht

Der rekursive Teil verweist über seinen Namen auf die CTE. Bei jeder Iteration verknüpft er die in der vorherigen Iteration erzeugten Zeilen mit der Basistabelle, um die nächste Ebene zu finden.

Er sieht nicht die gesamte bisher aufgebaute CTE — sondern nur die Zeilen, die im unmittelbar vorherigen Schritt hinzugekommen sind. Das ist das entscheidende mentale Modell, das Interviewer prüfen.

-- Recursive: children of the rows found so far
SELECT e.id, e.name, e.manager_id, c.depth + 1
FROM employees e
JOIN cte c ON e.manager_id = c.id

Alles zusammenführen

Kombinieren Sie den Ankerteil und den rekursiven Teil mit UNION ALL, und die Engine führt die Iterationen automatisch aus. Jeder Durchlauf hängt die nächste Ebene an, bis der rekursive Teil keine Zeilen zurückgibt; dann endet die Rekursion.

Hier sehen Sie einen vollständigen, ausführbaren Durchlauf durch ein Organigramm, der außerdem depth erfasst.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1
    FROM employees e
    JOIN org o ON e.manager_id = o.id
)
SELECT id, name, depth FROM org ORDER BY depth, id;

So funktioniert die Beendigung

Die Rekursion endet, sobald der rekursive Teil keine neuen Zeilen erzeugt. Ein expliziter Schleifenzähler ist nicht erforderlich — der Join läuft ganz natürlich leer, sobald Sie die Blätter des Baums erreicht haben.

Im Beispiel mit dem Organigramm findet der Join der nächsten Iteration keine Kinder mehr, sobald Sie Mitarbeiter ohne direkte Unterstellte erreichen. Er liefert ein leeres Ergebnis, und die Engine hält an. Dieses selbstbeendende Verhalten zu verstehen, ist eine typische Rückfrage im Interview.

UNION ALL vs. UNION

Interviewer fragen häufig, warum wir UNION ALL und nicht UNION verwenden. Dafür gibt es zwei Gründe:

  • Leistung — UNION entfernt in jeder Iteration Duplikate, was teuer ist.
  • Korrektheit — in einem Baum können doppelte Zeilen normalerweise nicht vorkommen, daher ist die Duplikatbereinigung überflüssige Arbeit.

Verwenden Sie UNION nur, wenn es sich um einen Graphen handelt und Sie wiederholte Knoten bewusst zusammenfassen möchten — für die Sicherheit vor Zyklen sind explizite Prüfungen jedoch besser (mehr dazu später).

Tiefe und Pfad erfassen

Zwei zusätzliche Spalten machen rekursive Ergebnisse deutlich nützlicher und werden in Interviews häufig verlangt:

  • depth — beginnen Sie im Anker bei 1 und addieren Sie im rekursiven Teil 1.
  • path — sammeln Sie die Kette aus IDs oder Namen, damit Sie den Weg von der Wurzel zum Knoten sehen können.

Wenn Sie path als Zeichenkette aufbauen, dient es später zugleich als Werkzeug zur Zykluserkennung.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id, 1 AS depth,
           CAST(name AS VARCHAR(1000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, o.depth + 1,
           o.path || ' > ' || e.name
    FROM employees e JOIN org o ON e.manager_id = o.id
)
SELECT name, depth, path FROM org;

Spaltentypen müssen übereinstimmen

Ein leicht zu übersehender Stolperstein: Der Ankerteil und der rekursive Teil müssen die gleiche Anzahl von Spalten mit kompatiblen Typen zurückgeben. Wenn Sie eine path-Zeichenkette aufbauen, muss der Anfangswert des Ankerteils breit genug gecastet werden, beispielsweise als VARCHAR(1000); andernfalls kann die Engine spätere Iterationen abschneiden oder einen Fehler wegen nicht übereinstimmender Typen auslösen.

Genau auf solche Details achten Interviewer, um zu erkennen, ob Sie eine rekursive CTE tatsächlich ausgeführt haben, statt nur darüber gelesen zu haben.

Beispiel für eine Stückliste

Dasselbe Grundgerüst löst auch das Problem einer Stückliste: Für ein Bauteil sollen alle Unterbauteile in beliebiger Tiefe aufgelistet werden. Der Ankerteil wählt die oberste Baugruppe aus; der rekursive Teil folgt den Verknüpfungen von parent_part zu child_part.

Beachten Sie, dass die Struktur mit dem Organigramm identisch ist — nur die Spaltennamen ändern sich. Zu erkennen, dass ein Grundgerüst zu vielen Problemen passt, ist die eigentliche Fähigkeit, die im Interview zählt.

WITH RECURSIVE bom AS (
    SELECT child_part, parent_part, 1 AS lvl
    FROM parts WHERE parent_part = 'ENGINE'
    UNION ALL
    SELECT p.child_part, p.parent_part, b.lvl + 1
    FROM parts p JOIN bom b ON p.parent_part = b.child_part
)
SELECT child_part, lvl FROM bom;

Hinweise zu SQL-Dialekten

Ein kurzes Merkblatt zu den verschiedenen Dialekten, das Interviewer zu schätzen wissen:

  • PostgreSQL, SQLite, MySQL 8+: WITH RECURSIVE name AS (...).
  • SQL Server: einfach WITH name AS (...) — das Schlüsselwort RECURSIVE ist implizit enthalten, und standardmäßig gilt MAXRECURSION 100.
  • Oracle: unterstützt sowohl rekursive CTEs als auch die ältere Syntax CONNECT BY.

Zu sagen, dass „SQL Server das Wort RECURSIVE nicht verwendet“, zeigt echte Bandbreite.

Kurzer Test

Testen Sie Ihr Verständnis des zweiteiligen Aufbaus.

Rückblick

Sie beherrschen jetzt das Grundgerüst für rekursive CTEs:

  • WITH RECURSIVE + Ankerteil + UNION ALL + rekursiver Teil.
  • Der Ankerteil legt Ebene null an und wird einmal ausgeführt.
  • Der rekursive Teil verknüpft die vorherige Iteration mit der Basistabelle und läuft, bis er keine Zeilen mehr zurückgibt.
  • Verwenden Sie UNION ALL, erfassen Sie depth und path und achten Sie auf kompatible Spaltentypen.

Als Nächstes wenden Sie dieses Grundgerüst auf das Durchlaufen eines echten Organigramms nach unten und oben an.

Häufig gestellte Fragen

Ist die Lektion „Anker- und rekursive Elemente“ kostenlos?

Ja — der vollständige Text von „Anker- und rekursive Elemente“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Anker- und rekursive Elemente“?

Die zweiteilige Struktur einer rekursiven CTE und die Funktionsweise ihrer Beendigung Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Coding Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Anker- und rekursive Elemente“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Anker- und rekursive Elemente
  2. Ein Organigramm durchlaufen
  3. Zahlen- und Datumsreihen erzeugen
  4. Unendliche Rekursion vermeiden
← Zurück zu Coding Interview Prep