Recursion vs loops

Question

I'm facing a problem where both recursion and using a loop seem like natural solutions. Is there a convention or "preferred method" for cases like this? (Obviously it is not quite as simple as below)

Recursion

Item Search(string desired, Scope scope) {     foreach(Item item in scope.items)         if(item.name == desired)             return item;      return scope.Parent ? Search(desired, scope.Parent) : null; } 

Loop

Item Search(string desired, Scope scope) {     for(Scope cur = scope; cur != null; cur = cur.Parent)         foreach(Item item in cur.items)             if(item.name == desired)                 return item;      return null; } 

Answer 1

I favor recursive solutions when:

• The implementation of the recursion is much simpler than the iterative solution, usually because it exploits a structural aspect of the problem in a way that the iterative approach cannot

• I can be reasonably assured that the depth of the recursion will not cause a stack overflow, assuming we're talking about a language that implements recursion this way

Condition 1 doesn't seem to be the case here. The iterative solution is about the same level of complexity, so I'd stick with the iterative route.

Answer 2

If performance matters, then benchmark both and choose on a rational basis. If not, then choose based on complexity, with concern for possible stack overflow.

There is a guideline from the classic book The Elements of Programming Style (by Kernighan and Plauger) that algorithm should follow data structure. That is, recursive structures are often processed more clearly with recursive algorithms.