Why should recursion be preferred over iteration ?

Question

Iteration is more performant than recursion, right? Then why do some people opine that recursion is better (more elegant, in their words) than iteration? I really don't see why some languages like Haskell do not allow iteration and encourage recursion? Isn't that absurd to encourage something that has bad performance (and that too when more performant option i.e. recursion is available) ? Please shed some light on this. Thanks.

Answer 1

Try implementing depth-first search recursively and iteratively and tell me which one gave you an easier time of it. Or merge sort. For a lot of problems it comes down to explicitly maintaining your own stack vs. leaving your data on the function stack.

I can't speak to Haskell as I've never used it, but this is to address the more general part of the question posed in your title.

Answer 2

Here is some information on the pros & cons of recursion & iteration in c:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

Mostly for me Recursion is sometimes easier to understand than iteration.

Answer 3

Haskell do not allow iteration because iteration involves mutable state (the index).

Answer 4

I don't think there's anything intrinsically less performant about recursion - at least in the abstract. Recursion is a special form of iteration. If a language is designed to support recursion well, it's possible it could perform just as well as iteration.

In general, recursion makes one be explicit about the state you're bringing forward in the next iteration (it's the parameters). This can make it easier for language processors to parallelize execution. At least that's a direction that language designers are trying to exploit.

Answer 5

Iteration is more performant than recursion, right?

Not necessarily. This conception comes from many C like languages, where calling a function, recursive or not, had a large overhead and created a new stackframe for every call.

For many languages this is not the case, and recursion is equally or more performant than an iterative version. These days, even some C compilers rewrite some recursive constructs to an iterative version, or reuse the stack frame for a tail recursive call.

Answer 6

As others have stated, there's nothing intrinsically less performant about recursion. There are some languages where it will be slower, but it's not a universal rule.

That being said, to me recursion is a tool, to be used when it makes sense. There are some algorithms that are better represented as recursion (just as some are better via iteration).

Case in point:

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

I can't imagine an iterative solution that could possibly make the intent clearer than that.

Answer 7

"Iteration is more performant than recursion" is really language- and/or compiler-specific. The case that comes to mind is when the compiler does loop-unrolling. If you've implemented a recursive solution in this case, it's going to be quite a bit slower.

This is where it pays to be a scientist (testing hypotheses) and to know your tools...

Answer 8

Several things:

1. Iteration is not necessarily faster
2. Root of all evil: encouraging something just because it might be moderately faster is premature; there are other considerations.
3. Recursion often much more succinctly and clearly communicates your intent
4. By eschewing mutable state generally, functional programming languages are easier to reason about and debug, and recursion is an example of this.

Answer 9

In Java, recursive solutions generally outperform non-recursive ones. In C it tends to be the other way around. I think this holds in general for adaptively compiled languages vs. ahead-of-time compiled languages.

Edit: By "generally" I mean something like a 60/40 split. It is very dependent on how efficiently the language handles method calls. I think JIT compilation favors recursion because it can choose how to handle inlining and use runtime data in optimization. It's very dependent on the algorithm and compiler in question though. Java in particular continues to get smarter about handling recursion.

Quantitative study results with Java (PDF link). Note that these are mostly sorting algorithms, and are using an older Java Virtual Machine (1.5.x if I read right). They sometimes get a 2:1 or 4:1 performance improvement by using the recursive implementation, and rarely is recursion significantly slower. In my personal experience, the difference isn't often that pronounced, but a 50% improvement is common when I use recursion sensibly.

Answer 10

I think it would help to get some understanding of what performance is really about. This link shows how a perfectly reasonably-coded app actually has a lot of room for optimization - namely a factor of 43! None of this had anything to do with iteration vs. recursion.

When an app has been tuned that far, it gets to the point where the cycles saved by iteration as against recursion might actually make a difference.

Answer 11

As a low level ITERATION deals with the CX registry to count loops, and of course data registries. RECURSION not only deals with that it also adds references to the stack pointer to keep references of the previous calls and then how to go back.-

My University teacher told me that whatever you do with recursion can be done with Iterations and viceversa, however sometimes is simpler to do it by recursion than Iteration (more elegant) but at a performance level is better to use Iterations.-

Answer 12

Recursion is the typical implementation of iteration. It's just a lower level of abstraction (at least in Python):

class iterator(object):
    def __init__(self, max):
        self.count = 0
        self.max = max

    def __iter__(self):
        return self

    # I believe this changes to __next__ in Python 3000
    def next(self):
        if self.count == self.max:
            raise StopIteration
        else:
            self.count += 1
            return self.count - 1

# At this level, iteration is the name of the game, but
# in the implementation, recursion is clearly what's happening.
for i in iterator(50):
    print(i)

Answer 13

Iteration is just a special form of recursion.