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

Re my edits, your code could be even more readable with the use of `cond` instead of nested `if`s, and the use of named `let` instead of the inner definitions. But I've kept my changes exclusively to formatting only. — C. K. Young, Sep 29 '14 at 16:07

score 3 · Accepted Answer · edited May 23 '17 at 10:28

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)

I am new to scheme so I don't really know a lot about structures and functions like table, make-vector etc. I tried checking out the documentaiton but it is not really helpful. Can you please briefly explain what they each do? — user3450695, Sep 29 '14 at 16:30
@user3450695 The first version uses vectors, think of them as fixed-size lists that allow fast retrieval given an index, and also permit the modification of a value - just like arrays in other programming languages. Perhaps you'll find this [documentation](http://docs.racket-lang.org/reference/vectors.html) easier to understand. If the first solution is too complex, then stick with the second version, it only uses basic procedures. — Óscar López, Sep 29 '14 at 16:48
@user3450695 Anyway, bear in mind that an iterative version for this procedure is not _that_ simple (you're asking for something inherently difficult!), you'd do well to read the explanation of the dynamic programming solution, please refer to Steven Skiena's "The Algorithm Design Manual", 2nd edition, page 278. — Óscar López, Sep 29 '14 at 16:53

score 1 · Answer 2 · answered Sep 30 '14 at 01:24

There are a number of soluitons presented already, and they do point out that usign dynamic programming is a good option here. I think that this can be written a bit more simply though. Here's what I'd do as a straightforward list-based solution. It's based on the observation that if row n is (a b c d e), then row n+1 is (a (+ a b) (+ b c) (+ c d) (+ d e) e). An easy easy to compute that is to iterate over the tails of (0 a b c d e) collecting ((+ 0 a) (+ a b) ... (+ d e) e).

(define (pascal n)
  (let pascal ((n n) (row '(1)))
    (if (= n 0) row
        (pascal (- n 1)
                (maplist (lambda (tail)
                           (if (null? (cdr tail)) 1
                               (+ (car tail)
                                  (cadr tail))))
                         (cons 0 row))))))

(pascal 0) ;=>     (1)
(pascal 1) ;=>    (1 1)
(pascal 2) ;=>   (1 2 1)
(pascal 3) ;=>  (1 3 3 1)
(pascal 4) ;=> (1 4 6 4 1)

This made use of an auxiliary function maplist:

(define (maplist function list)
  (if (null? list) list
      (cons (function list)
            (maplist function (cdr list)))))

(maplist reverse '(1 2 3))
;=> ((3 2 1) (3 2) (3))

Any reason for the downvote? I'm open to improvements? I think this is fairly clean way to calculate these rows using dynamic programming (we keep only two rows at a time). It addresses the last part of the question directly: "Also, how would I write it, if I want to use an iterative process (tail-recursion)?" This is tail recursive/iterative. — Joshua Taylor, Sep 30 '14 at 16:57

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

2 Answers2