Found in many textbooks is the problem of writing a function to create a portion of Pascal's Triangle. The first row of the triangle can, for purposes of this explanation, be the list [1]. The second row is [1,2,1], the third row [1,3,3,1]. The general pattern is to make row k by taking row k-1, and replacing all "gaps" (places between items) by the sum of numbers on either side of the gap. So, writing a function has two elements: recursion to generate rows (we use recursion because each row is built from the previous row, except for rows 1 and 2); and we need a way to do the "gap replacement". List comprehension can do this second part.

For the list comprehension, first look at this example:

row = [1, 3, 3, 1]

The gaps precede items row[1], row[2], row[3]. A reasonable conjecture on the general situation for a longer row with p items (instead of just 4 items) is that the gaps precede row[1] through row[p-1]. What should be done with a "gap" to create the new row? If the gap is row[k], then what's logical for the new row is row[k-1]+row[k]. Putting this into a list comprehension:

[ row[k-1]+row[k] for k in range(1,len(row)) ]

The trickiest part of the comprehension is getting the range just right, so that it runs from 1 up to one less than the length. But does it work?

1
2
3
>>> row = [1, 2, 1]
>>> [ row[k-1]+row[k] for k in range(1,len(row)) ]
[3, 3]

This isn't quite what we need: missing are the 1's to start and finish the new row. However, simple concatenation can fix that:


Next Row Function

def next(row):
  newrow = [ row[k-1]+row[k]
             for k in range(1,len(row)) ]
  return [1] + newrow + [1]
print next([1,2,1])
print next(next([1,2,1]))


The last line tests whether recursion looks OK, at least for one case. Now, to put all of this into a recursive program, we need to ask: in what order should the rows be printed? The usual way is to print them from first to last. The trick here is to use a counter to stop recursion. The counter will start with some number of rows (the counter will also be an argument to the recursive function). If the counter is zero, no more work remains to be done (no need for recursion). This is a pattern worth learning.


Triangle Function

def next(row):
  newrow = [ row[k-1]+row[k]
             for k in range(1,len(row)) ]
  return [1] + newrow + [1]
def pascal(rowsleft,oldrow):
  if rowsleft > 0:
    R = next(oldrow)
    print R
    pascal(rowsleft-1,R)
print [1]
print [1,2,1]
pascal(3,[1,2,1])