Databases
StackOverflow2013
Postsdbo
PORecursion faster than iteration
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORecursion faster than iteration
    primarykey
    data
    text
    <p>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.</p> <p>My nodes look like this:</p> <pre><code>class QuadNode { private QuadNode topLeft; private QuadNode topRight; private QuadNode bottomRight; private QuadNode bottomLeft; // other fields... } </code></pre> <p>To traverse the tree I used the following recursive method, which I invoke on the root node:</p> <pre><code>Traverse() { // visit 'this' if (topLeft != null) topLeft.Traverse(); if (topRight != null) topRight.Traverse(); if (bottomRight != null) bottomRight.Traverse(); if (bottomLeft != null) bottomLeft.Traverse(); } </code></pre> <p>Mostly out of interest, I tried to create an iterative method for traversing the tree.</p> <p>I added the following field to each node: <code>private QuadNode next</code>, and when I create the tree I perform a breadth-first traversal using a queue, linking the <code>next</code> field of each node to the next node in line. Essentially I created a singly-linked list from the nodes of the tree.<br> At this point I am able to traverse the tree with the following method:</p> <pre><code>Traverse() { QuadNode node = this; while (node != null) { // visit node node = node.next; } } </code></pre> <p>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 a<code>Stopwatch</code> for benchmarking) <br> <strong>I've confirmed that both methods traverse the entire tree successfully and that the iterative version only visits each node exactly once as planned</strong>, so it's not a problem with the linking between them.<br></p> <p>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?</p> <p><sub>I'm using Visual Studio 2012 and Compiled under Release, Any CPU (prefer 32 bit unchecked).</sub></p> <p><strong>Edit:</strong><br> I've opened a new project and created a simple test which also confirms my results.<br> Here's the full code: <a href="http://pastebin.com/SwAsTMjQ" rel="nofollow">http://pastebin.com/SwAsTMjQ</a><br> The code isn't commented but I think it's pretty self-documenting.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMaher
    1. USAcidic
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PORecursion faster than iteration
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PORecursion faster than iteration
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PORecursion faster than iteration
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhere are the results of your measurements?
      singulars
      1. PORecursion faster than iteration
      1. USTim Schmelter
    2. COhttp://stackoverflow.com/questions/72209/recursion-or-iteration , http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping/2651200#2651200
      singulars
      1. PORecursion faster than iteration
      1. USArie
    3. CO@Arie what he sees is exactly opposite, hence his question. In his case iteration is **slower**.
      singulars
      1. PORecursion faster than iteration
      1. USBart Friederichs
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload