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:

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.

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]) |