-
Notifications
You must be signed in to change notification settings - Fork 0
/
exercise1-12.scm
71 lines (52 loc) · 1.43 KB
/
exercise1-12.scm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
;;; SICP Exercise 1.12
;;; (The online text can be found at
;;; http://mitpress.mit.edu/sicp/full-text/book/book.html)
;;;
;;; This exercise had us writing a procedure to compute the elements of
;;; Pascal's triangle using a recursive process.
; Pascal's triangle looks like this:
;; 1
;; 1 1
;; 1 2 1
;; 1 3 3 1
;; 1 4 6 4 1
;; ... ...
; ... where the numbers at the edges are all 1's, and each number inside the
; triangle is the sum of the two numbers directly above it.
; If we slant the triangle over to the left, it looks like this:
;; 1
;; 1 1
;; 1 2 1
;; 1 3 3 1
;; 1 4 6 4 1
;; ... ...
; Then we can see that the first column will always have only 1's,
; there are 1's across the leading diagonal (where the row number
; equals the column number), and for a number in any other position
; (i,j), it is the sum of the number directly above it, ie. (i-1,j),
; and the number above it and one over to the left, ie. (i-1,j-1).
; So the procedure for the recursive process is then straight-forward:
(define (pascal row column)
(cond ((= column 1) 1)
((= column row) 1)
(else (+ (pascal (- row 1) (- column 1))
(pascal (- row 1) column)))))
; And we can use this procedure to print out the next row of the triangle:
(pascal 6 1)
;> 1
(pascal 6 2)
;> 5
(pascal 6 3)
;> 10
(pascal 6 4)
;> 10
(pascal 6 5)
;> 5
(pascal 6 6)
;> 1
;; 1
;; 1 1
;; 1 2 1
;; 1 3 3 1
;; 1 4 6 4 1
;; 1 5 10 10 5 1