Tail-recursive Pascal triangle in Scheme

问题:

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?

回答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 

回答2:

UPDATE: This problem has a far easier math solution that you can get down to O(row) using only factorial. Based on that this boils down to:

(define (pascal-on row col)
  (define (factorial from to acc)
    (if (> from to)
        acc
        (factorial (+ 1 from) to (* acc from))))

  (let* ((rmc (- row col))
         (fac-rmc (factorial 1 rmc 1))
         (fac-pos (factorial (+ rmc 1) col fac-rmc))
         (fac-row (factorial (+ col 1) row fac-pos)))
    (/ fac-row fac-pos fac-rmc)))

Old answer:

You need to study the patterns. Basically you want to iterate from the beginning of the triangle until you have enough information to produce a result. It's obvious that you need the previous row to compute the next so that must be an argument you give it and it must supply the next if the requested row is not the current. This solution is tail recusive and lightning fast.

(define (pascal row col)
  (define (aux tr tc prev acc)
    (cond ((> tr row) #f)              ; invalid input

          ((and (= col tc) (= row tr)) ; the next number is the answer
           (+ (car prev) (cadr prev))) 

          ((= tc tr)                   ; new row 
           (aux (+ tr 1) 1 (cons 1 acc) '(1)))

          (else (aux tr               ; new column
                     (+ tc 1) 
                     (cdr prev)
                     (cons (+ (car prev) (cadr prev)) acc))))) 

  (if (or (zero? col) (= col row))
      1
      (aux 2 1 '(1 1) '(1))))

回答3:

To add to Óscar's answer, we can use continuation-passing style to convert any program to use tail calls:

;; Int Int (Int → Int) → Int
(define (pascal/k x y k)
  (cond
   [(or (<= x 0) (<= y 0) (< x y)) (k 0)]
   [(or (= 1 y) (= x y)) (k 1)]
   [else (pascal/k (- x 1) y
                   (λ (a)
                     (pascal/k (- x 1) (- y 1)
                               (λ (b) (k (+ a b))))))]))

;; Int Int → Int
(define (pascal x y) (pascal/k x y (λ (x) x)))

You may say this program is not as satisfactory, as there's the closure that "grows". But they are allocated on the heap. In the general case, the point of having tail-call is not so much about performance as it is about space safety: you don't blow up the evaluation context.