Perrin Number - как это сделать tailrecursive?

HappyR спросил: 13 июня 2018 в 07:05 в: racket

В Racket:

; Number -> Number
; interp. Calculates the perrin sequence.(check-expect (per 0) 3)
(check-expect (per 1) 0)
(check-expect (per 2) 2)
(check-expect (per 7) 7)
(check-expect (per 11) 22)(define (per n)
  (cond
    [(= n 0) 3]
    [(= n 1) 0]
    [(= n 2) 2]
    [else (+ (per (- n 2)) (per (- n 3)))]
    )
  )

Как это сделать в tailrecursion, чтобы улучшить сложность? Я не могу прийти с решением. Это должно быть выполнимо с аккумуляторами, но я не могу понять это, можете ли вы мне помочь?

racket

2 ответа

Есть решение

Óscar López ответил: 13 июня 2018 в 07:38

Трюк состоит в том, чтобы сохранить в переменных предыдущие состояния, для этой последовательности, в частности, есть три из них. Затем на каждой итерации мы обновляем значения n-3 и n-2 и вычисляем значение n-1, используя другие предыдущие значения. Это то, что я имею в виду:

(define (perrin n)
  ; use a named `let` for simplicity, alternatively
  ; we could use a separate procedure as a helper
  (let loop ((a 3) (b 0) (c 2) (n n))
    (if (zero? n)
        a
        (loop b c (+ a b) (sub1 n)))))

coredump ответил: 13 июня 2018 в 07:21

Ваша функция per может принимать дополнительные параметры с именем m, pn2 и pn3, первая из которых является желаемым значением для которые вы хотите вычислить последовательность, а два других - результаты вычисления последовательности для n - 2 и n - 3.

Затем вместо вызова (per n) и, если он будет вычислять предыдущие значения рекурсивно, вы начинаете с n = 3 (другие случаи легко), вызывая (aux-per 3 m 0 3) и повторяя с возрастающими значениями до n equal m.

Вы можете легко обновить pn2 и pn3 во время движения, так как вы уже вычислили их. Я не тестировал его, поэтому, возможно, вам нужны дополнительные вспомогательные переменные, но подход один и тот же: определите функцию шага от n до n + 1, пока не достигнете m, используя функциональные параметры в качестве временного хранилища.

Другой подход заключается в том, чтобы memoize не хвостовую рекурсивную функцию.