Coding Interview Prep · Lezione

Evitare la ricorsione infinita

Rilevamento dei cicli, limiti di profondità e controllo della ricorsione verificato in ogni colloquio

Evitare la ricorsione infinita è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.

La domanda dietro la domanda

Dopo aver scritto una CTE ricorsiva, un intervistatore attento potrebbe chiedere: "Cosa succede se i dati contengono un ciclo?" Questa domanda verifica se si comprende che la ricorsione può continuare all'infinito e se si sa come proteggerla.

Un ciclo si verifica quando la gerarchia torna su se stessa: A riporta a B e B riporta ad A. Il membro ricorsivo ingenuo continuerebbe a passare dall'uno all'altro senza fine.

Come si forma un ciclo

Gli alberi dovrebbero essere aciclici, ma i dati reali sono complessi. Un aggiornamento errato può impostare un dipendente come proprio manager, direttamente o indirettamente. Un grafo, come quello degli "utenti che seguono altri utenti", è ciclico per natura.

Quando il membro ricorsivo incontra di nuovo un nodo già visitato, produce nuovamente quel nodo, riattivando i relativi figli, e il ciclo non si svuota mai. La ricorsione si arresta solo quando un passaggio non restituisce righe; un ciclo garantisce invece che vengano sempre restituite righe.

Controllo 1: limite di profondità

La protezione più semplice consiste nell'usare un contatore della profondità con un limite nel membro ricorsivo. Anche in presenza di un ciclo, la ricorsione si arresta al raggiungimento del limite.

È uno strumento poco raffinato, perché limita anche gli alberi legittimamente profondi, ma è rapido da applicare e adatto ai colloqui.

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;

Controllo 2: percorso dei nodi visitati

Un controllo preciso tiene traccia del percorso dei nodi visitati e impedisce di rientrare in un nodo già presente nel percorso. Si accumulano gli id in una stringa o in un array e se ne verifica l'appartenenza prima di ricorrere.

In questo modo i cicli vengono arrestati con precisione, consentendo comunque una profondità arbitraria negli alberi legittimi.

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;

Perché il controllo del percorso funziona

La condizione path NOT LIKE '%,' || e.id || ',%' significa "seguire questo collegamento solo se l'id del figlio non è già presente nel percorso". Le virgole fungono da delimitatori, così l'id 1 non viene erroneamente trovato all'interno dell'id 15.

Se un ciclo riporterebbe a un nodo già visitato, il WHERE filtra quella riga, il membro ricorsivo alla fine non restituisce nulla e la ricorsione termina correttamente.

Controllo 3: clausola CYCLE nativa

Le versioni moderne di Postgres (14+) e lo standard SQL offrono una clausola CYCLE integrata che automatizza il controllo del percorso e segnala i cicli. È la soluzione più pulita quando l'engine la supporta.

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;

MAXRECURSION di SQL Server

SQL Server impone un limite predefinito di 100 livelli di ricorsione. Se un ciclo o un albero profondo lo supera, la query genera un errore invece di continuare all'infinito: si tratta di una valvola di sicurezza implicita.

È possibile aumentare o rimuovere il limite con OPTION (MAXRECURSION n), dove 0 significa illimitato. Tuttavia, rimuovere il limite senza un controllo del percorso reintroduce il rischio di un ciclo infinito in presenza di dati ciclici.

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

Rilevare o prevenire i cicli

Gli intervistatori possono distinguere due obiettivi:

Prevenire: ignorare silenziosamente il collegamento ciclico affinché la query termini, usando il WHERE che controlla il percorso.
Rilevare e segnalare: mostrare quali righe fanno parte di un ciclo, così il team responsabile dei dati può correggerli, usando il flag is_cycle della clausola CYCLE.

Conoscere entrambi gli approcci e sapere quando usare ciascuno di essi è una distinzione da livello senior.

Considerazioni sulle prestazioni

La ricorsione può essere costosa anche in assenza di cicli. Ecco alcuni suggerimenti che gli intervistatori apprezzano:

Indicizzare la colonna usata nel join, ad esempio manager_id, per rendere rapido il join di ogni iterazione.
Filtrare presto nell'anchor, così da inizializzare solo il sottoalbero necessario e non l'intera tabella.
Evitare SELECT *: si devono mantenere solo le colonne necessarie alla ricorsione, oltre a depth/path.

Un modello sicuro

Combini i controlli in un modello riproducibile anche sotto pressione: la colonna della profondità come protezione aggiuntiva e il controllo del percorso come controllo preciso. Anche se uno dei due fosse eccessivo per dati puliti, mostrarli entrambi dimostra rigore.

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;

Errori comuni nei colloqui

Gli ultimi errori da evitare:

Rimuovere MAXRECURSION in SQL Server senza alcun altro controllo: si riapre il rischio di un ciclo infinito.
Dichiarare una colonna stringa per il percorso troppo corta, causando un troncamento e compromettendo silenziosamente il controllo.
Confrontare gli id senza delimitatori costituiti da virgole, così l'id 1 viene erroneamente trovato all'interno dell'id 21.
Supporre che i dati siano aciclici solo perché "dovrebbero" esserlo: è sempre necessario verificarlo.

Verifica rapida

Scelga il controllo che arresta i cicli con precisione senza limitare la profondità legittima.

Riepilogo

Ogni soluzione basata su una CTE ricorsiva dovrebbe affrontare gli aspetti di sicurezza:

I cicli fanno sì che il membro ricorsivo non restituisca mai un risultato vuoto, quindi la ricorsione non si arresta.
Limite di profondità = protezione rapida; controllo del percorso visitato = prevenzione precisa dei cicli; clausola CYCLE = rilevamento nativo negli engine moderni.
MAXRECURSION 100 di SQL Server è una valvola implicita: non va rimosso senza un altro controllo.
Si indicizzi la colonna del join e si inizializzi un sottoinsieme ristretto per migliorare le prestazioni.

Ora è possibile scrivere, attraversare, generare e proteggere CTE ricorsive dall'inizio alla fine.

Domande Frequenti

La lezione «Evitare la ricorsione infinita» è gratuita?

Sì — il testo completo di «Evitare la ricorsione infinita» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Evitare la ricorsione infinita»?

Rilevamento dei cicli, limiti di profondità e controllo della ricorsione verificato in ogni colloquio Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Coding Interview Prep?

Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.

Quanto tempo richiede la lezione «Evitare la ricorsione infinita»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?

Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a Coding Interview Prep