Хвост-рекурсивный треугольник Паскаля на схеме

Question

Недавно я начал читать SICP, и мне очень интересно преобразовать рекурсивную процедуру в хвостово-рекурсивную форму.

Для "одномерных" ситуаций (линейных), таких как ряд Фибоначчи или факториальное вычисление, нетрудно выполнить преобразование.

Например, как говорится в книге, мы можем переписать вычисление Фибоначчи следующим образом

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

И эта форма явно хвостовая рекурсивная

Однако для "двумерной" ситуации, такой как вычисление треугольника Паскаля (пример 1.12 в SICP), мы все еще можем легко написать рекурсивное решение, как следует

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

Вопрос в том, как преобразовать это в хвостовую рекурсивную форму?

Answer 1

Прежде всего, рекурсивный процесс pascal Процедура может быть выражена более простым способом (предполагая неотрицательные, допустимые входные данные) - как это:

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

Теперь по вопросу. Можно преобразовать реализацию рекурсивного процесса в версию итеративного процесса, использующую хвостовую рекурсию. Но это сложнее, чем кажется, и чтобы полностью понять это, вы должны понять, как работает динамическое программирование. Подробное описание этого алгоритма см. В Руководстве по разработке алгоритмов Стивена Скиены, 2-е издание, стр. 278.

Это тот алгоритм, который не подходит для идиоматического решения в Scheme, потому что он требует, чтобы мы изменяли состояние как часть решения (в этом случае мы обновляем частичные результаты в векторе). Это довольно надуманное решение, и я оптимизировал использование памяти таблицей, так что требуется только одна строка за раз - и вот оно:

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

Фактически, в этом случае было бы более естественным написать прямую итерацию, изменяющую переменные по пути. В Racket это выглядит так:

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

Мы можем напечатать результаты и проверить, что все три показанные реализации работают. Опять в Ракетке:

(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

ОБНОВЛЕНИЕ: У этой задачи гораздо более простое математическое решение, которое можно перейти к O(строке), используя только факториал. Исходя из этого, это сводится к:

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

Старый ответ:

Вам нужно изучить шаблоны. По сути, вы хотите выполнить итерацию от начала треугольника до тех пор, пока у вас не будет достаточно информации для получения результата. Очевидно, что вам нужна предыдущая строка для вычисления следующей, так что это должен быть аргумент, который вы ей даете, и он должен предоставлять следующую, если запрошенная строка не является текущей. Это решение рекурсивно и молниеносно.

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

Answer 3

Чтобы добавить к ответу Оскара, мы можем использовать стиль передачи продолжения для преобразования любой программы в хвостовые вызовы:

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

Вы можете сказать, что эта программа не так удовлетворительна, так как есть закрытие, которое "растет". Но они расположены в куче. В общем случае смысл хвостового вызова заключается не столько в производительности, сколько в безопасности пространства: вы не взрываете контекст оценки.