DS&A

Recursion on Trees

Recursion is one of the most difficult ideas in programming, but sometimes it can be simple. A recursive function is a function which can call itself. Some recursive functions are very puzzling, but others are so natural that you can understand them even without knowing what recursion is.

A recursive function

For example, suppose we have a tree containing numbers, represented using the list-of-children data structure. How can we find the sum of every number in the tree? Here’s some Python code for an example:

class Node:
    def __init__(self, value, children=None):
        # a leaf node has an empty list of children
        if children is None:
            children = []
        self.value = value
        self.children = children

root = Node(1, [
    Node(2, [
        Node(3, [
            Node(4),
            Node(5)
        ]),
        Node(6)
    ]),
    Node(7, [
        Node(8, [
            Node(9)
        ])
    ]),
    Node(10)
])

To simplify the problem, we’ll give each leaf node an empty list of children, instead of None.(1) Here’s a node/link diagram of the example tree:

We want a function to calculate the sum of the numbers in the tree; the function’s input will be the root node. To begin with, let’s use a variable t to keep track of the “result so far”:

def tree_sum(node):
    t = node.value
    # ...
    return t

The missing code is the hard part — adding every descendant’s value to t. The root node has a list of children, but it doesn’t have a list of descendants; the best we can do right now is iterate over the children.

def tree_sum(node):
    t = node.value
    for child in node.children:
        t += # ...
    return t

For each child, we must add its value — and its descendants’ values. But this is exactly the same problem that tree_sum is meant to solve! So, we can simply call the tree_sum function to get the required result for child:

def tree_sum(node):
    t = node.value
    for child in node.children:
        t += tree_sum(child)
    return t

This function works — test it in Python, and find the sum by hand to check that the result is correct.

A recursive structure

This problem was easy to solve recursively, because the problem naturally has a recursive structure. The Node class is a recursive type: a Node object has a list of children, which are Node objects. The type’s definition refers to itself, just like a recursive function calls itself.

Intuitively, a recursive structure has “parts” which resemble the “whole”. A more visual way to see that trees are recursive structures is to consider subtrees: each node in the tree can be thought of as a “root node” for a smaller part of the tree. Here’s the subtree defined by the node with value 2:

The tree_sum function is an example of structural recursion. The problem has a recursive structure where the “parts” resemble the “whole”; the solution is a function which takes the “whole” as an input, and calls itself on the “parts”.

We have seen several recursive structures already:

• A linked list node has a value and a pointer to the next item, which is also a linked list node.
• The list-of-lists, list-of-children and parent pointer tree data structures are all recursive, because a node’s children and its parent are also nodes.
• In the adjacency list graph data structure, a node has a list of neighbours, which are also nodes.

A non-solution

Suppose we didn’t notice that tree_sum could call itself recursively to find the sum of the child subtree. In this case we might have written something like this:

def tree_sum(node):
    t = node.value
    for child in node.children:
        t += child.value
        # ...
    return t

This calculates the sum up to the first level of the tree, giving 1 + 2 + 7 + 10 = 20. To go further we should add the values from the second level, by iterating over child’s children:

def tree_sum(node):
    t = node.value
    for child in node.children:
        t += child.value
        for child2 in child.children:
            t += child2.value
            # ...
    return t

This function should return 1 + 2 + 3 + 6 + 7 + 8 + 10 = 37. To get to the third level of the tree, we need yet another nested loop to iterate over child2’s children:

def tree_sum(node):
    t = node.value
    for child in node.children:
        t += child.value
        for child2 in child.children:
            t += child2.value
            for child3 in child2.children:
                t += child3.value
                # ...
    return t

This now gives the correct result for our example tree, but it won’t work for trees with more levels.

Clearly, however many nested loops we add, we’ll never finish writing this function. If you ever find yourself needing infinitely many nested blocks of code, that’s a clue that you should use structural recursion instead.

Footnotes

1. For technical reasons, we can’t give the children parameter a default value of [], so we make it None and check inside the constructor.

• Tags: 
• recursion, structural recursion, trees, algorithms