Using Nested Functions for Cleaner Recursion

Python is not a particularly friendly language for recursion — a finite stack and significant overhead on function calls often make alternate implementations more desirable. However, there are some problems that are difficult to handle gracefully any other way — tree structures, for example — and other instances where clarity is preferable to performance. They do still have a place, and where we use them we may as well try to make them as clean and elegant as possible. Fortunately, Python makes this rather easy.

Many recursive problems are actually handled best in two stages: first, to check initial conditions (does our tree have a root?), and second, carry out the actual recursive portion. Doing all of this in one function is messy, at best, so we split the function in two. Consider the following C code, for retrieving data out of a binary tree:

static TreeNode *Tree_get_node(Tree *tree, TreeNode *node, void *key)
{
    if (node->key == key) {
        return node;
    }
    else if (node->key < 0) {
        if (node->left) {
            return Tree_get_node(tree, node->left, key);
        }
        else {
            return NULL;
        }
    }
    else {
        if (node->right) {
            return Tree_get_node(tree, node->right, key);
        }
        else {
            return NULL;
        }
    }
}

void *Tree_get(Tree *tree, void *key)
{
    if (tree->root == NULL) {
        return NULL;
    }
    else {
        TreeNode *node = Tree_get_node(tree, tree->root, key);
        return node == NULL ? NULL : node->data;
    }
}

This is not a bad way to handle this problem, however there are a few issues:

  • You’re exposing internal functions. (Python has no notion of module-private functions.)
  • It’s not immediately obvious that the two functions are linked so tightly together (Even more so if the next maintainer to come along carelessly inserts code in between them.)
  • It’s not as pretty as it could be, and I like me some pretty code.

Python’s syntax allows you to define functions even within another function. This internal function is available within that function’s scope, and nowhere else.

So, rewriting the above example in Python, using our nested functions, we’d get something like this:


def Tree_get(tree, key):

    def _Tree_get(tree, node, key):

        if node.key == key:
            return node
        elif node.key < key:
            if node.left:
                return _Tree_get(tree, node.left, key)
            else:
                return None
        else:
            if node.right:
                return _Tree_get(tree, node.right, key)
            else:
                return None

    if tree.root == None:
        return None
    else:
        node = _Tree_get(tree, tree.root, key)
        return None if node == None else node.data

(Note that the internal function is not compiled by the interpreter until the outer function is called. As such, unlike global or module level functions, the definition of the internal function has to come before any code that calls it.)

The result is a single clean block of code, easier to read and maintain.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s