# RC17. Pascal’s Triangle in Lisp

*Daily dispatches from my 12 weeks at the Recurse Center in Summer 2023
*

I was stumped on implementing a procedure that computes a given element in Pascal’s triangle using Lisp but finally figured it out thanks to a little help from a mathematician.

Here’s Pascal’s triangle:

```
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
etc.
```

The pattern is simple enough: each number is the sum of the two numbers above it. But how to implement this simply? What was stumping me was sorting out how to retain a given row so that the following row could be, somehow, computed from it.

Turns out it’s a lot simpler than this.

First of all, let’s redraw the triangle in terms of each value’s row and column number:

```
1
(0, 0)
1 1
(1, 0) (1, 1)
1 2 1
(2, 0) (2, 1) (2, 2)
1 3 3 1
(3, 0) (3, 1) (3, 2) (3, 3)
1 4 6 4 1
(4, 0) (4, 1) (4, 2) (4, 3) (4, 4)
```

Thanks to this new format, we can make a few important observations about the pattern: seeing the pyramid in this format, Here are three observations that we can now thanks to the following observations about the pattern.

- If the column is 0, then the value is 1 (that’s the left-hand edge of the triangle)
- If the column is equal to the current row, then the value is also 1 (that’s the right-hand edge of the triangle)
- Otherwise, we need to compute the current value from the numbers above, which is to say from the previous row (
`row - 1`

). And here there’s another pattern, since the two numbers directly above are at columns`col - 1`

and`col`

.

At that point, implementing this suddenly becomes straightforward, since we have our base cases (`col = 0`

and `col = row`

, in which case the resulting value is 1) and we have our recursive case.

Here’s how it would look:

```
(define (pascal row col)
((cond)
(= col 0) 1 ; base case 1: left edge of triangle
(= col row) 1 ; base case 2: right edge of triangle
(else ; recursive case: sum left and right parent
(+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col))))
```

Thus is we call, for instance:

```
(pascal 7 3)
```

we will get

```
;Value: 35
```

# Etc

- Continued yesterday’s brain melt pairing on some leetcode stumpers
- Drew out a bunch of program counter schematics
- Weekly nand2tetris meeting
- Quick pairing session to sort out the above procedure