Understanding Recursion: Part 2/4

In the previous post, we discussed about the general nature of recursion and recursive programming. We looked at a simple piece of code to understand how recursion happens under the hood. This post delves a bit deeper into recursive programming. Now that we understand recursion, how do we apply it to a real programming problem? We need to understand how we can deconstruct a programming problem so that we can use recursion. Figuring this part out can get tricky sometimes! It’s easier for some problems, but not so much for a few others. In this post, we will look at an abstract data type and see how we use recursion to our advantage. Let’s get out hands dirty, shall we?  

Tree climbing is for recreation only!

Let’s talk about trees. In computer science, a tree is a structure made up of nodes, where each node has some number of children that are also nodes (or null if it’s a terminal node). A binary tree is a tree made of nodes that have exactly two children, typically called “left” and “right”; again the children can be nodes or null. A root is a node that is not the child of any other node. The picture on the left is an example of a binary tree. A binary tree is just a tree where each node can at most two children. In programming, binary trees are used extensively to model problems because of their useful properties.

Let’s say we have a binary tree and each node in this tree is associated with a number. Now we want to sum all the values in this tree. To sum value in any one node, we would add the value of node itself to the value of its left child and the value of its right child. Now we know that the children are also nodes (unless they are terminal nodes). So to sum the left child, we would add the value of child node itself to the value of its left child and the value of its right child. To sum the value of the left child’s left child, we would add the value of child node itself to the value of its left child and the value of its right child.

As you can see, the problem is self repetitive. The big problem is to sum up all the values and the smaller problem is to add a node’s value to its children’s values. If we define a method to solve the smaller problem, then we can use it recursively to solve the bigger problem. Here’s how we do it:

class node {
    public:
        node* left;
        node* right;
        int value;
};

int sumTree( node* root ) 
{
    // if there is no tree, its sum is zero
    if( root == null ) 
        return 0 ; 
    else // this node has children
        return root->value + sumTree(root->left) + sumTree(root->right);
}

Note that instead of explicitly testing the children to see if they are terminal nodes, we just make the recursive function return zero for a null node.

Let’s say we have a tree that looks like this:

          7
       /     \
     5         4
    / \       / \
   2   3     1   N
 /  \       /  \
 N   N     N    N

If we call sumTree on the root (the node with value 7), we will return:

return root->value + sumTree(root->left) + sumTree(root->right);

Now let’s expand that in place.

return 7 + sumTree(node-with-value-5) + sumTree(node-with-value-4);

Every time we see sumTree, we’ll replace it with the expansion of the ‘return’ statement. If you continue doing this for all the occurrences of sumTree(), you will see that it expands to a simple addition problem. Did you see how we conquered a data structure of random breadth and depth? We did it by considering it to be a repeated calculation of a smaller problem. Each time we went through our sumTree function, we dealt with only a single node. We just used a singe if/then branch, and two simple return statements that almost wrote themselves. Pretty sweet right! That’s the power of recursion.

In the next post, we will see a few more recursive programming problems.

————————————————————————————————-