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.

http://stackoverflow.com/questions/72209/recursion-or-iteration , http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping/2651200#2651200 — Arie, Sep 17 '13 at 07:08
@Arie what he sees is exactly opposite, hence his question. In his case iteration is **slower**. — Bart Friederichs, Sep 17 '13 at 07:22
how do you store "next" pointers? Do you change ur code to only store one Node pointer when changing to next? — Aleksander Fular, Sep 17 '13 at 07:30
Why didn't you go for the same as the recursion (depth first) and have a stack of elements next to visit? When timing, how much of the extra time is used creating a linked list? — Sylwester, Sep 17 '13 at 07:41
@Sylwester I link the nodes before even starting the test. During the test I ONLY iterate. — Acidic, Sep 17 '13 at 07:43
@Bart Friederichs yes and in the link I provided the answers say that sometimes recursion is slower. Although in this case none of the necessary conditions seem to apply. Besides, I run the code Acidic provided and in my case recursion is always almost exactly 2 times slower than iteration...? — Arie, Sep 17 '13 at 07:51

xanatos · Accepted Answer · 2013-09-17T08:56:35.673

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;
}

While testing this I noticed that the way I created by tree wasn't even depth-first, if you take a look at the code it's something slightly different. I fixed that, and now the iterative version really is faster - but only on 32 bit. On 64 bit the recursive version is slower for 'small' trees, but a tree with a depth of 10 or more still shows the recursive method to be just a little bit faster. I'll continue researching this for now. — Acidic, Sep 17 '13 at 10:24
Actually, I made a mistake in my code and it seems like the iterative version (with splitting fixed and your linking method) works faster in any and all conditions. Incredible, thanks a lot! — Acidic, Sep 17 '13 at 10:31

score 0 · Answer 2 · answered Sep 17 '13 at 07:09

Looking at your code, both methods seem to be working the same , BUT in the recursive one you visit 4 nodes in a "loop" , that means you do not "jump" between 3 tests whereas in the iterative you "jump" to the beginning of the loop each run. I'd say if you want to see almost similar behaviour you'll have to unroll the iterative loop into something like :

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

        node = node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;
        if (node!=null) node=node.next;

    }
}

loop unrolling is done by most of the modern compilers, and doing it manually just makes ur code more difficult to read. — Aleksander Fular, Sep 17 '13 at 07:29

Recursion faster than iteration

2 Answers2