## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.12

## Problem

The following pattern of numbers is called Pascal's triangle. (Markup courtesy of Wikipedia.)

<math> \begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&1&&3&&3&&1\\ &1&&4&&6&&4&&1 \end{matrix} </math>

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.

## Solution

Each element of the triangle has two coordinates: a row and an index. We'll call row 1 the top-most row (the row whose only element is 1) and index 1 the left-most number in a row. Note the following

- Row
*n*has*n*elements. - Index 1 and index
*n*are always 1. - The element at row
*r*and index*i*is 1 if*i*= 1 or*i*=*r*, otherwise it's the sum of the element at (row <math>r-1</math>, index <math>i-1</math>) and the element at (row <math>r-1</math>, index*i*).

Using these rules, we can create the procedure. The value it returns is the value of the element of Pascal's triangle at the given row and index.

(define (pascals-triangle row index) (cond ((or (= index 1) (= index row)) 1) (else (+ (pascals-triangle (- row 1) (- index 1)) (pascals-triangle (- row 1) index)))))

## Tests

(pascals-triangle 1 1)

*Output:*

`
`

1

(pascals-triangle 2 1)

*Output:*

`
`

1

(pascals-triangle 2 2)

*Output:*

`
`

1

(pascals-triangle 3 1)

*Output:*

`
`

1

(pascals-triangle 3 2)

*Output:*

`
`

2

(pascals-triangle 3 3)

*Output:*

`
`

1

(pascals-triangle 4 1)

*Output:*

`
`

1

(pascals-triangle 4 2)

*Output:*

`
`

3

(pascals-triangle 4 3)

*Output:*

`
`

3

(pascals-triangle 4 4)

*Output:*

`
`

1

(pascals-triangle 5 1)

*Output:*

`
`

1

(pascals-triangle 5 2)

*Output:*

`
`

4

(pascals-triangle 5 3)

*Output:*

`
`

6

(pascals-triangle 5 4)

*Output:*

`
`

4

(pascals-triangle 5 5)

*Output:*

`
`

1