Forberedelse til kodeintervjuer · leksjon

Unngå uendelig rekursjon

Syklusdeteksjon, dybdegrenser og rekursjonssikringen alle intervjuere ser etter.

Leksjon 4 av 413 trinn

Unngå uendelig rekursjon er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Spørsmålet bak spørsmålet

Etter at et rekursivt CTE er skrevet, spør en skarp intervjuer: «Hva skjer hvis dataene inneholder en syklus?» Dette undersøker om en forstår at rekursjon kan kjøre for alltid — og om en vet hvordan dette kan forhindres.

En syklus oppstår når hierarkiet går tilbake til seg selv: A rapporterer til B, og B rapporterer til A. Det naive rekursive medlemmet vil veksle mellom dem i det uendelige.

Slik oppstår en syklus

Trær skal være asykliske, men virkelige data er uoversiktlige. En feilaktig oppdatering kan gjøre en ansatt til sin egen (indirekte) leder. En graf — for eksempel «brukere som følger brukere» — er syklisk av natur.

Når det rekursive medlemmet møter en node det allerede har besøkt, produserer det noden på nytt, noe som utløser barna på nytt, og sløyfen tømmes aldri. Rekursjon stopper bare når et trinn returnerer ingen rader; en syklus garanterer at det alltid returneres rader.

Beskyttelse 1: En dybdegrense

Det enkleste sikkerhetsnettet er en dybdeteller med en grense i det rekursive medlemmet. Selv om det finnes en syklus, stopper rekursjonen ved grensen.

Dette er et grovt virkemiddel — det begrenser også legitime, dype trær — men det er raskt å bruke og egner seg godt 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;

Beskyttelse 2: En besøkt sti

En presis beskyttelse holder oversikt over stien til besøkte noder og nekter å gå inn i en node som allerede finnes på stien. Samle id-er i en streng eller tabell, og kontroller om noden finnes før rekursjonen fortsetter.

Dette stopper sykluser nøyaktig, samtidig som legitim dybde kan være vilkårlig stor.

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;

Derfor fungerer stisjekken

Betingelsen path NOT LIKE '%,' || e.id || ',%' betyr «følg bare denne kanten hvis barnets id ikke allerede finnes i stien». Kommaene fungerer som skilletegn, slik at id 1 ikke feilaktig blir matchet inne i id 15.

Hvis en syklus ville ha besøkt en node på nytt, filtrerer WHERE bort raden, det rekursive medlemmet returnerer til slutt ingenting, og rekursjonen avsluttes på en kontrollert måte.

Beskyttelse 3: Innebygd CYCLE-klausul

Moderne Postgres (14+) og SQL-standarden tilbyr en innebygd CYCLE-klausul som automatiserer stisjekken og markerer sykluser. Dette er det ryddigste svaret når motoren støtter det.

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 håndhever som standard en grense på 100 rekursjonsnivåer. Hvis en syklus eller et dypt tre overskrider den, avsluttes spørringen med en feilmelding i stedet for å kjøre for alltid — en innebygd sikkerhetsventil.

Grensen kan økes eller fjernes med OPTION (MAXRECURSION n), der 0 betyr ubegrenset. Å fjerne grensen uten en stisjekk gjeninnfører imidlertid risikoen for en uendelig løkke i sykliske data.

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

Oppdage kontra forhindre sykluser

Intervjuere kan skille mellom to mål:

Forhindre — hopp stille over den sykliske kanten slik at spørringen fullføres (stisjekkens WHERE).
Oppdage og rapportere — vis hvilke rader som inngår i en syklus, slik at et datateam kan rette de feilaktige dataene (flagget is_cycle i CYCLE-klausulen).

Å kjenne til begge, og vite når hver av dem passer, er en forskjell på seniornivå.

Ytelsesbetraktninger

Rekursjon kan være kostbar selv uten sykluser. Tips intervjuere gjerne hører:

Indekser koblingskolonnen, for eksempel manager_id, slik at koblingen i hver iterasjon går raskt.
Filtrer tidlig i ankeret, slik at bare deltreet som trengs, tas med, ikke hele tabellen.
Unngå SELECT * — ta bare med kolonnene rekursjonen trenger, i tillegg til depth/path.

En trygg mal

Kombiner beskyttelsene til en mal som kan gjenskapes under press: en dybdekolonne som sikkerhetsnett og en stisjekk som presis beskyttelse. Selv om én av dem er overflødig for rene data, viser det grundighet å ta med begge.

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;

Vanlige fallgruver i intervjuer

Unngå disse siste fellene:

Fjerne MAXRECURSION i SQL Server uten annen beskyttelse — dette åpner på nytt for risikoen for uendelige løkker.
Deklarere en kolonne for stistrengen med for kort lengde, slik at avkorting oppstår og beskyttelsen brytes uten synlig feil.
Sammenligne id-er uten kommaseparatorer, slik at id 1 feilaktig blir matchet inne i id 21.
Anta at dataene er asykliske bare fordi de «skal» være det — spør alltid.

Kort kontroll

Velg beskyttelsen som stopper sykluser presist uten å begrense legitim dybde.

Besvar den i den interaktive leksjonen

Oppsummering

Ethvert svar med et rekursivt CTE bør ta opp sikkerhet:

Sykluser gjør at det rekursive medlemmet aldri returnerer tomt, slik at rekursjonen aldri stopper.
Dybdegrense = raskt sikkerhetsnett; sjekk av besøkt sti = presis forebygging av sykluser; CYCLE-klausul = innebygd oppdagelse i moderne motorer.
SQL Servers MAXRECURSION 100 er en innebygd sikkerhetsventil — den bør ikke fjernes uten en annen beskyttelse.
Indekser koblingskolonnen og start smalt for bedre ytelse.

Nå kan en skrive, traversere, generere og sikre rekursive CTE-er fra ende til annen.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Unngå uendelig rekursjon» gratis?

Ja – hele teksten i «Unngå uendelig rekursjon» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Unngå uendelig rekursjon»?

Syklusdeteksjon, dybdegrenser og rekursjonssikringen alle intervjuere ser etter. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Unngå uendelig rekursjon»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Forberedelse til kodeintervjuer