Förberedelse inför kodningsintervjuer · Lektion

Ankare och rekursiva delar

Den tvådelade strukturen hos en rekursiv CTE och hur avslutningen fungerar

Lektion 1 av 413 steg

Ankare och rekursiva delar är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Varför rekursiva CTE:er dyker upp

När en intervjuare ger Er ett organisationsschema, en stycklista eller ett kategoriträd och ber Er hitta alla efterkommande noder, testar de om Ni väljer en rekursiv CTE. Vanliga JOIN-operationer kan bara gå igenom ett förutbestämt antal nivåer, medan rekursion kan gå igenom ett godtyckligt djup.

Den avslöjande formuleringen i en fråga är "på valfritt djup" eller "hela vägen ned". Det är Er signal. I den här lektionen lär Ni Er den struktur i två delar som alla rekursiva CTE:er har gemensamt: ankardelen och den rekursiva delen.

Strukturen i två delar

En rekursiv CTE innehåller alltid nyckelordet WITH RECURSIVE (Postgres, SQLite, MySQL 8+; SQL Server utelämnar RECURSIVE) och en kropp som består av två frågor kombinerade med UNION ALL:

Ankardelen — startraderna, körs en gång.
Den rekursiva delen — refererar till själva CTE-namnet och körs upprepade gånger.

Lär Er denna struktur utantill; intervjuare älskar att be Er skriva den från grunden.

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

Vad ankardelen gör

Ankardelen är en vanlig fråga utan någon referens till CTE:n. Den producerar startraderna — utgångspunkten på nivå noll. För ett organisationsschema är det vanligtvis VD:n (raden vars chef är NULL); för en talserie är det det första talet.

Ankardelen körs exakt en gång. Dess resultat blir den första gruppen rader som matas in i det rekursiva steget.

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

Vad den rekursiva delen gör

Den rekursiva delen refererar till CTE:n med namn. Vid varje iteration kopplar den ihop raderna från den föregående iterationen med bastabellen för att hitta nästa nivå nedåt.

Den ser inte hela CTE:n hittills — bara raderna som lades till i det omedelbart föregående steget. Det här är den centrala mentala modellen som intervjuare brukar undersöka.

-- 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

Sätt ihop delarna

Kombinera ankardelen och den rekursiva delen med UNION ALL, så itererar motorn automatiskt. Varje körning lägger till nästa nivå tills den rekursiva delen returnerar noll rader, varpå rekursionen avslutas.

Här är en komplett, körbar genomgång av ett organisationsschema som även spårar depth.

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;

Så fungerar avslutningen

Rekursionen avslutas när den rekursiva delen inte producerar några nya rader. Ingen uttrycklig loopräknare behövs — JOIN-operationen tar naturligt slut när lövnoderna i trädet nås.

I organisationsschemat hittar nästa iterations JOIN inga barn när Ni når medarbetare utan direktrapporterande. Den returnerar ett tomt resultat, och motorn stannar. Att förstå detta självavslutande beteende är en klassisk följdfråga.

UNION ALL jämfört med UNION

Intervjuare frågar ofta varför vi använder UNION ALL i stället för UNION. Det finns två skäl:

Prestanda — UNION tar bort dubbletter vid varje iteration, vilket är kostsamt.
Korrekthet — i ett träd kan dubblettrader vanligtvis inte uppstå, så dedupliceringen är onödigt arbete.

Använd UNION endast när strukturen är en graf och Ni medvetet vill slå ihop upprepade noder — men för skydd mot cykler är uttryckliga kontroller bättre (det tas upp senare).

Spåra djup och sökväg

Två extra kolumner gör resultat från rekursionen mycket mer användbara och efterfrågas ofta i intervjuer:

depth — börja på 1 i ankardelen och lägg till 1 i den rekursiva delen.
path — samla kedjan av id:n eller namn så att Ni kan se vägen från roten till noden.

Att bygga path som en sträng fungerar dessutom senare som ett verktyg för cykeldetektering.

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;

Kolumntyperna måste stämma överens

En subtil fallgrop: ankardelen och den rekursiva delen måste returnera samma antal kolumner med kompatibla typer. Om Ni bygger en path-sträng måste ankardelens ursprungliga värde typkonverteras till en tillräckligt bred typ (till exempel VARCHAR(1000)), annars kan motorn trunkera värdet eller utlösa ett typkonverteringsfel vid senare iterationer.

Det här är precis den typ av detalj som en intervjuare lägger in för att se om Ni faktiskt har kört en rekursiv CTE och inte bara läst om en.

Exempel med stycklista

Samma struktur löser en stycklista: givet en del, lista alla underdelar på valfritt djup. Ankardelen väljer toppmonteringen, och den rekursiva delen följer länkarna från parent_part till child_part.

Lägg märke till att strukturen är identisk med organisationsschemat — bara kolumnnamnen ändras. Den verkliga intervjufärdigheten är att känna igen att samma struktur passar många problem.

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;

Anteckningar om SQL-dialekter

En snabb fusklapp för olika dialekter som intervjuare uppskattar:

PostgreSQL, SQLite, MySQL 8+: WITH RECURSIVE name AS (...).
SQL Server: endast WITH name AS (...) — nyckelordet RECURSIVE är implicit, och SQL Server tillämpar ett standardvärde för MAXRECURSION på 100.
Oracle: har stöd för både rekursiva CTE:er och den äldre syntaxen CONNECT BY.

Att säga "SQL Server använder inte ordet RECURSIVE" visar verklig bredd.

Snabbtest

Testa hur väl Ni behärskar strukturen i två delar.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Nu behärskar Ni strukturen för rekursiva CTE:er:

WITH RECURSIVE + ankardel + UNION ALL + rekursiv del.
Ankardelen initierar nivå noll och körs en gång.
Den rekursiva delen kopplar föregående iteration till bastabellen och körs tills den returnerar inga rader.
Använd UNION ALL, spåra depth och path, och se till att kolumntyperna är kompatibla.

Nästa steg: använd denna struktur för att gå igenom ett verkligt organisationsschema uppåt och nedåt.

Gratis att börja

Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 90
Lektioner: 360

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Ankare och rekursiva delar” gratis?

Ja – hela texten till ”Ankare och rekursiva delar” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.

Vad lär jag mig i ”Ankare och rekursiva delar”?

Den tvådelade strukturen hos en rekursiv CTE och hur avslutningen fungerar Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?

Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.

Hur lång tid tar lektionen ”Ankare och rekursiva delar”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?

Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Förberedelse inför kodningsintervjuer