Is there a more efficient way to write this recursive process?
I was asked to write a procedure that computes elements of Pascal's triangle by means of a recursive process. I may create a procedure that returns a single row in the triangle or a number within a particular row.
Here is my solution:
(define (f n) (cond ((= n 1) '(1)) (else (define (func i n l) (if (> i n) l (func (+ i 1) n (cons (+ (convert (find (- i 1) (f (- n 1)))) (convert (find i (f (- n 1))))) l)))) (func 1 n '())))) (define (find n l) (define (find i n a) (if (or (null? a) (<= n 0)) '() (if (>= i n) (car a) (find (+ i 1) n (cdr a))))) (find 1 n l)) (define (convert l) (if (null? l) 0 (+ l 0)))
This seems to work fine but it gets really inefficient to find elements of a larger row starting with (f 8). Is there a better procedure that solves this problem by means of a recursive process?
Also, how would I write it, if I want to use an iterative process (tail-recursion)?
There are several ways to optimize the algorithm, one of the best would be to use dynamic programming to efficiently calculate each value. Here is my own solution to a similar problem, which includes references to better understand this approach - it's a tail-recursive, iterative process. The key point is that it uses mutation operations for updating a vector of precomputed values, and it's a simple matter to adapt the implementation to print a list for a given row:
(define (f n) (let ([table (make-vector n 1)]) (let outer ([i 1]) (when (< i n) (let inner ([j 1] [previous 1]) (when (< j i) (let ([current (vector-ref table j)]) (vector-set! table j (+ current previous)) (inner (add1 j) current)))) (outer (add1 i)))) (vector->list table)))
Alternatively, and borrowing from @Sylwester's solution we can write a purely functional tail-recursive iterative version that uses lists for storing the precomputed values; in my tests this is slower than the previous version:
(define (f n) (define (aux tr tc prev acc) (cond ((> tr n) '()) ((and (= tc 1) (= tr n)) prev) ((= tc tr) (aux (add1 tr) 1 (cons 1 acc) '(1))) (else (aux tr (add1 tc) (cdr prev) (cons (+ (car prev) (cadr prev)) acc))))) (if (= n 1) '(1) (aux 2 1 '(1 1) '(1))))
Either way it works as expected for larger inputs, it'll be fast for n values in the order of a couple of thousands:
(f 10) => '(1 9 36 84 126 126 84 36 9 1)