Coding Interview Prep · Lezione

Membri anchor e ricorsivi

La struttura in due parti di un CTE ricorsivo e il funzionamento della terminazione

Membri anchor e ricorsivi è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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.

Perché si parla di CTE ricorsive

Quando un intervistatore Le presenta un organigramma, una distinta base o un albero di categorie e Le chiede di trovare ogni discendente, sta verificando se sa ricorrere a una CTE ricorsiva. Le semplici JOIN possono percorrere solo un numero fisso di livelli; la ricorsione può percorrere una profondità arbitraria.

Le espressioni rivelatrici in una domanda sono "a qualsiasi profondità" o "fino in fondo". Questo è il segnale da riconoscere. In questa lezione imparerà la struttura in due parti condivisa da ogni CTE ricorsiva: il membro di ancoraggio e il membro ricorsivo.

La struttura in due parti

Una CTE ricorsiva contiene sempre la parola chiave WITH RECURSIVE (Postgres, SQLite, MySQL 8+; SQL Server omette RECURSIVE) e un corpo composto da due query unite da UNION ALL:

Membro di ancoraggio — le righe iniziali, eseguito una volta.
Membro ricorsivo — fa riferimento al nome della CTE stessa ed eseguito ripetutamente.

Memorizzi questa struttura: gli intervistatori spesso chiedono di scriverla da zero.

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

Cosa fa il membro di ancoraggio

Il membro di ancoraggio è una query ordinaria che non fa riferimento alla CTE. Produce le righe iniziali, cioè il punto di partenza di livello zero. In un organigramma è in genere il CEO, ovvero la riga il cui manager è NULL; per una sequenza di numeri è il primo numero.

Il membro di ancoraggio viene eseguito esattamente una volta. Il suo risultato diventa il primo gruppo di righe passato al passaggio ricorsivo.

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

Cosa fa il membro ricorsivo

Il membro ricorsivo fa riferimento alla CTE tramite il suo nome. A ogni iterazione unisce le righe prodotte dall'iterazione precedente alla tabella di base per trovare il livello successivo.

Non vede l'intera CTE costruita fino a quel momento — vede solo le righe aggiunte nel passaggio immediatamente precedente. Questo è il modello mentale fondamentale che gli intervistatori vogliono verificare.

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

Mettere insieme i componenti

Unisca il membro di ancoraggio e quello ricorsivo con UNION ALL e il motore eseguirà automaticamente le iterazioni. Ogni passaggio aggiunge il livello successivo, finché il membro ricorsivo non restituisce zero righe; a quel punto la ricorsione si arresta.

Ecco un esempio completo ed eseguibile di attraversamento di un organigramma, che tiene traccia anche di 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;

Come funziona la terminazione

La ricorsione si arresta quando il membro ricorsivo non produce nuove righe. Non è necessario alcun contatore esplicito del ciclo — la JOIN si esaurisce naturalmente quando si raggiungono le foglie dell'albero.

Nell'esempio dell'organigramma, quando si raggiungono dipendenti senza subordinati diretti, la JOIN dell'iterazione successiva non trova figli, restituisce un risultato vuoto e il motore si arresta. Comprendere questo comportamento con terminazione automatica è una classica domanda di approfondimento.

UNION ALL e UNION a confronto

Gli intervistatori chiedono spesso perché si usa UNION ALL invece di UNION. I motivi sono due:

Prestazioni — UNION elimina i duplicati a ogni iterazione, un'operazione costosa.
Correttezza — in un albero, di norma non possono comparire righe duplicate, quindi eliminare i duplicati è lavoro inutile.

Usi UNION solo quando la struttura è un grafo e desidera deliberatamente accorpare i nodi ripetuti — per gestire i cicli, però, sono preferibili controlli espliciti, che vedrà più avanti.

Tracciare profondità e percorso

Due colonne aggiuntive rendono i risultati ricorsivi molto più utili e vengono richieste spesso nei colloqui:

depth — inizi a 1 nel membro di ancoraggio e aggiunga 1 nel membro ricorsivo.
path — accumuli la catena di id o nomi per visualizzare il percorso dalla radice al nodo.

Costruire path come stringa serve anche come strumento per rilevare i cicli, come vedrà più avanti.

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;

I tipi delle colonne devono corrispondere

Un dettaglio insidioso: il membro di ancoraggio e quello ricorsivo devono restituire lo stesso numero di colonne con tipi compatibili. Se costruisce una stringa path, il valore iniziale del membro di ancoraggio deve essere convertito a una larghezza sufficiente, ad esempio VARCHAR(1000), altrimenti il motore potrebbe troncare il valore o generare un errore di incompatibilità dei tipi nelle iterazioni successive.

È esattamente il tipo di dettaglio che un intervistatore inserisce per verificare se ha davvero eseguito una CTE ricorsiva, invece di averne soltanto letto.

Esempio di distinta base

La stessa struttura risolve il problema di una distinta base: data una parte, elencare ogni sottoparte a qualsiasi profondità. Il membro di ancoraggio seleziona l'assemblaggio principale; il membro ricorsivo percorre i collegamenti da parent_part a child_part.

Noti che la struttura è identica a quella dell'organigramma: cambiano solo i nomi delle colonne. Riconoscere che un'unica struttura si adatta a molti problemi è la vera competenza richiesta nei colloqui.

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;

Note sui dialetti

Un rapido promemoria tra dialetti che gli intervistatori apprezzano:

PostgreSQL, SQLite, MySQL 8+: WITH RECURSIVE name AS (...).
SQL Server: semplicemente WITH name AS (...) — la parola chiave RECURSIVE è implicita e viene imposto un valore predefinito di MAXRECURSION pari a 100.
Oracle: supporta sia le CTE ricorsive sia la sintassi precedente CONNECT BY.

Dire "SQL Server non usa la parola RECURSIVE" dimostra una conoscenza concreta dei diversi dialetti.

Verifica rapida

Verifichi di aver compreso la struttura in due parti.

Riepilogo

Ora conosce la struttura di base delle CTE ricorsive:

WITH RECURSIVE + membro di ancoraggio + UNION ALL + membro ricorsivo.
Il membro di ancoraggio inizializza il livello zero e viene eseguito una volta.
Il membro ricorsivo unisce l'iterazione precedente alla tabella di base e continua finché non restituisce righe.
Usi UNION ALL, tenga traccia di depth e path e mantenga compatibili i tipi delle colonne.

Prossimo passo: applicare questa struttura per percorrere un vero organigramma verso il basso e verso l'alto.

Domande Frequenti

La lezione «Membri anchor e ricorsivi» è gratuita?

Sì — il testo completo di «Membri anchor e ricorsivi» è 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 «Membri anchor e ricorsivi»?

La struttura in due parti di un CTE ricorsivo e il funzionamento della terminazione 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 1 di 4.

Quanto tempo richiede la lezione «Membri anchor e ricorsivi»?

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