Which recursive functions cannot be rewritten using loops? [duplicate]

recursion

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

Solution 1:

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.

Solution 2:

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;
  }
}

Solution 3:

Every recursive function can be implemented with a single loop.

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

Solution 4:

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.