CODEWITHSUNDEEP
performancerecursion
user514088
user514088

Reputation: 11

When is recursion better than iteration?

In my understanding, generally, recursive solutions are looked down upon since recursion usually takes a large chunk of memory while iterative solutions are more efficient in that sense.

What level of elegance must a solution have in order for its recursive implementation to be more generally accepted than its iterative implementation?

For example, an iterative implementation of the Tower of Hanoi problem is absolutely atrocious, yet its recursive implementation is almost awe-inspiringly elegant. I would never code Hanoi using an iterative implementation just because it is so tedious.

For trees and other recursively defined data structures, recursion is more elegant, but are we wasting space? Should we represent the tree as an array and use some nasty indices in order to achieve optimal performance?

Upvotes: 1

Views: 517

Answers (1)

J_H
J_H

Reputation: 20435

Cite your references, please. Who is "looking down" upon certain solutions?

One can solve the Tower of Hanoi problem in multiple ways in C, as there is language support for stack allocated locals. Without such language support, application code would have to manage user-allocated stacks, at the cost of making the code less concise and less clear to the casual reader.

You seem to be looking at two distinct metrics: machine performance (time + space), and maintainability. Typically you should optimize for maintainability, for minimizing hours needed for a skilled programmer to analyze your code in order to add a feature or repair a bug. Start worrying about machine performance when excessive running time gets in the way of achieving some business goal. By the time your code is mature enough that optimizing 50% out of a 100 msec running time becomes worth it, you'll have lots of business drivers giving you guidance to help you decide.

Upvotes: 1

Related Questions