.NET Performance: Deep Recursion vs Queue

I'm writing a component that needs to walk large object graphs, sometimes 20-30 levels deep.

What is the most performant way of walking the graph?

A. Enqueueing "steps" so as to avoid deep recursion

or

B. A DFS (depth first search) which may step many levels deep and have a "deep" stack trace at times.

I guess the question I'm asking is: Is there a performance hit in .NET for doing a DFS that causes a "deep" stack trace? If so, what is the hit? And would I better better off with some BFS by me开发者_Python百科ans of queueing up steps that would have been handled recursively in a DFS?

Sorry if I'm being unclear. Thanks.

There's nothing in the runtime that would cause code execution in a deep stack to be slower than in a shallow call stack. There's no reason for that, because usually code execution doesn't trigger a stack walk.

When I say usually, this means there are a couple of exceptions:

• Security/Evidence checks do usually walk the call stack to determine the current security context
• Throwing and catching exceptions of course (you don't want to do that in a tree traversal anyway, except for aborting it)

Whether you should implement an iterative or recursive tree traversal isn't dependent on whether the .NET runtime will give you better perfomance in one scenario vs. the other, but you should make your decision based on Big-O (time and memory), especially if its for large trees. I don't think I need to remind you of the chance of a stack overflow with a recursive solution, given where we are... Tailcall optimization is possible though.

After you've chosen the fastest traversal for your tree and traversal purpose Big-O wise, you can start worrying about optimizing your implementation.

See Why doesn't .NET/C# optimize for tail-call recursion?. Apparently, .NET performs tail recursion optimization on x86-64, so if that's your architecture, and your code is amenable to such an optimization, stick with recursion.

You're mingling two concepts which ought to be separate to some degree:

• Iteration of a data structure vs. using recursive functions where the call stack becomes your structure.

• Breadth-first vs depth-first traversal.

They are connected, insofar as recursive functions tend to implement depth-first. However, when using a queue, there's nothing restricting you to breadth-first.

Use a FIFO queue if you want breadth-first, and a LIFO queue if you want depth first. Either way, you save the function call overhead (probably fairly minor, and calling methods on the queue may well be more expensive if they don't get inlined by the optimizer) and the stack space usage on the system call stack.