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?

  • 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
  • 2
    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
  • Odd question. Iteration and recursion are not logically equivalent and thus pointless to compare as such. – Martin Maat Sep 4 '19 at 7:58

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
  • But wouldn't you be scared that you will get a StackOverflow error when using recursion? From online, it seems that 256k is default depth for stack size in compilers usually. But with iterative solutions, int(or even long) size is much more than 256k. Maybe I am thinking this in a wrong way and making wrong assumptions. Thanks – theprogrammer Jun 24 '20 at 0:43
  • Not really. My answer assumes you're dealing with a problem that feels natural to think about recursively, with the point being don't pass the recursive solution up unless the iterative solution is somehow "better". Not blowing the stack is definitively better if your data, structure, and algorithm lead to deep calls without potential for tail call optimization. – svidgen Jun 24 '20 at 13:43

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
  • 3
    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
  • 3
    @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

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.)

OK, there are some things that can be said.

Tony Hoare originally described Quicksort iteratively, and he reported that it was very difficult to explain. Explained recursively, it is SIMPLE. See Quicksort in Haskell for the details. If the array has length equal to one, you are finished, otherwise, you actually have to sort it. First, you pick a pivot element. Traditionally, this is the first element, but any element can be used. Next, you take a pass over the array, to form three subarrays. The first is all elements less than the pivot, the second is all elements equal to the pivot, and the third is all elements greater than the pivot. (If the array element values are required to be unique, then the length of the second subarray is equal to one.) Now quicksort the first subarray, and then quicksort the second subarray.

Binary search is easiest to understand when presented recursively, and it is in fact tail-recursive. You probe the middle element of the array. If it is equal to the value you are looking for, you are done. If the middle element is greater than the value you seek, then you know that the desired value must lie "to the left", and you search the subarray before the middle element, otherwise you search the subarray after the middle element. In both cases, you know that the middle element is not the target, so you leave it out. You either find your target, or you run out of array to search. At that point, you bail all the way out, and you're done. In the year 2014, never mind 2019, any self-respecting compiler knows how to do tail recursion optimization, even Java compilers. (Note: The classic Java virtual machine does not support general tail call optimization, for lack of a general GOTO operation, but that does not affect tail recursion optimization.)

The real problem, a lot of places, is that the people running the show never learned about tail recursion optimization, and so they ban all recursion. I ran into this at Nortel Networks, and had to write a full page of comments explaining it and some related concepts AND show them the assembly language listings that proved the compiler was NOT actually generating recursive calls. Nortel is gone now, but those managers still exist in a lot of places.

Hope this helps.

  • I waited 5 years for the expansion. Am dissapointed. – NoName Sep 4 '19 at 3:04

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