Issue 8: More Complicated Recursion

Failure is the key to success; each mistake teaches us something.
- Morihei Ueshiba  


Last week, I discusssed a simple recursive function that returns a boolean value. However, in many cases that is insufficient. Luckily, it is just as easy to return non-boolean values in recursion.

Let us consider a standard Tree ADT.  

class Tree:
    
    def __init__(self: "Tree", value: str=None, children: list=None):
        self.value = value
        if not children:
            self.children = []
        else:
            self.children = children[:]

We are given a few Trees and we need to find whether a letter exists in value of the Tree and its children, and if so, how many. We'll try to find how many times the letter a exists in the following tree as our example:

    tn2 = Tree("one", [Tree("two"), Tree("three"), Tree("apple"), Tree("five")])

    tn3 = Tree("answer", [Tree("six"), Tree("seven")])

    tn1 = Tree("eight", [tn2, tn3])

Similar to last time, we first consider the simplest case. A single Tree with no children.

def count(t: "Tree", x: str) -> int:
    """Return number of values in t and its children that contains x.
    
     >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    return t.value.count(x)

We simply count the number of letters, easy enough. Now, what if the Tree have children? Then we can call this recursively, as we've already defined the simplest case. 

def count(t: "Tree", x: str) -> int:
    """Return number of values in t and its children that contains x.
    
    >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    if not t.children is None:
        for child in t.children:
            return count_tree(child, x)
        
    return t.value.count(x)

However, running it like this won't do us any good. We don't want to simply return how many items exist in a particular Tree, we want to return how many items exists in all the trees in total. This should be a good hint as to what we need to do! (hint: add)

def count_tree(t: "Tree", x: str) -> int:
    """Return number of values in t and its children that contains x.
    
    >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    total = 0
    
    if not t.children is None:
        for child in t.children:
            total = total + count_tree(child, x)
        
    return total + t.value.count(x)

What makes this algorithm works is that if a Tree has no children, then total is 0, and the for loop is not run; so it is equivalent to the very simple case. However, if a Tree has children, then it will run equivalent to the very simple case for every single child, and sum it up in our accumulator variable called total. As a result, even though every "branch" of the Tree returns a different value, we are still able to return the final sum when we call the function.

As a bonus, here is my alternative algorithm that works. 

def count_tree(t: "Tree", x: str):
    """Return number of values in t that begin with 'a'.
    
    >>> tn2 = Tree("one", [Tree("two"), Tree("three"),\
    Tree("apple"), Tree("five")])
    >>> tn3 = Tree("answer", [Tree("six"), Tree("seven")])
    >>> tn1 = Tree("eight", [tn2, tn3])
    >>> count_tree(tn1, "a")
    2
    >>> count_tree(tn2, "a")
    1
    """
    initial_list = [t.value] + t.children 
    
    total_list = [count_tree(t, x) if isinstance(t, Tree) 
              else t.count(x) for t in initial_list]
    
    return sum(total_list)

It ended up confusing several people during their first glance. However, if we break it down, we can see that the value and children are added together into a single list. Using the list comprehension syntax, we ask Python to treat every item in the list differently, depending on whether it is a Tree or a value. If it was a value, then we simply returned the number of time x exists value using t.count(x). This is our simplest case. If it was a Tree, then we recursively called count_tree(t, x) on that Tree. Our recursive function will then find the number of times x exists in that Tree, and return it as an integer. Eventually, total_list will be populated by integers, each representing the number of time x exists in value for a particular Tree or value, which we sum up to find to total number of time.

So in conclusion, even complicated Recursive functions can be made based on the rule of starting with the simplest case, and then adding up from there.