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