Server Fault is a question and answer site for system and network administrators. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to understand the difference between iterative and recursive DNS lookups. Fundamentally, I think of iterative as being like calling a department store looking for a product, and when they don't have it, they give you the number of another one of their branches to call and then you call the other branch yourself. Versus recursive, which is like calling the department store, and when they don't have what you're after, they call the other branch on your behalf looking for the product. Thing is, I'm getting conflicting views about this when it comes to DNS. When I think of recursive, I think of something that looks like this: alt text

But while reading articles on the web, and even doing a Google image search for DNS recursive, I see far more examples that look like this: alt text

To me, this second example looks more iterative than it does recursive, because each of the "other DNS servers" is telling the "preferred DNS server" the address of the next machine to lookup, rather than looking it up on behalf of the preferred DNS server. The only recursive element I see is that the preferred DNS server does lookups on behalf of the DNS client, but from here on, it sure looks iterative though.

So I guess my question is, does "recursive" DNS lookup really only mean recursive in the sense of the preferred DNS server doing something on the client's behalf, but really iterative from here on in? The majority of results I'm seeing in Google image search are leading me to believe this, which then begs the question, is the first image in this post just plain wrong?

share|improve this question
Check out the Ask Mr DNS podcast, entertaining, informative, and they have been managing DNS as since 1989, authored or co-authored every O'Reily DNS book, etc. Learn more than you ever wanted to know. – Ronald Pottol Sep 18 '10 at 9:18
Awesome question! – quux Sep 18 '10 at 12:21
up vote 16 down vote accepted

Your last paragraph is correct.

The "Recursion Desired" (RD) flag sent by the client in the DNS request header (see RFC 1035) asks the server "please give me the complete answer to this question".

That server than iteratively asks the chain of name servers for the correct answer. Those queries shouldn't themselves have the RD bit set.

Ultimately the recursive server's response will have the "Recursion Available" (RA) flag set, indicating that the answer was indeed fully answered. Conversely an authoritative server will not set the RA flag.

IMHO, it's a poor choice of terminology.

For what it's worth, that first diagram you've found is fundamentally incorrect. The root servers do not perform queries to any other server, they only issue referrals to other servers.

share|improve this answer

As far as I understand it, "recursive lookup" is solely from the view of the original querier. So, if it asks a DNS server and gets a completely resolved answer back, then it is a "recursive query". If that server in turn does recursive or iterative lookups is, well, not something the original querier has to care about.

share|improve this answer

The first of the two diagrams in your question is incorrect. Root servers don't send queries to other servers. If the root servers did in fact forward queries like shown in that diagram the DNS system would be a lot more vulnerable to DoS attacks than it really is.

The second diagram is mostly correct but too simplified to show you the recursive nature of lookups. The diagram is still detailed enough though that we can point out where recursion happens.

The DNS server next to the number 12 the one denoted Preferred DNS server is where recursion happens. The term Preferred DNS server is not standard terminology. That server would usually be called a caching DNS recursor or some abbreviation of that.

When looking at the network traffic it does indeed look iterative. The recursion is entirely internal to the DNS recursor. If you look at the implementation of a DNS recursor you will find some recursive structure in how requests are handled.

The recursion may be easy to spot if the implementation uses a thread per request and the lookups are implemented using recursive function calls. But more efficient designs don't use a thread per request and the recursion is instead found inside the data structures used by the DNS recursor.

The reason that recursion is needed is due to how the references between the authoritative DNS servers are implemented. This is best illustrated with an example. In the diagram you see the authoritative DNS server for point to the authoritative DNS server for This is done using a NS record which points to a hostname. So for example the authoritative server for could tell the DNS recursor that is authoritative for

At that point the DNS recursor would have to resolve before it would be able to proceed with the resolution of

In order to resolve one hostname it first has to resolve a different hostname. That is recursion. In order for this to not lead to infinite recursion, DNS has glue records which are sent along with NS records in certain cases.

share|improve this answer
There are lots of errors in this. The use of the term "recursion" has nothing to do with whether "recursive function calls" are used - Vatine's answer is closer - recursion is just a (poorly chosen) name for when a client asks a server for a complete resolved answer. The mechanism used by the so-called "recursive servers" is actually called iteration. Also, glue records and not to prevent "infinite recursion" - they are there to prevent the "chicken and egg" problem of how you find the address of the nameservers if those servers are within the delegated domain's space. – Alnitak Oct 6 '15 at 3:51
@Alnitak DNS resolution is inherently recursive. Any recursive algorithm can be turned into something iterative by turning the execution stack into a different data structure. That possibility is already mentioned in my answer. And the cyclic dependency problem that you mention is not something different from an infinite recursion. The two are really the same thing. If you were to apply a naive recursive algorithm without noticing that the underlying task suffers from a cyclic dependency, the result will be infinite recursion. – kasperd Oct 6 '15 at 9:04
@Alnitak You cannot get rid of the recursion stack and perform the DNS resolution iteratively keeping track of only a constant number of DNS names at a time. You can represent the recursion stack with a differently looking data structure, but it remains inherently recursive. It is possible to configure a domain name in a way that will keep the recursion depth to just one. But not all domain names are configured that way. – kasperd Oct 6 '15 at 9:09
I quote RFC 1034 - ""The two general approaches to dealing with this problem are "recursive", in which the first server pursues the query for the client at another server, and "iterative", in which the server refers the client to another server and lets the client pursue the query ."" It has nothing to do with "stacks" or "data structures". – Alnitak Oct 6 '15 at 13:17
@Alnitak That paragraph is referring to a different kind of recursion than my answer. The recursion mentioned in my answer is (as clearly stated in my answer) internal to one specific DNS server. If you actually tried to implement DNS recursion in an entirely iterative fashion, it would never work. As soon as you get a reply with an NS record without associated glue, you have to look up the IP address of the hostname pointed to by that NS record before you can continue with the original resolution. – kasperd Oct 6 '15 at 13:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.