recursion - Triángulo de Pascal recursivo en Scheme

tail-recursion sicp

Question

Empecé a leer SICP recientemente, y estoy muy interesado en convertir un procedimiento recursivo en una forma recursiva de cola.

Para situaciones "unidimensionales" (lineales), como la serie de Fibonacci o el cálculo factorial, no es difícil hacer la conversión.

Por ejemplo, como dice el libro, podemos reescribir el cálculo de Fibonacci de la siguiente manera

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

Y esta forma es obviamente recursiva de la cola

Sin embargo, para una situación "bidimensional", como el cálculo del triángulo de Pascal (Ej 1.12 en SICP), aún podemos escribir fácilmente una solución recursiva de la siguiente manera

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

La pregunta es, ¿cómo convertir esto en una forma recursiva de cola?

Answer 1

En primer lugar, el procedimiento pascal proceso recursivo se puede expresar de una manera más simple (suponiendo entradas válidas no negativas), como esta:

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

Ahora para la pregunta. Es posible transformar la implementación de proceso recursivo en una versión de proceso iterativo que usa recursividad de cola. Pero es más complicado de lo que parece, y para comprenderlo completamente debe comprender cómo funciona la programación dinámica. Para una explicación detallada de este algoritmo, consulte el Manual de diseño de algoritmos de Steven Skiena, 2ª edición, página 278.

Este es el tipo de algoritmo que no se presta para una solución idiomática en Scheme, porque requiere que mutemos el estado como parte de la solución (en este caso, estamos actualizando los resultados parciales en un vector). Es una solución bastante artificial y optimicé el uso de la memoria de la tabla por lo que solo se necesita una fila a la vez, y aquí va:

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

De hecho, en este caso sería más natural escribir una iteración directa, mutando variables a lo largo del camino. En Racket , así es como se ve:

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

Podemos imprimir los resultados y verificar que las tres implementaciones que se muestran funcionen. Nuevamente, en 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 

Answer 2

Para agregar a la respuesta de Óscar , podemos usar el estilo de continuación y paso para convertir cualquier programa para usar llamadas de cola:

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

Puede decir que este programa no es tan satisfactorio, ya que existe un cierre que "crece". Pero están asignados en el montón. En el caso general, el objetivo de hacer una llamada de cola no es tanto sobre el rendimiento como sobre la seguridad del espacio: no se explota el contexto de la evaluación.

Answer 3

ACTUALIZACIÓN: Este problema tiene una solución matemática mucho más fácil que puede bajar a O (fila) utilizando solo factorial. Basado en eso, esto se reduce a:

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

Respuesta anterior:

Necesitas estudiar los patrones. Básicamente, desea iterar desde el principio del triángulo hasta que tenga suficiente información para producir un resultado. Es obvio que necesita la fila anterior para calcular la siguiente, por lo que debe ser un argumento que le dé y debe proporcionar la siguiente si la fila solicitada no es la actual. Esta solución es cola recusiva y rápida como el rayo.

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