Cuando un servidor DNS no conoce una resolución, normalmente utiliza otro servidor DNS situado inmediatamente superior en la jerarquía de dominios para intentar resolverla. Esta política de consultas recursivas finalmente encuentra un servidor DNS que sí conoce la resolución. Entonces el registro DNS solicitado viaja desde dicho servidor DNS deshaciendo el camino hasta el servidor DNS al que inicialmente realizamos la consulta. En este proceso, cada servidor DNS actualiza su caché con esta información por un determinado periodo de tiempo.
Por ejemplo, cuando queremos acceder a www.nasa.gov desde un host de la Universidad de Almería, dicho host (generalmente* ) debería preguntar a filabres.ual.es. Si filabres no almacena en su caché la resolución, pregunta al siguiente servidor DNS en la jerarquía que podría ser un nodo del CICA (Centro Informático Científico de Andalucía). Si éste fallara, preguntaría a un servidor de RedIRIS (la red académica y de investigación nacional), y así sucesivamente hasta llegar a un servidor DNS raíz. Si éste falla, entonces la consulta comienza a descender por la jerarquía de servidores DNS hasta llegar al responsable del dominio nasa.gov que necesariamente debe conocer la resolución.
Existe una versión diferente de este algoritmo recursivo que se realiza una consulta iterativa. La diferencia radica en que cuando un servidor DNS falla en lugar de hacer él la consulta le indica al cliente a qué otro servidor DNS puede preguntar. Este proceso, sin embargo, no actualiza las cachés de los servidores.