Some of this, sum of that
Posted February 02, 2013 at 09:00 AM | categories: miscellaneous, recursive | tags:
Updated February 27, 2013 at 02:44 PM
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.