Un DFS recursivo profundo en Python sobre un grafo en forma de camino de 100.000 nodos probablemente…
Opciones
- Funcionará bien, porque Python optimiza la recursión profunda
- Dará un RecursionError, porque el límite por defecto es de unos 1000 (Opción correcta)
- Correrá en espacio O(1), usando el mismo stack frame
- Se optimizará con eliminación de tail calls en el intérprete
Respuesta
Dará un RecursionError (límite por defecto de unos 1000)
Por qué
Cada llamada recursiva añade un frame al call stack. Python limita la profundidad a unos 1000 frames por defecto para evitar caídas.
Un camino de 100.000 nodos necesita 100.000 llamadas anidadas → RecursionError. Python no optimiza las tail calls.
Solución: escríbelo de forma iterativa con tu propia pila (una lista).
def dfs(start):
stack, seen = [start], {start}
while stack:
node = stack.pop()
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)Recuerda
Recursión profunda en Python → conviértela en un bucle con una pila.