7

This question already has an answer here:

I am about to make two assumptions. Please correct me if they're wrong:

  1. There isn't a recursive algorithm without an iterative equivalent.
  2. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.).

If it's true that recursion is always more costly than iteration, and that it can always be replaced with an iterative algorithm (in languages that allow it) - than I think that the two remaining reasons to use recursion are: elegance and readability.

Some algorithms are expressed more elegantly with recursion. E.g. scanning a binary tree.

However apart from that, are there any reasons to use recursion over iteration? Does recursion have advantages over iteration other than sometimes elegance and readability?

marked as duplicate by gnat, Jörg W Mittag, Giorgio, user40980, mattnz Jun 4 '14 at 7:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • Try implementing QuickSort without recursion. It can be done -- I've done it -- but doing so will give you a better understanding of why recursion. – kdgregory Jun 3 '14 at 15:14
  • 1
    The recursive version can not only be more readable, it can also be more writable. While this is generally a lesser factor than readability (code is read far more often than it is written), it does matter since all good programmers are lazy ;-) The overarching advantage is that the recursive version is (usually) simpler, and this reflects on both reading and writing the code. – user7043 Jun 3 '14 at 15:26
  • 1
    Recursion lets you use immutable values. A loop is a statement and returns no value; the only way it can achieve anything useful is through side effects. Immutability in turn makes reasoning about code easier. – Doval Jun 3 '14 at 16:58
  • Iteration is a fixed control flow. Recursion may appear in a dynamic control flow (think virtual method calls), which is not possible to translate to iteration directly. – SK-logic Jun 3 '14 at 23:01
11

Well, it's usually less code.

And to the extent that it's less code, it's less error-prone.

In particular, recursion is very beneficial when the iterative solutions requires that you simulate recursion with a stack. Recursion acknowledges that the compiler already manages a stack to accomplish precisely what you need. When you start managing your own, not only are you likely re-introducing the function call overhead you intended to avoid; but you're re-inventing a wheel (with plenty of room for bugs) that already exists in a pretty bug-free form.

IMO, only eschew recursion if it can be done naturally and easily without a stack. (Or other non-scalar state and/or scope management structure.)

  • It's an old question but I wanted to ask something about this: you said "the compiler already manages a stack". Did you mean: "the runtime system [i.e. the VM or CPU] already manages a stack"? As far as I understand the compiler emits instructions that explicitly or implicitly manipulate the call stack (e.g. call func tells the VM or CPU before jumping to push the instruction pointer on the stack), but it doesn't itself manage a call stack. The call stack is implemented in the runtime system. Am I wrong? – Aviv Cohn Aug 22 '14 at 15:25
  • @Prog Really, all I meant is that the compiler writes the necessary instructions to work with and/or manage a stack. Whether the CPU and/or OS and/or VM you're targeting has built-in stack management is irrelevant. The compiler needs to know on some level how to work with that stack. And it generally does so without you needing to know about it. – svidgen Aug 22 '14 at 15:42
2

Recursion uses the call stack to store function call returns. Function state is stored in between calls.

Iteration must also use a stack or some similar mechanism to store intermediate states, except that you create the stack yourself. Unless, of course, you can find a substitute algorithm that doesn't require such state storage.

Recursion is only more costly if you overflow the stack. In a sense, iteration is going to be more costly (in those algorithms that lend themselves to recursion), because you're re-creating the state storage mechanism that recursion already provides.

  • 1
    'Recursion is only more costly if you overflow the stack.' - you sure? Pretty much everybody says recursion is more costly in general, not only in the case of Stack Overflows. – Aviv Cohn Jun 3 '14 at 15:14
  • 4
    [citation-needed.] Function calls are not that expensive in most languages. – Robert Harvey Jun 3 '14 at 15:15
  • 2
    In a language without tail calls, wouldn't pushing an entire stack frame for each recursive call be more expensive than, say, manually pushing a single element of whatever you're working with onto your own, manually maintained stack? – KChaloux Jun 3 '14 at 15:21
  • 2
    @RobertHarvey Function calls are not expensive, but they are almost always more expensive than merely going back to the start of the loop body. jmp vs (push r1, r2 and jmp) in C, "set up a whole frame object" versus "change the interpreter's instruction pointer" in CPython. A function call simply needs to do more than a loop backedge. The more important question then is whether you can do the required state management more effectively than the language implementation. – user7043 Jun 3 '14 at 15:23
  • 2
    @delnan: It's all academic if the expense won't matter anyway. – Robert Harvey Jun 3 '14 at 15:24
2

First, while it is true that there always exists an equivalent iterative equivalent to any recursive algorithm, it is not necessarily the case that the iterative equivalent is better, for any reasonable definition of "better".

For some algorithms, the iterative equivalent winds up just simulating the recursive algorithm, complete with simulated parameter and local variable stacking and unstacking. Consider Ackermann's Function. Consider Huffman coding. In these cases, there is very little gained by (re)writing the explicit stack operations.

Second, it is not necessarily the case that recursion is always more expensive than iteration. Consider tail recursion, and read the "Lambda: The Ultimate..." papers.

(Yes, I know this needs expansion. I have to go to a doctor's appointment right now.)

Not the answer you're looking for? Browse other questions tagged or ask your own question.