Recursion on TreesMar 122018
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) ])
We want a function to calculate the sum of the numbers in the tree; the function’s input will be the
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
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
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
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.
Node class is a recursive type: a
Node object has a list of children, which are
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:
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.
Suppose we didn’t notice that
tree_sum could call itself recursively to find the sum of the
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
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
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.
Image credit: Warner Bros. Pictures
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.
- For technical reasons, we can’t give the
childrenparameter a default value of
, so we make it
Noneand check inside the constructor.