Collapsing recursive calls

Collapsing recursive calls

If you can't be bothered changing a recursive algorithm to a loop or stack, here's a smaller optimization to consider. By channeling the spirit of loop unrolling, we can “collapse” one or more levels of recursion into sequential code. The method of “function call collapsing” can be applied to recursive functions in this limited sense. Obviously, it isn’t possible to collapse a recursive function call completely into inline code, but it is possible to collapse a few levels of recursive calls at a time, reducing the total number of recursive calls by a constant factor.

Moving the recursive base case higher. The simplest method is to test the base case one level higher up. In the simple implementation of the preorder traversal , the recursive base case is “root==NULL”. If this occurs, the function call does nothing. One simple method of avoiding these unnecessary function calls is to test for the base case before the recursive call. The new function becomes:

    void preorder(node_ptr root)
    {
        while (root != NULL) {
            visit(root);
            if (root->left != NULL) // Test moved up
                preorder(root->left);
            }
            root = root->right;
        }

Collapsing multiple levels of recursion. By converting multiple levels of recursive calls into sequential code, the function does much more work each time, but makes recursive calls less frequently, thereby reducing function call overhead. For example, the preorder traversal can be rewritten so that the current node and its two children are handled by the function, and then recursive calls are made for any of the children’s children:

    void preorder(node_ptr root)
    {
        if (root != NULL) {
            visit(root);
            if (root->left != NULL) { // do left child
                visit(root->left);
                preorder(root->left->left);
                preorder(root->left->right);
            }
            if (root->right != NULL) { // do right child
                visit(root->right);
                preorder(root->right->left);
                preorder(root->right->right);
            }
        }
    }

But alas, we've reverted here to a fully recursive version again, just to show function call collapsing. The above method should also be combined with (a) tail recursion elimination, and (b) a stack data structure. This is left as an exercise for the reader (thankfully), and as a project scope estimate, I suggest two weeks!

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++