SICP Exercise 1.12

Question

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

copy    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.

Answer

copy(define (pascal n k)
  (cond ((or (< k 0) (> k n)) 0)
  	    ((= n 0) 1)
	    (else (+ (pascal (- n 1) (- k 1)) (pascal (- n 1) k)))))

The function I am defining here takes two parameters: n for the row of the triangle starting from 0, and k for the element within the row, also starting from 0. For understanding the way this works, picture the triangle as having a slant to the left:

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

Every element in the triangle is the sum of the element directly above it ($n-1,k$) and the element above and to the left of it ($n-1,k-1$). The space surrounding the triangle could be imagined as being filled with $0$s, so any access to $k<0$ or $k>n$ simply returns $0$. In this way, the algorithm “climbs” up the triangle until it reaches $n=0$, which of course returns $1$.