Eliminating tail recursion

Eliminating tail recursion

Recursion is rarely a good solution, but some types of recursive algorithms are not easy to change to loops, because they would require a stack data structure to do so. If a stack is needed, there may be little gain in removing recursion fully — it depends on how efficiently recursion is implemented by the compiler on the builtin C++ function call stack, versus your skill in hand-coding a stack data structure.

In these situations, a simpler optimization is still possible without a stack. Partial recursion elimination without the need for a stack is possible via the elimination of “tail recursion.” Tail recursion occurs when the last action of the recursive procedure is to call itself.

A simple modification changes this last recursive call to become a loop back to the top of the current invocation. For example, consider the preorder traversal of a binary tree. The simplest recursive algorithm is:

    void preorder(node_ptr root)
    {
        if (root != NULL) {
            visit(root);
            preorder(root->left);
            preorder(root->right); // Tail recursion here
        }
    }

Tail recursion can be eliminated by replacing the if statement with a while loop. The transformation effectively reduces recursion by half, as the second recursive call is eliminated. This reduction in recursion is achieved with virtually no extra overhead!

    void preorder(node_ptr root)
    {
        while (root != NULL) { // while loop replaces if
            visit(root);
            preorder(root->left);
            root = root->right; // Move to right subtree
        }
    }