В 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, чтобы улучшить сложность? Я не могу прийти с решением. Это должно быть выполнимо с аккумуляторами, но я не могу понять это, можете ли вы мне помочь?
Трюк состоит в том, чтобы сохранить в переменных предыдущие состояния, для этой последовательности, в частности, есть три из них. Затем на каждой итерации мы обновляем значения
n-3
иn-2
и вычисляем значениеn-1
, используя другие предыдущие значения. Это то, что я имею в виду:Ваша функция
per
может принимать дополнительные параметры с именемm
,pn2
иpn3
, первая из которых является желаемым значением для которые вы хотите вычислить последовательность, а два других - результаты вычисления последовательности дляn - 2
иn - 3
.Затем вместо вызова
(per n)
и, если он будет вычислять предыдущие значения рекурсивно, вы начинаете с n = 3 (другие случаи легко), вызывая(aux-per 3 m 0 3)
и повторяя с возрастающими значениями доn
equalm
.Вы можете легко обновить
pn2
иpn3
во время движения, так как вы уже вычислили их. Я не тестировал его, поэтому, возможно, вам нужны дополнительные вспомогательные переменные, но подход один и тот же: определите функцию шага отn
доn + 1
, пока не достигнетеm
, используя функциональные параметры в качестве временного хранилища.Другой подход заключается в том, чтобы memoize не хвостовую рекурсивную функцию.