Tail-recursive Pascal triangle in Scheme

Question

I started to read SICP recently, and I'm very interested in converting a recursive procedure into a tail-recursive form.

For "one dimensional" situations (linear ones), like the Fibonacci series or factorial computation, it is not hard to do the conversion.

For example, as the book says, we can rewrite the Fibonacci computation as follows

(define (fib n)
    (fib-iter 1 0 n))
(define (fib-iter a b count)
    (if (= count 0) 
        b 
        (fib-iter (+ a b) a (- count 1))))

And this form is obviously tail recursive

However, for a "two dimensional" situation, like calculating Pascal's triangle (Ex 1.12 in SICP), we can still easily write a recursive solution like follows

(define (pascal x y) 
  (cond ((or (<= x 0) (<= y 0) (< x y )) 0)
        ((or (= 1 y) (= x y) ) 1)
        (else (+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))

The question is, how to convert this into a tail recursive form?

Answer 1

First of all, the recursive-process pascal procedure can be expressed in a simpler way (assuming non-negative, valid inputs) - like this:

(define (pascal x y) 
  (if (or (zero? y) (= x y))
      1
      (+ (pascal (sub1 x) y)
         (pascal (sub1 x) (sub1 y)))))

Now for the question. It is possible to transform the recursive-process implementation into an iterative-process version that uses tail recursion. But it's trickier than it seems, and to fully understand it you have to grasp how dynamic programming works. For a detailed explanation of this algorithm, please refer to Steven Skiena's The Algorithm Design Manual, 2nd edition, page 278.

This is the kind of algorithm that doesn't lend itself for an idiomatic solution in Scheme, because it requires that we mutate state as part of the solution (in this case, we're updating the partial results in a vector). It's a rather contrived solution and I optimized the table memory usage so only one row is needed at a time - and here it goes:

(define (pascal x y)
  (let ([table (make-vector (add1 x) 1)])
    (let outer ([i 1])
      (when (<= i x)
        (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-ref table y)))

In fact, in this case it would be more natural to write a straight iteration, mutating variables along the way. In Racket, this is how it looks:

(define (pascal x y)
  (define current null)
  (define previous null)
  (define table (make-vector (add1 x) 1))
  (for ([i (in-range 1 (add1 x))])
    (set! previous 1)
    (for ([j (in-range 1 i)])
      (set! current (vector-ref table j))
      (vector-set! table j (+ (vector-ref table j) previous))
      (set! previous current)))
  (vector-ref table y))

We can print the results and check that all of the three implementations shown work. Again, in Racket:

(define (pascal-triangle n)
  (for ([x (in-range 0 n)])
    (for ([y (in-range 0 (add1 x))])
      (printf "~a " (pascal x y)))
    (newline)))

(pascal-triangle 5)

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1