** Some of this, sum of that
:PROPERTIES:
:categories: miscellaneous, recursive
:date: 2013/02/02 09:00:00
:updated: 2013/02/27 14:44:46
:END:
[[http://matlab.cheme.cmu.edu/2012/05/29/some-of-this-sum-of-that/][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.
#+BEGIN_SRC python
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)
#+END_SRC
#+RESULTS:
: 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.
#+BEGIN_SRC python
v = {'a':1, 'b':3, 'c':4}
print sum(v.values())
#+END_SRC
#+RESULTS:
: 8
*** 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.
#+BEGIN_SRC python
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
#+END_SRC
#+RESULTS:
: 45
: 45
In [[http://matlab.cheme.cmu.edu/2012/05/28/lather-rinse-and-repeat/][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.