127

There are times where using recursion is better than using a loop, and times where using a loop is better than using recursion. Choosing the "right" one can save resources and/or result in fewer lines of code.

Are there any cases where a task can only be done using recursion, rather than a loop?

  • 13
    I seriously doubt it. Recursion is a glorified loop. – Lightness Races with Monica Nov 22 '15 at 5:06
  • 6
    Seeing the diverging directions into which the answers go (and having just failed myself at providing a better one) you might do anyone trying to answer a favor if you provide a bit more background and what kind of answer you are after. Do you want a theoretical proof for hypothetical machines (with unlimited storage and run-time)? Or practical examples? (Where “would be ridiculously complicated” might qualify as “can't be done”.) Or something different? – 5gon12eder Nov 22 '15 at 6:51
  • 8
    @LightnessRacesinOrbit To my non-native-English-speaker ear, "Recursion is a glorified loop" sounds you mean "You might as well use a looping construct instead of recursive call anywhere, and the concept doesn't really deserve it's own name". Perhaps I interpret the "glorified something" idiom wrong, then. – hyde Nov 22 '15 at 15:24
  • 13
    What about Ackermann function? en.wikipedia.org/wiki/Ackermann_function, not particularly useful but impossible to do via looping. (You may also want to check this video youtube.com/watch?v=i7sm9dzFtEI by Computerphile) – WizardOfMenlo Nov 22 '15 at 21:12
  • 8
    @WizardOfMenlo the befunge code is a implementation of the ERRE solution (which is also an interactive solution... with a stack). An iterative approach with a stack can emulate a recursive call. On any programming that is suitably powerful, one looping construct can be used to emulate another one. The register machine with the instructions INC (r), JZDEC (r, z) can implement a Turing machine. It has no 'recursion' - thats a Jump if Zero else DECrement. If the Ackermann function is computable (it is), that register machine can do it. – user40980 Nov 22 '15 at 22:23

11 Answers 11

164

Yes and no. Ultimately, there's nothing recursion can compute that looping can't, but looping takes a lot more plumbing. Therefore, the one thing recursion can do that loops can't is make some tasks super easy.

Take walking a tree. Walking a tree with recursion is stupid-easy. It's the most natural thing in the world. Walking a tree with loops is a lot less straightforward. You have to maintain a stack or some other data structure to keep track of what you've done.

Often, the recursive solution to a problem is prettier. That's a technical term, and it matters.

  • 120
    Basicly, doing loops instead of recursion means to manually handle the stack. – Silviu Burcea Nov 22 '15 at 6:27
  • 15
    ... the stack(s). The following situation may strongly prefer having more than one stack. Consider one recursive function A that finds something in a tree. Everytime A encounters that thing, it launches another recursive function B which finds a related thing in the subtree at the position where it was launched by A. Once B finishes the recursion it returns to A, and the latter continues its own recursion. One may declare one stack for A and one for B, or put the B stack inside the A loop. If one insists using a single stack, things get really complicated. – rwong Nov 22 '15 at 6:48
  • 35
    Therefore, the one thing recursion can do that loops can't is make some tasks super easy. And the one thing that loops can do that recursion can't is make some tasks super easy. Have you seen the ugly, unintuitive things you have to do to transform most naturally-iterative problems from naive recursion to tail recursion so they won't blow the stack? – Mason Wheeler Nov 22 '15 at 17:29
  • 10
    @MasonWheeler 99% of the time those "things" can be better encapsulated inside a recursion-operator like map or fold (in fact if you choose to consider them primitives, I think you can use fold/unfold as a third alternative to loops or recursion). Unless you're writing library code there aren't that many cases where you should be worrying about the implementation of the iteration, rather than the task it's supposed to be accomplishing - in practice, that means explicit loops and explicit recursion are both equally poor abstractions that should be avoided at the top level. – Leushenko Nov 22 '15 at 18:06
  • 7
    You could compare two strings by recursively comparing substrings, but just comparing each character, one-by-one, until you get a mismatch is apt to perform better and be more clear to the reader. – Gort the Robot Nov 22 '15 at 18:35
78

No.

Getting down to the very basics of the necessary minimums in order to compute, you just need to be able to loop (this alone isn't sufficient, but rather is a necessary component). It doesn't matter how.

Any programming language that can implement a Turing Machine, is called Turing complete. And there are lots of languages that are turing complete.

My favorite language in the way down there of "that actually works?" Turing completeness is that of FRACTRAN, which is Turing complete. It has one loop structure, and you can implement a Turing machine in it. Thus, anything that is computable, can be implemented in a language that doesn't have recursion. Therefore, there is nothing that recursion can give you in terms of computability that simple looping cannot.

This really boils down to a few points:

  • Anything that is computable is computable on a Turing machine
  • Any language that can implement a Turing machine (called Turing complete), can compute anything that any other language can
  • Since there are Turing machines in languages that lack recursion (and there are others that only have recursion when you get into some of the other esolangs), it is necessarily true that there is nothing that you can do with recursion that you cannot do with a loop (and nothing you can do with a loop that you can't do with recursion).

This isn't to say that there are some problem classes that more easily be thought of with recursion rather than with looping, or with looping rather than with recursion. However, these too tools are equally powerful.

And while I took this to the 'esolang' extreme (mostly because you can find things that are Turing complete and implemented in rather strange ways), this doesn't mean that the esolangs are by any means optional. There is a whole list of things that are accidentally Turing complete including Magic the Gathering, Sendmail, MediaWiki templates, and the Scala type system. Many of these are far from optimal when it comes to actually doing anything practical, its just that you can compute anything that is computable using these tools.


This equivalence can get particularly interesting when you get into a particular type of recursion known as tail call.

If you have, lets say, a factorial method written as:

int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

This type of recursion will be rewritten as a loop - no stack used. Such approaches are indeed often more elegant and easier to understand than the equivalent loop being written, but again, for every recursive call there can be an equivalent loop written and for every loop there can be a recursive call written.

There are also times where converting the simple loop into a tail call recursive call can be convoluted and more difficult to understand.


If you want to get into the theory side of it, see the Church Turing thesis. You may also find the church-turing-thesis on CS.SE to be useful.

  • 29
    Turing completeness is thrown around too much like it matters. A lot of things are Turing Complete (like Magic the Gathering), but that doesn't mean it's the same as something else that's Turing Complete. At least not at a level that matters. I don't want to walk a tree with Magic the Gathering. – Scant Roger Nov 22 '15 at 6:03
  • 7
    Once you can reduce a problem to "this has equal power to a Turing machine" it is enough to get it there. Turing machines are a rather low hurdle, but it's all that is needed. There is nothing a loop can do that recursion cannot do, nor vice versa. – user40980 Nov 22 '15 at 6:06
  • 4
    The statement made in this answer is of course correct, but I dare to say that the argument is not really convincing. Turing machines have no direct concept of recursion so saying “you can simulate a Turing machine without recursion” doesn't really prove anything. What you'd have to show in order to prove the statement is that Turing machines can simulate recursion. If you don't show this, you have to faithfully assume that the Church-Turing hypothesis also holds for recursion (which it does) but the OP questioned this. – 5gon12eder Nov 22 '15 at 6:25
  • 10
    The OP's question is "can", not "best", or "most efficiently" or some other qualifier. "Turing Complete" means anything that can be done with recursion can also be done with a loop. Whether that is the best way to do it in any particular language implementation is an entirely different question. – Gort the Robot Nov 22 '15 at 17:00
  • 7
    "Can" is very much NOT the same thing as "best". When you mistake "not best" for "can't", you become paralyzed because no matter what way you do something, there's nearly always a better way. – Gort the Robot Nov 22 '15 at 18:31
31

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: No, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps? And the answer to that is: No, it still isn't called recursion, it is called iteration with explicit stack (if you want to use established terminology).


Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

So let's consider question, are there general tasks, for which there are only recursion-like algorithms. From comment of @WizardOfMenlo under the question, Ackermann function is a simple example of that. So the concept of recursion stands on its own, even if it can be implemented with a different computer program construct (iteration with explicit stack).

  • 2
    When dealing with an assembly for a stackless processor, these two techniques suddenly become one. – Joshua Nov 24 '15 at 18:59
  • @Joshua Indeed! It is a matter of level of abstraction. If you go a level or two lower, it's just logic gates,. – hyde Nov 24 '15 at 20:51
  • 2
    That's not quite correct. To emulate recursion with iteration, you need a stack where random access is possible. A single stack without random access plus a finite amount of directly-accessible memory would be a PDA, which is not Turing-complete. – Gilles 'SO- stop being evil' Nov 24 '15 at 22:06
  • @Gilles Old post, but why is random access stack needed? Also, aren't all real computers then even less than PDAs, as they have only finite amount of directly accessible memory, and no stack at all (except by using that memory)? This doesn't seem very practical abstraction, if it says "we can't do recursion in reality". – hyde Apr 5 at 8:01
20

It depends on how strictly you define "recursion".

If we strictly require it to involve the call-stack (or whatever mechanism for maintaining program state is used), then we can always replace it with something that doesn't. Indeed, languages that lead naturally to heavy use of recursion tend to have compilers that make heavy use of tail-call optimisation, so what you write is recursive but what you run is iterative.

But lets consider a case where we make a recursive call and use the result of a recursive call for that recursive call.

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Making the first recursive call iterative is easy:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

We can then clean-up remove the goto to ward off velociraptors and the shade of Dijkstra:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

But to remove the other recursive calls we're going to have to store the values of some calls into a stack:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

Now, when we consider the source code, we have certainly turned our recursive method into an iterative one.

Considering what this has been compiled to, we have turned code that uses the call stack to implement recursion into code that does not (and in doing so turned code that will throw a stack-overflow exception for even quite small values into code that will merely take an excruciatingly long time to return [see How can I prevent my Ackerman function from overflowing the stack? for some further optimisations that make it actually return for many more possible inputs]).

Considering how recursion is implemented generally, we have turned code that uses the call-stack into code that uses a different stack to hold pending operations. We could therefore argue that it is still recursive, when considered at that low level.

And at that level, there are indeed no other ways around it. So if you do consider that method to be recursive, then there are indeed things we cannot do without it. Generally though we do not label such code recursive. The term recursion is useful because it covers a certain set of approaches and gives us a way to talk about them, and we are no longer using one of them.

Of course, all of this assumes you have a choice. There are both languages that prohibit recursive calls, and languages that lack the looping structures necessary for iterating.

  • It's only possible to replace the call stack with something equivalent if either the call stack is bounded or one has access to an unbounded memory outside the call stack. There is a significant class of problems which are solvable by push-down automata which have an unlimited call stack but can only have a finite number of states otherwise. – supercat Nov 24 '15 at 0:10
  • This is the best answer, perhaps the only correct answer. Even the second example is still recursive, and at this level, the answer to the original question is no. With a broader definition of recursion, recursion for the Ackermann function is impossible to avoid. – gerrit Nov 24 '15 at 10:26
  • @gerrit and with a narrower, it does avoid it. Ultimately it comes down to the edges of just what we do or do not apply this useful label we use for certain code to. – Jon Hanna Nov 24 '15 at 10:34
  • 1
    Joined the site to up vote this. The Ackermann function /is/ recursive in nature. Implementing a recursive structure with a loop and a stack does not make it an iterative solution, you've just moved the recursion into userspace. – Aaron McMillin Nov 25 '15 at 16:22
9

The classical answer is "no", but allow me to elaborate on why I think "yes" is a better answer.


Before going on, let's get something out of the way: from a computability & complexity standpoint:

  • The answer is "no" if you are permitted to have an auxiliary stack when looping.
  • The answer is "yes" if you are not permitted any extra data when looping.

Okay, now, let's put one foot in practice-land, keeping the other foot in theory-land.


The call stack is a control structure, whereas a manual stack is a data structure. Control and data are not equal concepts, but they're equivalent in the sense that they can be reduced to each other (or "emulated" via one another) from a computability or complexity standpoint.

When might this distinction matter? When you're working with real-world tools. Here's an example:

Say you're implementing N-way mergesort. You might have a for loop that goes through each of the N segments, calls mergesort on them separately, then merges the results.

How might you parallelize this with OpenMP?

In the recursive realm, it's extremely simple: just put #pragma omp parallel for around your loop that goes from 1 to N, and you're done. In the iterative realm, you can't do this. You have to spawn threads manually and pass them the appropriate data manually so that they know what to do.

On the other hand, there are others tools (such as automatic vectorizers, e.g. #pragma vector) that work with loops but are utterly useless with recursion.

Point being, just because you can prove the two paradigms are equivalent mathematically, that doesn't mean they are equal in practice. A problem that might be trivial to automate in one paradigm (say, loop parallelization) might be much more difficult to solve in the other paradigm.

i.e.: Tools for one paradigm do not automatically translate to other paradigms.

Consequently, if you require a tool to solve a problem, chances are that the tool will only work with one particular kind of approach, and consequently you will fail to solve the problem with a different approach, even if you can mathematically prove the problem can be solved either way.

  • Even beyond that, consider that the set of problems that can be solved with a push-down automaton is larger than the set which can be solved with a finite automaton (whether deterministic or non) but smaller than the set which can be solved with a Turing machine. – supercat Nov 24 '15 at 23:30
8

Setting aside theoretical reasoning, let's have a look at what recursion and loops look like from a (hardware or virtual) machine point of view. Recursion is a combination of control flow that allows to start execution of some code and to return on completion (in a simplistic view when signals and exceptions are ignored) and of data that is passed to that other code (arguments) and that is returned from it (result). Usually no explicit memory management is involved, however there is implicit allocation of stack memory to save return addresses, arguments, results and intermediate local data.

A loop is a combination of control flow and local data. Comparing this to recursion we can see that the amount of data in this case is fixed. The only way to break this limitation is to use dynamic memory (also known as heap) that can be allocated (and freed) whenever needed.

To summarize:

  • Recursion case = Control flow + Stack (+ Heap)
  • Loop case = Control flow + Heap

Assuming that control flow part is reasonably powerful, the only difference is in available memory types. So, we are left with 4 cases (expressiveness power is listed in parentheses):

  1. No stack, no heap: recursion and dynamic structures are impossible. (recursion = loop)
  2. Stack, no heap: recursion is OK, dynamic structures are impossible. (recursion > loop)
  3. No stack, heap: recursion is impossible, dynamic structures are OK. (recursion = loop)
  4. Stack, heap: recursion and dynamic structures are OK. (recursion = loop)

If rules of the game are a bit stricter and recursive implementation is disallowed to use loops, we get this instead:

  1. No stack, no heap: recursion and dynamic structures are impossible. (recursion < loop)
  2. Stack, no heap: recursion is OK, dynamic structures are impossible. (recursion > loop)
  3. No stack, heap: recursion is impossible, dynamic structures are OK. (recursion < loop)
  4. Stack, heap: recursion and dynamic structures are OK. (recursion = loop)

The key difference with the previous scenario is that lack of stack memory does not allow recursion without loops to do more steps during execution than there are lines of code.

2

Yes. There are several common tasks that are easy to accomplish using recursion but impossible with just loops:

  • Causing stack overflows.
  • Totally confusing beginner programmers.
  • Creating fast looking functions that actually are O(n^n).
  • 3
    Please, these are really easy with loops, I see them all the time. Heck, with a bit of effort you don't even need the loops. Even if recursion is easier. – AviD Nov 24 '15 at 10:10
  • 1
    actually, A(0,n)=n+1; A(m,0)=A(m-1,1) if m>0; A(m,n) = A(m-1,A(m,n-1)) if m>0,n>0 grows even a bit faster than O(n^n) (for m=n) :) – John Donn Nov 24 '15 at 11:31
  • 1
    @JohnDonn More than a bit, it's super exponential. for n=3 n^n^n for n=4 n^n^n^n^n and so on. n to the n power n times. – Aaron McMillin Nov 25 '15 at 16:25
1

There's a difference between recursive functions and primitive recursive functions. Primitive recursive functions are those that are calculated using loops, where the maximum iteration count of each loop is calculated before the loop execution starts. (And "recursive" here has nothing to do with the use of recursion).

Primitive recursive functions are strictly less powerful than recursive functions. You would get the same result if you took functions that use recursion, where the maximum depth of the recursion has to be calculated beforehand.

  • 3
    I'm not sure how this applies to the question above? Can you please make that connection more clear? – Yakk Nov 23 '15 at 15:49
  • 1
    Replacing the imprecise "loop" with the important distinction between "loop with limited iteration count" and "loop with unlimited iteration count", which I thought everyone would know from CS 101. – gnasher729 Nov 29 '15 at 0:30
  • sure, but it still doesn't apply to the question. The question is about looping and recursion, not primitive recursion and recursion. Imagine if someone asked about C/C++ differences, and you answered about the difference between K&R C and Ansi C. Sure that makes things more precise, but it does not answer the question. – Yakk Nov 29 '15 at 1:40
1

If you are programming in c++, and use c++11, then there is one thing that has to be done using recursions : constexpr functions. But the standard limits this to 512, as explained in this answer. Using loops in this case is not possible, since in that case the function can not be constexpr, but this is changed in c++14.

0
  • If the recursive call is the very first or very last statement(excluding condition checking) of a recursive function, it is pretty easy to translate into a looping structure.
  • But if the function does some other things before and after the recursive call, then it would be cumbersome to convert it to loops.
  • If the function have multiple recursive calls, the converting it to code which is using just loops will be pretty much impossible. Some stack will be needed to keep up with the data. In recursion the call-stack itself will work as the data-stack.
  • Tree walking has multiple recursive calls (one for each child), yet it's trivially transformed into a loop using an explicit stack. Parsers on the other hand are often annoying to transform. – CodesInChaos Nov 27 '15 at 9:37
  • @CodesInChaos Edited. – Gulshan Nov 27 '15 at 9:47
-6

I agree with the other questions. There is nothing you can do with recursion you can't do with a loop.

BUT, in my opinion recursion can be very dangerous. First, for some its more difficult to understand what is actually happening in the code. Second, at least for C++ (Java I am not sure) each recursion step has an impact on the memory because each method call causes memory accumulation and initialization of the methods header. This way you can blow up your stack. Simply try recursion of the Fibonacci numbers with a high input value.

  • 2
    A naive recursive implementation of Fibonacci numbers with recursion will run "out of time" before it runs out of stack space. I guess there are other problems which are better for this example. Also, for many problems a loop version has just the same memory impact as a recursive one, just on the heap instead of the stack (if your programming language distinguishes those). – Paŭlo Ebermann Nov 22 '15 at 10:27
  • 6
    Loop can also be "very dangerous" if you just forget to increment the loop variable ... – h22 Nov 22 '15 at 12:05
  • 2
    So, indeed, deliberately producing a stack overflow is a task that becomes very tricky without using recursion. – 5gon12eder Nov 22 '15 at 20:16
  • @5gon12eder which brings us to What methods are there to avoid a stack overflow in a recursive algorithm? - writing to engage TCO, or Memoisation can be useful. Iterative vs. Recursive Approaches is also interesting as it deals with two different recursive approaches for Fibonacci. – user40980 Nov 22 '15 at 20:29
  • 1
    Most of the time if you do get a stack overflow on recursion, you would have had a hang on the iterative version. At least the former throws with a stack trace. – Jon Hanna Nov 23 '15 at 13:17

protected by Community Nov 22 '15 at 20:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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