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

From Drewiki
Jump to: navigation, search

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
Personal tools