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

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

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

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

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

(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 равна (a b c d e), то строка n + 1 равна (a (+ a b) (+ b c) (+ c d) (+ d e) 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))