Exercise 1.12 asks us to write a procedure that computes the elements of Pascal's triangle by means of a recursive process.

The numbers along the left and right edges of the triangle are all 1, and each number inside the triangle is the sum of the two numbers directly above it.

We'll design our procedure to take the row and column numbers as arguments, and return the value of the element in that position.

`(pascal row col)`

We start counting both rows and columns at 0, as pictured in the diagram. So the procedure call

`(pascal 4 2)`

should return a value of 6, since that is the value in the 4th row and 2nd column.The first thing we should note is that the nth row of the triangle contains exactly n columns. This means that we shouldn't expect to call our procedure with a column argument greater than the row argument. So, the following call would be expected to return nonsense information:

`(pascal 3 4)`

We should also note that the 0th and nth column of any row should return 1. This is enough to get us started.

`(define (pascal row col)`

(cond ((< row col) #f)

((or (= 0 col) (= row col)) 1)

(else #t)))

Here we're just defining the initial logic of the procedure. If the row argument is less than the column, we simply return #f (probably not the best error message I've ever written, but it's not the focus of the exercise). If the column is the 0th or nth column, we return 1, otherwise we return a value of #t. This last value is just a placeholder which we'll need to replace with a calculation of the correct Pascal number.

To finish up the procedure, we need to recursively calculate values from the interior of the triangle. An interior value is defined as the sum of the two values directly above in the triangle. So, for example, to calculate Pascal(4, 2) we would sum Pascal(3, 1) and Pascal(3, 2). Each of these values (since there are both interior values) would be calculated in the same manner, but the recursive property of our procedure will take care of that for us.

The two values to sum in order to calculate Pascal(row, column) are always going to be the value in the previous row and same column, Pascal(row-1, column), and the value in the previous row and previous column, Pascal(row-1, column-1). Translating this information to Scheme and adding it to our earlier procedure, we get our final answer to the exercise:

`(define (pascal row col)`

(cond ((< row col) #f)

((or (= 0 col) (= row col)) 1)

(else (+ (pascal (- row 1) col)

(pascal (- row 1) (- col 1))))))

Try several examples from Pascal's triangle illustration to verify that the results are correct. Note that since this procedure defines a recursive process, calculating larger values can be extremely time consuming. It takes a noticeable amount of time (a few seconds) on my machine to calculate values in the 25th row.

For more fun with Pascal's triangle see Pascal's Triangle and its Patterns.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.