Which recursive functions cannot be rewritten using loops?

0 votes
asked Feb 10, 2009 by hosam-aly

As far as I know, most recursive functions can be rewritten using loops. Some maybe 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)?

11 Answers

0 votes
answered Jan 8, 2009 by eli-bendersky

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.

0 votes
answered Jan 10, 2009 by michael-burr

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

0 votes
answered Jan 10, 2009 by brian

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

0 votes
answered Jan 10, 2009 by spence

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.

0 votes
answered Jan 10, 2009 by hosam-aly

Indirect recursion comes to mind...

Edit: Mile's answer shows how to inline indirect recursion, so I was wrong.

0 votes
answered Jan 10, 2009 by annakata

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.

0 votes
answered Jan 10, 2009 by toon-krijthe

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;
  }
}
0 votes
answered Jan 10, 2009 by 1800-information

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

alt text

0 votes
answered Jan 10, 2009 by miles

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.

0 votes
answered Jan 10, 2009 by starblue

Every recursive function can be implemented with a single loop.

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

Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...