SICP Exercise 1.12: Pascal's Triangle

The following pattern of numbers is called Pascal's triangle.

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

As we've not been introduced to lists yet we can't write a procedure to generate rows iteratively, but we can write one that will return a single element from the triangle corresponding to a particular row and column. Just to be different, I'm going to use one-based indexing for referencing the rows and columns in the triangle. This means:

• Row 1 is the row at the top of the triangle. This has a single column containing the value 1.
• Column 1 is the left-most number in a row. Note that column 1 has the value 1 in all rows. This means that if the value in column 1 is requested we can simply return 1 without any further calculation.
• Column n is the n^th number (or right-most number) in row n. This also has the value 1 in all rows and similarly means that if the value in column n is requested we can simply return 1 without any further calculation.

What else can we say before we start? Well, the value for a particular row and column is only defined for row values of 1 or more, and for column values between 1 and the row number we're trying to calculate it for. The error operator hasn't been introduced at this point in SICP, so we'll need to do something else to indicate when we get bad input values. Let's return #f for now.

Okay, given all that, here's the procedure:

(define (pascal-tri row column)
  (cond ((or (< row 1) (< column 1) (> column row)) #f)
        ((or (= column 1) (= column row)) 1)
        (else (+ (pascal-tri (- row 1) (- column 1))
                 (pascal-tri (- row 1) column)))))

Let's test it! We know that row 5 has the column values {1, 4, 6, 4 1}, so let's try that:

> (pascal-tri 5 0)
#f
> (pascal-tri 5 1)
1
> (pascal-tri 5 2)
4
> (pascal-tri 5 3)
6
> (pascal-tri 5 4)
4
> (pascal-tri 5 5)
1
> (pascal-tri 5 6)
#f