Why should recursion be preferred over iteration?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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

Solution 4:

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.