0

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 down1.

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.

  • 1
  • 2
    @gnat: how can this be a dupe when the OP explicitly asks if there is a solution with no stack involved? – Doc Brown Apr 22 '17 at 8:07
  • I think if you ponder your Fibonacci example you will realize that they are two completely different ways of looking at the problem, which answers the "is there a mechanical way to actually eliminate the recursion." And the real issue is not "doing work on the way down" but keeping track of how to get back up. – kdgregory Apr 22 '17 at 11:05
  • @DocBrown agree the other question is not a duplicate, I misread. Not going to retract close vote though since there is another question that covers this one, a more appropriate dupe target: Is there anything that can be done with recursion that can't be done with loops? (specifically first and fourth top voted answers seem to address matters asked about here – gnat Apr 22 '17 at 13:23
  • One possibility is to (automatically) transform the program to continuation-passing-style, in which every call is a tail call. We can then eliminate the tail calls with a trampoline: each function doesn't tail-call some continuation, but returns it to be then called by the trampoline loop. Technically this doesn't use a stack, but any data that would usually reside on a stack is now stored in the continuations which are closures. It's possible to avoid an explicit stack, but it's not possible to eliminate that data. Once you lose recursion and dynamic memory, you also lose Turing completeness. – amon Apr 23 '17 at 11:04
4

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.