Recursion faster than iteration

Question

I've implemented a quadtree in C# and have come across a weird occurrence where recursion seems to perform better than iteration, despite looking like it should be the opposite.

My nodes look like this:

class QuadNode
{
    private QuadNode topLeft;
    private QuadNode topRight;
    private QuadNode bottomRight;
    private QuadNode bottomLeft;
    // other fields...
}

To traverse the tree I used the following recursive method, which I invoke on the root node:

Traverse()
{
    // visit 'this'

    if (topLeft != null)
        topLeft.Traverse();
    if (topRight != null)
        topRight.Traverse();
    if (bottomRight != null)
        bottomRight.Traverse();
    if (bottomLeft != null)
        bottomLeft.Traverse();
}

Mostly out of interest, I tried to create an iterative method for traversing the tree.

I added the following field to each node: private QuadNode next, and when I create the tree I perform a breadth-first traversal using a queue, linking the next field of each node to the next node in line. Essentially I created a singly-linked list from the nodes of the tree.
At this point I am able to traverse the tree with the following method:

Traverse()
{
    QuadNode node = this;
    while (node != null)
    {
        // visit node

        node = node.next;
    }
}

After testing the performance of each method I was very surprised to learn that the iterative version is consistently and noticeably slower than the recursive one. I've tested this on both huge trees and small trees alike and the recursive method is always faster. (I used aStopwatch for benchmarking)
I've confirmed that both methods traverse the entire tree successfully and that the iterative version only visits each node exactly once as planned, so it's not a problem with the linking between them.

It seems obvious to me that the iterative version would perform better... what could be the cause of this? Am I overlooking some obvious reason as to why the recursive version is faster?

_{I'm using Visual Studio 2012 and Compiled under Release, Any CPU (prefer 32 bit unchecked).}

Edit:
I've opened a new project and created a simple test which also confirms my results.
Here's the full code: http://pastebin.com/SwAsTMjQ
The code isn't commented but I think it's pretty self-documenting.

Answer 1

Cache locality is killing speed. Try:

public void LinkNodes()
{
    var queue = new Queue<QuadNode>();
    LinkNodes(queue);

    QuadNode curr = this;

    foreach (var item in queue)
    {
        curr.next = item;
        curr = item;
    }
}

public void LinkNodes(Queue<QuadNode> queue)
{
    queue.Enqueue(this);

    if (topLeft != null)
        topLeft.LinkNodes(queue);
    if (topRight != null)
        topRight.LinkNodes(queue);
    if (bottomRight != null)
        bottomRight.LinkNodes(queue);
    if (bottomLeft != null)
        bottomLeft.LinkNodes(queue);
}

Now the iterative version should be 30/40% faster than the recursive version.

The reason of the slowness is that your iterative algorithm will go Breadth First instead of Depth First. You created your elements Depth First, so they are sorted Depth First in memory. My algorithm creates the traverse list Depth First.

(note that I used a Queue in LinkNodes() to make it easier to follow, but in truth you could do it without)

public QuadNode LinkNodes(QuadNode prev = null)
{
    if (prev != null)
    {
        prev.next = this;
    }

    QuadNode curr = this;

    if (topLeft != null)
        curr = topLeft.LinkNodes(curr);

    if (topRight != null)
        curr = topRight.LinkNodes(curr);

    if (bottomRight != null)
        curr = bottomRight.LinkNodes(curr);

    if (bottomLeft != null)
        curr = bottomLeft.LinkNodes(curr);

    return curr;
}