Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.
The procedure will return the mth element of the nth row given that \(0 <= m <= n\).
The outer elements of a row will always be \(1\) (therefore the first and second row will also contain exclusively \(1\)). In all other cases, element m of row n will be the sum of mth and (m - 1)th coefficients of previous row. For example, the third element of the fourth row is the sum of the second and third elements of the third row: \(1 + 2 = 3\). This suggests a recursive implementation:
(define (f m n)
(cond ((= n 0) 1) ; first row
((= n 1) 1) ; second row
((= m 0) 1) ; left-most element
((= m n) 1) ; right-most element
(else (+ (f m (dec n)) (f (dec m) (dec n))))))
In fact, the first two cases are redundant, and the above procedure can be simplified by removing them:
(define (f m n)
(cond ((= m 0) 1)
((= m n) 1)
(else (+ (f m (dec n)) (f (dec m) (dec n))))))
(Note that there is no error handling; the constraint \(0 <= m <= n\) must be followed).
The following applications of the procedure compute the elements of the seventh row:
(f 0 7)
1
(f 1 7)
7
(f 2 7)
21
(f 3 7)
35
(f 4 7)
35
(f 5 7)
21
(f 6 7)
7
(f 7 7)
1