Eliminating recursion

Question

It is easy to eliminate tail recursion.

There are few curious cases where the not-tail recursion can also be eliminated.

• Exhibit 1: Fibonacci numbers.

  A naive recursive solution

  fib(n)
      if (n < 2)
          return n
      return fib(n-1) + fib(n-2)
  

  leads to exponential complexity. An iterative solution

  fib(n)
     f_0 = 0
     f_1 = 1
     for i = 2; i < n; ++i
         f = f_0 + f1
         f_0 = f1
         f_1 = f
     return f
  

  is linear. I know I can have a logarithmic one, but it's besides the point.

• Exhibit 2: merge sort

  A recursive solution

  merge_sort(begin, end)
      mid = begin + (end - begin)
      merge_sort(begin, mid)
      merge_sort(mid, end)
      merge(begin, mid, end)
  

  (which is not as bad as Exhibit 1, but still) also allows an iterative version:

  merge_sort(begin, end)
      for stride = 2; stride < end - begin; stride *= 2
          for start = begin; start < end; start += stride
              merge(start, start + stride/2, start + stride)
  

These seemingly unrelated exhibits share a common trait: there is no job done on the way down¹.

The real questions are,

• does this trait warrant that elimination is possible,

• is it possible to identify it, and

• once identified, is there a mechanical way to actually eliminate the recursion.

Disclaimer: I am only interested in elimination without using a stack. I know it is always possible to eliminate recursion introducing a stack like shown in General way to convert a loop (while/for) to recursion or from a recursion to a loop?

---

[1] Nobody is going to rob us going down the mountain. We have got no money going down the mountain. When we have got the money, on the way back, then you can sweat.

Answer 1

does this trait [no job done on the way down] warrant that elimination is possible,

No. A simple example: visiting a binary-tree in post order: no work is done on the way down, yet you need a stack (there are ways to encode that stack in the tree by temporarily modifying the tree, but the stack is fundamentally there).

Yet, there are ways to remove non-terminal recursions without using a stack. But those I know are using additional properties, and notably the one that some operations can be carried in another order than the one used for the recursive version. That's true for your Fibonacci example (where you also are using the fact that some operations are redundant), and your merge sort one. Detecting that this property holds can be difficult (it could change the stability and error characteristic of a floating point algorithm for instance).

At least two of them are systematic enough that it would be possible to get compilers implementing them (I know that the first has been implemented in compilers).

• the introduction of accumulator parameters. Some cases of non-terminal recursion can be turned into a terminal recursion by introducing an additional parameters and using the associativity of the operation still to be done. That's the case for a recursive factorial or list-length function:

  int len(list l) {
      if (l == NIL)
          return 0;
      else
          return 1 + len(tail(l));
  }
  

  can be replaced with

  int len_aux(list l, int acc) {
      if (l == NIL)
          return acc;
      else
          return len_aux(tail(l), acc+1);
  }
  
  int len(list l) {
      return len_aux(l, 0);
  }
  

  There are algorithms showing how to do automatically.

• the next technique I've used (but don't remember having seen described in the context of an optimization pass for a compiler) is using memoization as an intermediary step (and thus is valid only for pure function). That is you consider that you are caching the result of the function in a table indexed with its parameters and then see that the table can be computed in another order, sometimes reducing the number of values that need to be kept. That method would be applicable to your Fibonacci program.

Being able to remove recursion for your merge example is even more complex: it is not a pure function but one which mutate state. You can think and deduce that it is possible to change the order of operations to made them suitable for a non-recursive implementation without needing a stack, but such a small description can be useful for a human, expanding it to an algorithm to be implemented in a compiler would need some additional work.