Förberedelse inför kodningsintervjuer · Lektion

Undvik oändlig rekursion

Cykeldetektering, djupbegränsningar och rekursionsskyddet som varje intervjuare kontrollerar

Lektion 4 av 413 steg

Undvik oändlig rekursion är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 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.

Frågan bakom frågan

När du har skrivit en rekursiv CTE frågar en skarp intervjuare: "Vad händer om data innehåller en cykel?" Det testar om du förstår att rekursion kan fortsätta för evigt — och om du vet hur du skyddar dig mot det.

En cykel uppstår när hierarkin går tillbaka till sig själv: A rapporterar till B och B rapporterar till A. Den naiva rekursiva medlemmen skulle växla mellan dem i all oändlighet.

Så uppstår en cykel

Träd ska vara acykliska, men verkliga data är ofta röriga. En felaktig uppdatering kan göra en anställd till sin egen (indirekta) chef. En graf — till exempel "användare som följer användare" — är cyklisk till sin natur.

När den rekursiva medlemmen träffar på en nod som redan har besökts skapas noden igen, vilket utlöser dess barn på nytt, och loopen töms aldrig. Rekursionen upphör endast när ett steg inte returnerar några rader; en cykel garanterar att det alltid returneras rader.

Skydd 1: En djupgräns

Det enklaste skyddet är en djupmätare med en gräns i den rekursiva medlemmen. Även om det finns en cykel stannar rekursionen vid gränsen.

Detta är ett trubbigt verktyg — det begränsar även legitimt djupa träd — men det är snabbt och passar bra i intervjuer.

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
    WHERE o.depth < 50
)
SELECT * FROM org;

Skydd 2: En sökväg med besökta noder

Ett exakt skydd håller reda på sökvägen med besökta noder och vägrar gå in i en nod som redan finns på sökvägen. Samla id:n i en sträng (eller array) och kontrollera om noden finns där innan du fortsätter rekursionen.

Detta stoppar cykler exakt och tillåter samtidigt godtyckligt djup i legitima träd.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id,
           CAST(',' || id || ',' AS VARCHAR(2000)) AS path
    FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id,
           o.path || e.id || ','
    FROM employees e JOIN org o ON e.manager_id = o.id
    WHERE o.path NOT LIKE '%,' || e.id || ',%'
)
SELECT id, name, path FROM org;

Därför fungerar sökvägskontrollen

Villkoret path NOT LIKE '%,' || e.id || ',%' betyder "följ bara denna kant om barnets id inte redan finns i sökvägen". Kommatecknen fungerar som avgränsare, så att id 1 inte felaktigt matchar inuti id 15.

Om en cykel skulle besöka en nod igen filtrerar WHERE bort raden, den rekursiva medlemmen returnerar till slut ingenting och rekursionen avslutas korrekt.

Skydd 3: Den inbyggda CYCLE-satsen

Moderna versioner av Postgres (14+) och SQL-standarden erbjuder en inbyggd CYCLE-sats som automatiserar sökvägskontrollen och markerar cykler åt dig. Det är det renaste svaret när databasmotorn stöder den.

WITH RECURSIVE org AS (
    SELECT id, name, manager_id FROM employees WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e JOIN org o ON e.manager_id = o.id
)
CYCLE id SET is_cycle USING cycle_path
SELECT id, name, is_cycle FROM org;

SQL Servers MAXRECURSION

SQL Server tillämpar som standard en gräns på 100 rekursionsnivåer. Om en cykel (eller ett djupt träd) överskrider den misslyckas frågan med ett fel i stället för att loopa för evigt — en inbyggd säkerhetsventil.

Du kan höja eller ta bort gränsen med OPTION (MAXRECURSION n), där 0 betyder obegränsat. Men om du tar bort gränsen utan ett sökvägsskydd återinför du risken för oändliga loopar i cykliska data.

-- Cap recursion at 200 levels in SQL Server
SELECT * FROM org
OPTION (MAXRECURSION 200);

Upptäcka eller förhindra cykler

Intervjuare kan skilja mellan två mål:

Förhindra — hoppa tyst över den cykliska kanten så att frågan slutförs (sökvägskontrollen i WHERE).
Upptäcka och rapportera — visa vilka rader som ingår i en cykel så att ett datateam kan korrigera de felaktiga uppgifterna (is_cycle-flaggan i CYCLE-satsen).

Att känna till båda metoderna och när de passar är en distinktion på seniornivå.

Prestandaöverväganden

Rekursion kan vara kostsam även utan cykler. Tips som intervjuare gärna hör:

Indexera join-kolumnen (till exempel manager_id) så att joinen i varje iteration går snabbt.
Filtrera tidigt i anchor-delen så att du bara initierar det delträd du behöver, inte hela tabellen.
Undvik SELECT * — ta bara med de kolumner som rekursionen kräver, plus depth/path.

En säker mall

Kombinera skydden i en mall som du kan återskapa under press: en djupkolumn som reservskydd och en sökvägskontroll som exakt skydd. Även om det ena skyddet är överflödigt för rena data signalerar det noggrannhet att visa båda.

WITH RECURSIVE walk AS (
    SELECT id, parent_id, 1 AS depth,
           CAST(',' || id || ',' AS VARCHAR(4000)) AS path
    FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT n.id, n.parent_id, w.depth + 1,
           w.path || n.id || ','
    FROM nodes n JOIN walk w ON n.parent_id = w.id
    WHERE w.depth < 100
      AND w.path NOT LIKE '%,' || n.id || ',%'
)
SELECT id, depth FROM walk;

Vanliga fallgropar i intervjuer

Slutliga fällor att undvika:

Ta bort MAXRECURSION i SQL Server utan något annat skydd — då återuppstår risken för oändliga loopar.
En sökvägssträngskolumn som deklarerats för kort, vilket orsakar trunkering och ett sökvägsskydd som slutar fungera utan tydligt fel.
Matcha id:n utan kommatecken som avgränsare, så att id 1 felaktigt matchar inuti id 21.
Anta att data är acykliska bara för att de "borde" vara det — fråga alltid.

Snabb kontroll

Välj det skydd som stoppar cykler exakt utan att begränsa ett legitimt djup.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Varje svar med en rekursiv CTE bör behandla säkerheten:

Cykler gör att den rekursiva medlemmen aldrig returnerar tomt, så rekursionen upphör aldrig.
Djupgräns = snabbt reservskydd; kontroll av besökt sökväg = exakt cykelförebyggande; CYCLE-sats = inbyggd upptäckt i moderna databasmotorer.
SQL Servers MAXRECURSION 100 är en inbyggd säkerhetsventil — ta inte bort den utan ett annat skydd.
Indexera join-kolumnen och initiera snävt för bättre prestanda.

Nu kan du skriva, traversera, generera och säkra rekursiva CTE:er från början till slut.

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 ”Undvik oändlig rekursion” gratis?

Ja – hela texten till ”Undvik oändlig rekursion” 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 ”Undvik oändlig rekursion”?

Cykeldetektering, djupbegränsningar och rekursionsskyddet som varje intervjuare kontrollerar 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 4 av 4.

Hur lång tid tar lektionen ”Undvik oändlig rekursion”?

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