Exercise 1.12: The following pattern of numbers is called Pascal’s triangle.
- The LaTeX for this triangle is really a pain however this great python script makes the process trivial.
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.
(define (pascal row col)
(cond ((and (= row 0) (= col 0)) 1)
((= col 0) 1)
((and (= row col) 1))
(else
(+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col)))))
Both 1 and 2 hold true for the top node.
- The first condition recognizes that the first element on of every row is always 1, hence P(n,0) = 1 for each n
- The second condition recognizes that the last element of every row is always 1, hence P(n,n) = 1 for each n
- 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