Coding Interview Prep · Lección

Evitar la recursividad infinita

Conozca la detección de ciclos, los límites de profundidad y la protección contra recursividad que comprueban todos los entrevistadores

Evitar la recursividad infinita es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

La pregunta que hay detrás de la pregunta

Después de escribir una CTE recursiva, un entrevistador perspicaz puede preguntar: «¿Qué ocurre si los datos contienen un ciclo?». Con esto comprueba si entiende que la recursión puede ejecutarse indefinidamente y si sabe cómo protegerse contra ello.

Un ciclo se produce cuando la jerarquía vuelve sobre sí misma: A depende de B y B depende de A. El miembro recursivo ingenuo alternará entre ambos indefinidamente.

Cómo se forma un ciclo

Se supone que los árboles son acíclicos, pero los datos reales pueden ser desordenados. Una actualización incorrecta puede establecer a un empleado como su propio gerente (directa o indirectamente). Un grafo —por ejemplo, «usuarios que siguen a otros usuarios»— es cíclico por naturaleza.

Cuando el miembro recursivo vuelve a encontrar un nodo que ya había visitado, lo produce de nuevo, lo que vuelve a activar sus hijos, y el conjunto nunca se vacía. La recursión solo se detiene cuando un paso no devuelve filas; un ciclo garantiza que siempre devuelva alguna.

Protección 1: un límite de profundidad

La red de seguridad más sencilla es un contador de profundidad con un límite en el miembro recursivo. Aunque exista un ciclo, la recursión se detendrá al alcanzar ese límite.

Es una medida poco precisa —también limita los árboles legítimamente profundos—, pero resulta rápida y adecuada para una entrevista.

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;

Protección 2: una ruta de nodos visitados

Una protección precisa realiza un seguimiento de la ruta de los nodos visitados y evita volver a entrar en uno que ya se encuentre en ella. Acumule los identificadores en una cadena (o un array) y compruebe si ya están presentes antes de continuar la recursión.

Esto detiene los ciclos con precisión y, al mismo tiempo, permite cualquier profundidad en los árboles legítimos.

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;

Por qué funciona la comprobación de la ruta

La condición path NOT LIKE '%,' || e.id || ',%' significa «siga esta arista solo si el identificador del hijo no está ya en la ruta». Las comas actúan como delimitadores para que el identificador 1 no coincida por error dentro del identificador 15.

Si un ciclo volviera a visitar un nodo, el WHERE filtraría esa fila, el miembro recursivo acabaría sin devolver ninguna fila y la recursión terminaría correctamente.

Protección 3: la cláusula CYCLE nativa

Las versiones modernas de Postgres (14+) y el estándar SQL ofrecen una cláusula CYCLE integrada que automatiza la comprobación de la ruta y marca los ciclos. Es la respuesta más limpia cuando el motor la admite.

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 de SQL Server

SQL Server aplica de forma predeterminada un límite de 100 niveles de recursión. Si un ciclo (o un árbol profundo) lo supera, la consulta produce un error en lugar de ejecutarse indefinidamente: es una válvula de seguridad implícita.

Puede aumentarlo o eliminarlo mediante OPTION (MAXRECURSION n), donde 0 significa que no hay límite. Sin embargo, eliminar el límite sin una protección basada en la ruta vuelve a introducir el riesgo de un bucle infinito con datos cíclicos.

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

Detectar frente a prevenir ciclos

Los entrevistadores pueden distinguir entre dos objetivos:

Prevenir: omitir silenciosamente la arista cíclica para que la consulta termine (el WHERE que comprueba la ruta).
Detectar e informar: mostrar qué filas forman parte de un ciclo para que el equipo de datos pueda corregir los datos incorrectos (el indicador is_cycle de la cláusula CYCLE).

Conocer ambos objetivos y saber cuándo corresponde aplicar cada uno es una distinción propia de un nivel sénior.

Consideraciones de rendimiento

La recursión puede ser costosa incluso sin ciclos. Estas son algunas recomendaciones que los entrevistadores valoran:

Indexe la columna de unión (por ejemplo, manager_id) para que la unión de cada iteración sea rápida.
Filtre pronto en la ancla para iniciar solo el subárbol que necesita, no toda la tabla.
Evite SELECT *: conserve únicamente las columnas que requiere la recursión, además de depth y path.

Una plantilla segura

Combine las protecciones en una plantilla que pueda reproducir bajo presión: la columna de profundidad como respaldo y la comprobación de la ruta como protección precisa. Aunque una de ellas sea excesiva para datos limpios, mostrar ambas señales de rigor.

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;

Errores habituales en entrevistas

Estos son los últimos errores que debe evitar:

Eliminar MAXRECURSION en SQL Server sin ninguna otra protección: vuelve a abrir el riesgo de un bucle infinito.
Declarar demasiado corta la columna de cadena de la ruta, lo que provoca truncamiento y rompe la protección sin que se detecte.
Comparar identificadores sin delimitadores de comas, de modo que el identificador 1 coincida por error dentro del identificador 21.
Suponer que los datos son acíclicos solo porque «deberían serlo»: pregúntelo siempre.

Comprobación rápida

Elija la protección que detiene los ciclos con precisión sin limitar la profundidad legítima.

Repaso

Toda respuesta que utilice una CTE recursiva debe abordar la seguridad:

Los ciclos hacen que el miembro recursivo nunca devuelva un resultado vacío, por lo que la recursión no se detiene.
Límite de profundidad = respaldo rápido; comprobación de la ruta de nodos visitados = prevención precisa de ciclos; cláusula CYCLE = detección nativa en los motores modernos.
MAXRECURSION 100 de SQL Server es una válvula implícita: no la elimine sin otra protección.
Indexe la columna de unión e inicie la recursión con un conjunto reducido para mejorar el rendimiento.

Ahora puede escribir, recorrer, generar y proteger CTE recursivas de principio a fin.

Preguntas frecuentes

¿La lección «Evitar la recursividad infinita» es gratis?

Sí — el texto completo de «Evitar la recursividad infinita» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Evitar la recursividad infinita»?

Conozca la detección de ciclos, los límites de profundidad y la protección contra recursividad que comprueban todos los entrevistadores Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.

¿Cuánto tiempo toma la lección «Evitar la recursividad infinita»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

← Volver a Coding Interview Prep