Coding Interview Prep · Leçon

Éviter la récursivité infinie

Détection des cycles, limites de profondeur et garde-fou de récursivité vérifié par tout recruteur

Éviter la récursivité infinie est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

La question sous-jacente

Après avoir écrit une CTE récursive, une personne qui mène l'entretien peut vous poser une question pertinente : « Que se passe-t-il si les données contiennent un cycle ? » Cela vérifie que vous comprenez que la récursivité peut s'exécuter indéfiniment — et que vous savez vous en prémunir.

Un cycle se produit lorsque la hiérarchie revient sur elle-même : A dépend de B et B dépend de A. Le membre récursif naïf oscille alors indéfiniment entre les deux.

Comment un cycle se forme

Les arbres sont censés être acycliques, mais les données réelles sont désordonnées. Une mauvaise mise à jour peut désigner un employé comme son propre responsable, directement ou indirectement. Un graphe — comme celui des « utilisateurs qui suivent des utilisateurs » — est cyclique par nature.

Lorsque le membre récursif rencontre à nouveau un nœud déjà visité, il produit encore ce nœud, ce qui réactive ses enfants et empêche la boucle de se vider. La récursivité ne s'arrête que lorsqu'une étape ne renvoie aucune ligne ; un cycle garantit qu'elle renvoie toujours des lignes.

Protection 1 : une limite de profondeur

La protection la plus simple consiste à utiliser un compteur de profondeur avec un plafond dans le membre récursif. Même en présence d'un cycle, la récursivité s'arrête lorsqu'elle atteint cette limite.

C'est une solution rudimentaire — elle plafonne aussi les arbres légitimement profonds — mais elle est rapide et adaptée aux entretiens.

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;

Protection 2 : un chemin parcouru

Une protection précise suit le chemin des nœuds visités et refuse de revenir dans un nœud déjà présent sur ce chemin. Accumulez les identifiants dans une chaîne ou un tableau, puis vérifiez leur appartenance avant de poursuivre la récursivité.

Cela arrête exactement les cycles tout en autorisant une profondeur arbitraire dans les arbres valides.

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;

Pourquoi la vérification du chemin fonctionne

La condition path NOT LIKE '%,' || e.id || ',%' signifie « ne suivez cette arête que si l'identifiant enfant n'est pas déjà présent dans le chemin ». Les virgules servent de délimiteurs afin que l'identifiant 1 ne corresponde pas par erreur à l'intérieur de l'identifiant 15.

Si un cycle devait revisiter un nœud, le WHERE exclurait cette ligne, le membre récursif ne renverrait finalement plus rien et la récursivité s'arrêterait proprement.

Protection 3 : la clause native CYCLE

Les versions modernes de Postgres (14 et suivantes) ainsi que la norme SQL proposent une clause CYCLE intégrée qui automatise la vérification du chemin et signale les cycles pour vous. C'est la réponse la plus élégante lorsque le moteur la prend en charge.

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;

La limite MAXRECURSION de SQL Server

SQL Server impose par défaut un plafond de 100 niveaux de récursivité. Si un cycle ou un arbre profond le dépasse, la requête échoue au lieu de boucler indéfiniment — c'est un mécanisme de sécurité implicite.

Vous pouvez augmenter ou supprimer cette limite avec OPTION (MAXRECURSION n), où 0 signifie qu'il n'y a aucune limite. Mais supprimer le plafond sans protection fondée sur le chemin réintroduit le risque de boucle infinie avec des données cycliques.

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

Détecter ou empêcher les cycles

Les personnes qui mènent les entretiens peuvent distinguer deux objectifs :

Empêcher — ignorer silencieusement l'arête cyclique afin que la requête s'achève, grâce au WHERE qui vérifie le chemin.
Détecter et signaler — indiquer quelles lignes font partie d'un cycle afin que l'équipe chargée des données puisse corriger les données incorrectes, grâce à l'indicateur is_cycle de la clause CYCLE.

Connaître ces deux approches et savoir quand chacune est adaptée est une distinction de niveau confirmé.

Considérations de performances

La récursivité peut être coûteuse même en l'absence de cycles. Voici des conseils que les personnes qui mènent les entretiens aiment entendre :

Indexez la colonne de jointure, par exemple manager_id, afin que la jointure de chaque itération soit rapide.
Filtrez tôt dans l'ancre afin d'initialiser uniquement le sous-arbre nécessaire, plutôt que la table entière.
Évitez SELECT * — ne conservez que les colonnes nécessaires à la récursivité, ainsi que depth et path.

Un modèle sûr

Combinez les protections dans un modèle que vous pouvez reproduire sous pression : une colonne de profondeur comme filet de sécurité et une vérification du chemin comme protection précise. Même si l'une des deux est excessive pour des données propres, les présenter toutes les deux témoigne de votre rigueur.

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;

Pièges fréquents en entretien

Voici les derniers pièges à éviter :

Supprimer MAXRECURSION dans SQL Server sans autre protection — cela rouvre le risque de boucle infinie.
Déclarer une colonne de chaîne de chemin trop courte, ce qui provoque une troncature et rend la protection inefficace sans avertissement.
Comparer les identifiants sans délimiteurs virgule, de sorte que l'identifiant 1 corresponde par erreur à l'intérieur de l'identifiant 21.
Supposer que les données sont acycliques simplement parce qu'elles « devraient » l'être — posez toujours la question.

Vérification rapide

Choisissez la protection qui arrête précisément les cycles sans plafonner la profondeur valide.

Récapitulatif

Toute réponse utilisant une CTE récursive doit traiter les aspects de sécurité :

Les cycles empêchent le membre récursif de ne plus rien renvoyer, et la récursivité ne s'arrête donc jamais.
Plafond de profondeur = filet de sécurité rapide ; vérification du chemin parcouru = prévention précise des cycles ; clause CYCLE = détection native dans les moteurs modernes.
Le MAXRECURSION 100 de SQL Server est une soupape implicite — ne le supprimez pas sans une autre protection.
Indexez la colonne de jointure et initialisez un sous-ensemble restreint pour de meilleures performances.

Vous pouvez maintenant écrire, parcourir, générer et sécuriser des CTE récursives de bout en bout.

Questions Fréquemment Posées

La leçon « Éviter la récursivité infinie » est-elle gratuite ?

Oui — le texte complet de « Éviter la récursivité infinie » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Éviter la récursivité infinie » ?

Détection des cycles, limites de profondeur et garde-fou de récursivité vérifié par tout recruteur Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Éviter la récursivité infinie » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

Membres d’ancrage et membres récursifs
Parcourir un organigramme
Générer des séries de nombres et de dates
Éviter la récursivité infinie

← Retour à Coding Interview Prep