Optimizing recursive calls over data structures

Question

Is there an algorithm to optimize a highly recursive function into an iteration over a data structure? For example, given the following function...

// template <typename T> class BSTNode is defined somewhere else
// It's a generic binary search tree.
template <typename T, typename R>
void in_order(BSTNode<T>* root, R (*routine)(T))
{
    if (root)
    {
        in_order(root->leftChild);
        routine(root->data);
        in_order(root->rightChild);
    }
}

... is it possible to optimize it into...

// template <typename> class Stack is defined somewhere else
// It's a generic LIFO array (aka stack).

template <typename T, typename R>
void in_order(BSTNode<T>* root, R (*routine)(T))
{
    if (!root) return;

    Stack<BSTNode*> stack;
    stack.push(NULL);

    line1:
    while (root->leftChild)
    {
        stack.push(root);
        root = root->leftChild;
    }

    line2:
    routine(root->data);
    if (root->rightChild)
    {
        root = root->rightChild;
        goto line1;
    }

    else if (root = stack.pop())
        goto line2;
}

(Of course, the difference is that, instead of filling the call stack, the latter fills another stack in the heap.)

---

EDIT: I meant an algorithm that can be executed by the compiler, so I don't have to optimize it by hand.

Answer 1

Of course, the difference is that, instead of filling the call stack, the latter fills another stack in the heap.

You answered yourself. What is cheaper, stack or heap? (unless you are running out of stack space)

Answer 2

Technically the answer to this is "yes": any algorithm which can be expressed recursively (i.e. with an implicit stack) can also be reformulated to use iteration (i.e. with an explicit stack or other tracking structure).

However, I suspect that most compilers can't or won't attempt to do this for you. Coming up with a general-purpose automatic algorithm for performing the transformation is likely to be pretty difficult, although I've never tried it, so I shouldn't say that it's intractable.

Answer 3

Yes, you can do this.

However, aside from possibly exhausting stack space with very deep trees, there is no "optimization" here. If you need speed gains, consider threading your trees instead.

Answer 4

The only general recursive optimisation I've come across is that of optimising tail recursion. This is frequently done in functional languages and basically involves the compiler/interpreter changing a function where the final operation is the recursive call into a fully iterative function (so no problems with stack, etc).

For other forms of recursion, I'm not aware that any general purpose algorithm for optimising them into iterative functions has been found/created. You can certainly always express such functions in an iterative manner, but the transformation is not a general purpose one.

Answer 5

It is possible to traverse a tree depth-first, without using recursion.

A good example is the following: http://code.activestate.com/recipes/461776/.

The compiler won't do this optimization for you, though. However, the concept is not so hard to grasp. What you're doing is creating a call stack and nodelist yourself, instead of using a function call to go deeper into the tree.

Answer 6

It is possible to traverse a mutable ordered tree iteratively, by recording the node's parent in the branches you take, and knowing the direction you approach a node from ( down, or up from the left or right, which the ordered property of the tree lets you test ):

template <typename T, typename R>
void in_order ( BSTNode<T>* root, R (*routine)(T) ) {
    typedef BSTNode<T>* Node;

    Node current = root;
    Node parent  = 0;

    bool going_down = true;

    while ( current ) {
        Node next = 0;

        if ( going_down ) {
            if ( current -> leftChild ) {
                // navigate down the left, swapping prev with the path taken
                Node next_child = current -> leftChild;
                current -> leftChild = parent;
                parent = current;
                current = next_child;
            } else if ( current -> rightChild ) {
                // navigate down the right, swapping prev with the path taken
                Node next_child = current -> rightChild;
                current -> rightChild = parent;
                parent = current;
                current = next_child;
            } else {
                // leaf
                routine ( current -> data );
                going_down = false;
            }
        } else {
            // moving up to parent
            if ( parent ) {
                Node next_parent = 0;

                // came from the left branch
                if ( parent -> data > current -> data ) {
                    // visit parent after left branch
                    routine ( parent -> data );

                    // repair parent
                    next_parent = parent -> leftChild;
                    parent -> leftChild = current;

                    // traverse right if possible
                    if ( parent -> rightChild ) {
                        going_down = true;
                        // navigate down the right, swapping prev with the path taken
                        Node next_child = parent -> rightChild;
                        parent -> rightChild = next_parent;
                        //parent = current;
                        current = next_child;
                        continue;
                    }
                } else {
                    // came from the right branch
                    next_parent = parent -> rightChild;
                    parent -> rightChild = current;
                }

                current = parent;
                parent = next_parent;
            } else {
                break;
            }
        }
    }
}

If rather than storing the children, you store the XOR of the parent and child, then you can get the next node in whatever direction you approach from without having to mutate the tree.

I don't know of anything with automatically transforms non-tail recursive functions into such code. I do know of environments where the call stack is allocated on the heap, which transparently avoid a stack overflow in cases where you can't perform such mutations and have a fixed small stack size. Usually recording the state on a stack takes less space that the call stack, as you're selecting only the essential local state to record, and are not recording return addresses or any caller-save registers ( if you used a functor rather than a function pointer, then it's more likely that the compiler might be able to inline routine and so not save the caller save registers in the simple recursive case, so reducing the amount of stack required for each recursion. YMMV ).

Since you're using templates you should only need to do the traversal code once, and combine it with strategy templates to switch between pre, post and inorder, or whatever other iteration modes you want.

Answer 7

Sure you can make your own stack.

You want speed? Unless routine(root->data) does almost nothing, you'll never notice the difference.

Answer 8

You're asking for the continuation-passing-style transformation with defunctionalized continuations; it's covered in chapter 6 of Essentials of Programming Languages, with code in Scheme. But it'd be a huge pain to implement for C++. Maybe if you have a compiler frontend that converts C++ into reasonably accessible datastructures, though, and you need to do this to a lot of code. The book also explains how to do this transformation systematically by hand, which is more likely to be practical in your situation.