performance - Is recursion ever faster than looping? -

i know recursion lot cleaner looping, , i'm not asking when should use recursion on iteration, know there lots of questions already.

what i'm asking is, recursion ever faster loop? me seems like, able refine loop , perform more recursive function because loop absent setting new stack frames.

i'm looking whether recursion faster in applications recursion right way handle data, such in sorting functions, in binary trees, etc.

this depends on language being used. wrote 'language-agnostic', i'll give examples.

in java, c, , python, recursion expensive compared iteration (in general) because requires allocation of new stack frame. in c compilers, 1 can use compiler flag eliminate overhead, transforms types of recursion (actually, types of tail calls) jumps instead of function calls.

in functional programming language implementations, sometimes, iteration can expensive , recursion can cheap. in many, recursion transformed simple jump, changing loop variable (which mutable) sometimes requires relatively heavy operations, on implementations support multiple threads of execution. mutation expensive in of these environments because of interaction between mutator , garbage collector, if both might running @ same time.

i know in scheme implementations, recursion faster looping.

in short, answer depends on code , implementation. use whatever style prefer. if you're using functional language, recursion might faster. if you're using imperative language, iteration probably faster. in environments, both methods result in same assembly being generated (put in pipe , smoke it).

addendum: in environments, best alternative neither recursion nor iteration instead higher order functions. these include "map", "filter", , "reduce" (which called "fold"). not these preferred style, not cleaner, in environments these functions first (or only) boost automatic parallelization — so can faster either iteration or recursion. data parallel haskell example of such environment.

list comprehensions alternative, these syntactic sugar iteration, recursion, or higher order functions.