Есть ли более эффективный способ написать этот рекурсивный процесс?

Question

Меня попросили написать процедуру, которая вычисляет элементы треугольника Паскаля с помощью рекурсивного процесса. Я могу создать процедуру, которая возвращает одну строку в треугольнике или число в определенной строке.

Вот мое решение:

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

Кажется, это работает нормально, но становится действительно неэффективно находить элементы большего ряда, начиная с (f 8), Есть ли лучшая процедура, которая решает эту проблему с помощью рекурсивного процесса?

Кроме того, как бы я написал это, если я хочу использовать итеративный процесс (хвостовая рекурсия)?

Answer 1

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

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

В качестве альтернативы, заимствуя из решения @Sylwester, мы можем написать чисто функциональную хвостовую рекурсивную итерационную версию, которая использует списки для хранения предварительно вычисленных значений; в моих тестах это медленнее, чем в предыдущей версии:

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

В любом случае это работает как ожидается для больших входов, это будет быстро для n значения порядка пары тысяч:

(f 10)
=> '(1 9 36 84 126 126 84 36 9 1)

Answer 2

Уже представлено несколько решений, и они указывают на то, что использование динамического программирования является хорошим вариантом здесь. Я думаю, что это можно написать немного проще, хотя. Вот что я бы сделал как простое решение на основе списка. Это основано на наблюдении, что если строка n - (abcde), то строка n+1 - (a (+ ab) (+ bc) (+ cd) (+ de) e). Легко вычислить, что нужно перебрать хвосты (0 a b c d e) сбора ((+ 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)

Это позволило использовать вспомогательную функцию 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))