42

As far as I know, most recursive functions can be rewritten using loops. Some may be harder than others, but most of them can be rewritten.

Under which conditions does it become impossible to rewrite a recursive function using a loop (if such conditions exist)?

Hosam Aly
  • 41,555
  • 36
  • 141
  • 182

10 Answers10

42

When you use a function recursively, the compiler takes care of stack management for you, which is what makes recursion possible. Anything you can do recursively, you can do by managing a stack yourself (for indirect recursion, you just have to make sure your different functions share that stack).

So, no, there is nothing that can be done with recursion and that cannot be done with a loop and a stack.

nbro
  • 15,395
  • 32
  • 113
  • 196
Carl Seleborg
  • 13,125
  • 11
  • 58
  • 70
  • 1
    I have a related question: can all recursive functions be represented as a **single loop**? – Abhinav Sarkar Jun 03 '10 at 11:48
  • 3
    @Abhinav: sorry to reply to a very old thread, but this caught my eye and there's a simple proof that the answer is yes: A Turing machine does everything it does by executing a single loop: 1. fetch an instruction, 2. evaluate it, 3. goto 1. – mokus Jan 21 '11 at 03:35
  • @mokus Your proof seems incomplete. The aim is to prove that every recursive function can be represented as a single loop. You're saying that a TM executes in a single loop. Where does recursion come into this? – Vicky Chijwani May 05 '13 at 23:45
  • 3
    @VickyChijwani: mokus' proof is perfectly complete for the scope he mentions, and less confusingly, he could have said, "all programs and subroutines are executed in a simple single loop...", so, recursion is an abstraction that takes care of stack management similar to how any higher level programming control construct is an abstraction for what the processor pipeline will eventually do, fetch instructions and execute them. So, at some level of removed abstractions, all programs are a single loop. – marr75 Jun 06 '14 at 20:16
  • 1
    Is *mostly* true. In other words it is not true. There are problems which cannot be done in loops, they have to be recursive. Rare, but they do exist https://www.youtube.com/watch?v=i7sm9dzFtEI – Chris Huang-Leaver Feb 27 '16 at 23:16
  • 1
    @ChrisHuang-Leaver you probably haven't googled "how to write akermann as loop". https://stackoverflow.com/questions/5605258/simple-loop-ackermann-function –  Jul 31 '17 at 13:12
16

Any recursive function can be made to iterate (into a loop) but you need to use a stack yourself to keep the state.

Normally, tail recursion is easy to convert into a loop:

A(x) {
  if x<0 return 0;
  return something(x) + A(x-1)
}

Can be translated into:

A(x) {
  temp = 0;
  for i in 0..x {
    temp = temp + something(i);
  }
  return temp;
}

Other kinds of recursion that can be translated into tail recursion are also easy to change. The other require more work.

The following: 

treeSum(tree) {
  if tree=nil then 0
  else tree.value + treeSum(tree.left) + treeSum(tree.right);
}

Is not that easy to translate. You can remove one piece of the recursion, but the other one is not possible without a structure to hold the state.

treeSum(tree) {
  walk = tree;
  temp = 0;
  while walk != nil {
    temp = temp + walk.value + treeSum(walk.right);
    walk = walk.left;
  }
}
Toon Krijthe
  • 52,876
  • 38
  • 145
  • 202
  • 2
    Your original tail-recursive example is not quite tail-recursive (but still illustrates the point that 'linear' recursion is often easy to translate, whereas higher arities are often not so easy). – Brian Feb 10 '09 at 09:51
  • Thanks. The last example seems to be what I am looking for. Is it really impossible to remove recursion from it? – Hosam Aly Feb 10 '09 at 09:52
  • 1
    No, you can always rewrite it with loops. It is almost mechanical to transform into code that uses continuations, which can be compiled into loops (not use the stack) in a language like F#, see e.g. http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!256.entry – Brian Feb 10 '09 at 09:56
  • 1
    Thank you. Your answer is very nice, but I chose Carl's answer because it's simpler (which is helpful to new readers of the thread). – Hosam Aly Feb 12 '09 at 20:34
10

Every recursive function can be implemented with a single loop.

Just think what a processor does, it executes instructions in a single loop.

starblue
  • 55,348
  • 14
  • 97
  • 151
  • Actually it doesn't work as a loop. The pipeline in a modern CPU is much more like a assembly line. Start at instruction one, go to the next instruction on the instruction pointer++. Some instructions modify the instruction pointer itself which results in a loop or a jump occuring. – Spence Sep 06 '12 at 13:00
  • It's a little more than just data. Most of the branch prediction cache runs off the position and previous future instructions based on the pointer. Although it can be modified through assembly, it's a fundamental part of the processor. – Spence Sep 09 '12 at 11:35
8

I don't know about examples where recursive functions cannot be converted to an iterative version, but impractical or extremely inefficient examples are:

  • tree traversal

  • fast Fourier

  • quicksorts (and some others iirc)

Basically, anything where you have to start keeping track of boundless potential states.

nbro
  • 15,395
  • 32
  • 113
  • 196
annakata
  • 74,572
  • 17
  • 113
  • 180
6

It's not so much a matter of that they can't be implemented using loops, it's the fact that the way the recursive algorithm works, it's much clearer and more concise (and in many cases mathematically provable) that a function is correct.

Many recursive functions can be written to be tail loop recursive, which can be optimised to a loop, but this is dependent on both the algorithm and the language used.

Spence
  • 28,526
  • 15
  • 68
  • 103
4

They all can be written as an iterative loop (but some might still need a stack to keep previous state for later iterations).

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
3

In SICP, the authors challenge the reader to come up with a purely iterative method of implementing the 'counting change' problem (here's an example one from Project Euler).

But the strict answer to your question was already given - loops and stacks can implement any recursion.

nbro
  • 15,395
  • 32
  • 113
  • 196
Eli Bendersky
  • 263,248
  • 89
  • 350
  • 412
3

One example which would be extremely difficult to convert from recursive to iterative would be the Ackermann function.

alt text

Community
  • 1
  • 1
1800 INFORMATION
  • 131,367
  • 29
  • 160
  • 239
  • 2
    Nice example. But a question remains: is it impossible, or just extremely difficult? – Hosam Aly Feb 10 '09 at 09:53
  • Not even too difficult if you know the general techniques. – Brian Feb 10 '09 at 09:59
  • 2
    I tried to do this, and it doesn't seem difficult to me. Check this code (and please tell me anything wrong with it): ... – Hosam Aly Feb 10 '09 at 12:47
  • 7
    push(m); push(n); while (stackSize > 1) { n = pop(); m = pop(); if (m == 0) push(n+1); else if (m > 0 && n == 0) { push(m-1); push(1); } else if (m > 0 && n > 0) { push(m-1); push(m); push(n-1); } } – Hosam Aly Feb 10 '09 at 12:49
  • It is impossible to implement because Ackermann function is not primitive recursive function. – yeachan park Aug 08 '22 at 07:34
  • @yeachanpark wrong: https://stackoverflow.com/questions/5605258/simple-loop-ackermann-function – underscore_d Apr 22 '23 at 23:31
3

Indirect recursion is still possible to convert to a non-recursive loop; just start with one of the functions, and inline the calls to the others until you have a directly recursive function, which can then be translated to a loop that uses a stack structure.

Miles
  • 31,360
  • 7
  • 64
  • 74
2

You can always use a loop, but you may have to create more data structure (e.g. simulate a stack).

Brian
  • 117,631
  • 17
  • 236
  • 300