Is there a more efficient way to write this recursive process?

Question

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)?

Answer 1

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)