Some of this, sum of that

| categories: miscellaneous, recursive | tags: | View Comments

Matlab plot

Python provides a sum function to compute the sum of a list. However, the sum function does not work on every arrangement of numbers, and it certainly does not work on nested lists. We will solve this problem with recursion.

Here is a simple example.

v = [1, 2, 3, 4, 5, 6, 7, 8, 9] # a list
print sum(v)

v = (1, 2, 3, 4, 5, 6, 7, 8, 9)  # a tuple
print sum(v)
45
45

If you have data in a dictionary, sum works by default on the keys. You can give the sum function the values like this.

v = {'a':1, 'b':3, 'c':4}
print sum(v.values())
8

1 Nested lists

Suppose now we have nested lists. This kind of structured data might come up if you had grouped several things together. For example, suppose we have 5 departments, with 1, 5, 15, 7 and 17 people in them, and in each department they are divided into groups.

Department 1: 1 person Department 2: group of 2 and group of 3 Department 3: group of 4 and 11, with a subgroups of 5 and 6 making up the group of 11. Department 4: 7 people Department 5: one group of 8 and one group of 9.

We might represent the data like this nested list. Now, if we want to compute the total number of people, we need to add up each group. We cannot simply sum the list, because some elements are single numbers, and others are lists, or lists of lists. We need to recurse through each entry until we get down to a number, which we can add to the running sum.

v = [1, 
    [2, 3],
    [4, [5, 6]],
    7,
    [8,9]]

def recursive_sum(X):
    'compute sum of arbitrarily nested lists'
    s = 0 # initial value of the sum

    for i in range(len(X)):
        import types  # we use this to test if we got a number
        if isinstance(X[i], (types.IntType,
                             types.LongType,
                             types.FloatType,
                             types.ComplexType)):
            # this is the terminal step
            s += X[i]
        else:
            # we did not get a number, so we recurse
            s += recursive_sum(X[i])
    return s

print recursive_sum(v)
print recursive_sum([1,2,3,4,5,6,7,8,9]) # test on non-nested list
45
45

In Post 1970 we examined recursive functions that could be replaced by loops. Here we examine a function that can only work with recursion because the nature of the nested data structure is arbitrary. There are arbitary branches and depth in the data structure. Recursion is nice because you do not have to define that structure in advance.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

blog comments powered by Disqus