Why should recursion be preferred over iteration?

performance language-agnostic recursion iteration
Debashish12 picture Debashish12 · Feb 2, 2010 · Viewed 55.1k times · Source

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

nos picture nos · Feb 2, 2010

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.

Related questions

Recursion or Iteration?

Is there a performance hit if we use a loop instead of recursion or vice versa in algorithms where both can serve the same purpose? Eg: Check if the given string is a palindrome. I have seen many programmers using …

Read More
Performance optimization strategies of last resort

There are plenty of performance questions on this site already, but it occurs to me that almost all are very problem-specific and fairly narrow. And almost all repeat the advice to avoid premature optimization. Let's assume: the code already is …

Read More
What is the fastest way to get the value of π?

I'm looking for the fastest way to obtain the value of π, as a personal challenge. More specifically, I'm using ways that don't involve using #define constants like M_PI, or hard-coding the number in. The program below tests the various …

Read More