Exercise 1.12 of SICP

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

\begin{tabular}{rccccccccc}row=0:&    &    &    &    &  1\\\noalign{\smallskip\smallskip}row=1:&    &    &    &  1 &    &  1\\\noalign{\smallskip\smallskip}row=2:&    &    &  1 &    &  2 &    &  1\\\noalign{\smallskip\smallskip}row=3:&    &  1 &    &  3 &    &  3 &    &  1\\\noalign{\smallskip\smallskip}row=4:&  1 &    &  4 &    &  6 &    &  4 &    &  1\\\noalign{\smallskip\smallskip}\end{tabular}

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.

Both 1 and 2 hold true for the top node.

  1. The first condition recognizes that the first element on of every row is always 1, hence P(n,0) = 1 for each n
  2. The second condition recognizes that the last element of every row is always 1, hence P(n,n) = 1 for each n
  3. This final condition states that in order to get the next number in the sequence: go up a row and back one column + up a row and stay in the same column P(n,k)=P(n-1,k-1)+P(n-1,k)

> (pascal 0 0)
1
> (pascal 7 2)
21
> (pascal 16 8)
12870

Leave a Reply