Loop optimization of non-tail recursion

Question

When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form:

fn F(x):
  if p(x):
    return F(a(x))
  else:
    return b(x)

Then it may be written as:

fn F(x):
  while p(x):
    x = a(x)
  return b(x)

However, I was wondering about how to do this if the recursion is not in tail call position, i.e. the value is modified after the recursive call like this:

fn F(x):
  if p(x):
    return h(F(a(x)))
  else:
    return b(x)

And I came upon this solution:

fn F(x):
  i = 0
  while p(x):
    x = a(x)
    i++
  x = b(x)
  repeat i times:
    x = h(x)
  return x

Are those two functions equivalent in functionality? Furthermore, is there a general way to make a recursive function into a loop?

Answer 1

One systematic way to analyze these problems is to rewrite the function in continuation-passing style. For our purposes this means that the function takes an extra argument which is another function describing the postprocessing that is to be applied to the returned value. Your third function F in continuation-passing style would look like

fn F(x, k):
  if p(x):
    return F(a(x), k ∘ h)
  else:
    return k(b(x))

where ∘ denotes function composition. Note that F is now tail recursive.

You can then look for alternate (more efficient) representations of the continuation argument. In this case, the continuation always has the form $k_0\circ h\circ\cdots\circ h = k_0\circ h^i$ where $k_0$ is the continuation passed by the external caller. This can be represented by two arguments, $k_0$ and $i$:

fn F(x, k0, i):
  if p(x):
    return F(a(x), k0, i+1)
  else:
    x = b(x)
    repeat i times:
      x = h(x)
    return k0(x)

If you convert this to an iterative function in the usual way, and assume the caller always passes the identity function and zero for the second and third arguments, you get your iterative version of the function.

Usually you won't find such a concise encoding for the continuation. But quite generally the continuation will either be the original continuation, or one of a finite number of other functions that contains the previous continuation as a free variable (and possibly some other free variables). You can represent this as an array with one element for each "level", each element being a function number and the values of the non-continuation free variables. When you recurse downward you push another element, and when you return upward you pop an element. This gets you a stack-array-based iterative algorithm with the same space and time complexity as the original algorithm, but probably better constant factors.