Хвостовая рекурсия Haskell

[gogoshik]

Здравствуйте! Мне нужно составить код для вычисления следующей рекуррентной последовательности: $a_0 = 1, a_1 = 2, a_2 = 3, a_n = a_{n-1} + a_{n-2} - 2a_{n-3}$. С помощью обычной рекурсии и хвостовой рекурсии.

С обычной я разобрался.

seq :: Integer -> Integer
seq n | n >= 0  && n <= 2   = (n + 1)
      | n > 2               = seq (n - 1) + seq (n - 2) - 2 * seq (n - 3)
      | otherwise           = error "arg must be >= 0" 

С хвостовой пока не получается. Помогите, пожалуйста.

[Pphantom]

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

[gogoshik]

По видимому это будет функция от четырех аргументов. Только какая она будет не понятно.

Что-нибудь вроде:

helperS n1 n2 n3 n = helperS n1 n2 (n1 + n2 - 2 * n3) (n - 2)

[Pphantom]

gogoshik в сообщении #1452950 писал(а):

Только какая она будет не понятно.

Допустим, вы пытаетесь считать какой-нибудь десятый член последовательности вручную. Что именно вы будете делать? Опишите свои действия - просто словами.

[gogoshik]

Pphantom в сообщении #1452959 писал(а):

Допустим, вы пытаетесь считать какой-нибудь десятый член последовательности вручную. Что именно вы будете делать? Опишите свои действия - просто словами.

Возьму 9, 8 и 7 члены последовательности и подставлю в данную рекуррентную формулу.

[arseniiv]

gogoshik в сообщении #1452950 писал(а):

helperS n1 n2 n3 n = helperS n1 n2 (n1 + n2 - 2 * n3) (n - 2)

Идея как будто та, но исполнение не то, да. Можно ещё попробовать как-то преобразовать исходную последовательность, чтобы её рекуррентная формула была вида $A_n = \ldots A_{n-1} \ldots$, без вхождений $A_{n-2}$ и так далее. Получится — и хвостовая рекурсия получится.

-- Чт апр 09, 2020 02:39:51 --

gogoshik в сообщении #1452960 писал(а):

Возьму 9, 8 и 7 члены последовательности и подставлю в данную рекуррентную формулу.

Но откуда они будут вам известны? А вот Pphantom может вполне намекать на динамическое программирование. (Результат тут везде правда выйдет одинаковый.)

[Pphantom]

gogoshik в сообщении #1452960 писал(а):

Возьму 9, 8 и 7 члены последовательности и подставлю в данную рекуррентную формулу.

А откуда вы их возьмете? Нет, честный набор действий напишите.

arseniiv в сообщении #1452963 писал(а):

Можно ещё попробовать как-то преобразовать исходную последовательность, чтобы её рекуррентная формула была вида $A_n = \ldots A_{n-1} \ldots$, без вхождений $A_{n-2}$ и так далее.

Можно, но это задача уже не по программированию. Так-то можно не мелочиться и просто найти явное выражение для $a_n$...

[arseniiv]

(СПОЙЛЕРНЫЙ ответ Pphantom)

Pphantom в сообщении #1452964 писал(а):

Можно, но это задача уже не по программированию.

Как раз по нему, я предлагаю последовательность $A_n = (a_n, a_{n+1}, a_{n+2})$.

[Pphantom]

arseniiv, тогда согласен.

[gogoshik]

Pphantom в сообщении #1452964 писал(а):

А откуда вы их возьмете? Нет, честный набор действий напишите.

Будет так:

a(0) = 1
a(1) = 2
a(2) = 3
a(n) = a(n-1) + a(n-2) - 2 * a(n-3)
n=3: a(3) = a(2) + a(1) - 2 * a(0) = 3 + 2 - 2 * 1 = 3
n=4: a(4) = a(3) + a(2) - 2 * a(1) = 3 + 3 - 2 * 2 = 2
n=5: a(5) = a(4) + a(3) - 2 * a(2) = 2 + 3 - 2 * 3 = -1
n=6: a(6) = a(5) + a(4) - 2 * a(3) = (-1) + 2 - 2 * 3 = -5
n=7: a(7) = a(6) + a(5) - 2 * a(4) = (-5) + (-1) - 2 * 2 = -10
n=8: a(8) = a(7) + a(6) - 2 * a(5) = (-10) + (-5) - 2 * (-1) = -13
n=9: a(9) = a(8) + a(7) - 2 * a(6) = (-13) + (-10) - 2 * (-5) = -13
n=10: a(10) = a(9) + a(8) - 2 * a(7) = (-13) + (-13) - 2 * (-10) = -6 


a(0) = 1
a(1) = 2
a(2) = 3
a(n+3) = a(n+2) + a(n+1) - 2 * a(n)
n=0: a(3) = a(2) + a(1) - 2 * a(0) = 3 + 2 - 2 * 1 = 3
n=1: a(4) = a(3) + a(2) - 2 * a(1) = 3 + 3 - 2 * 2 = 2
n=2: a(5) = a(4) + a(3) - 2 * a(2) = 2 + 3 - 2 * 3 = -1
n=3: a(6) = a(5) + a(4) - 2 * a(3) = (-1) + 2 - 2 * 3 = -5
n=4: a(7) = a(6) + a(5) - 2 * a(4) = (-5) + (-1) - 2 * 2 = -10
n=5: a(8) = a(7) + a(6) - 2 * a(5) = (-10) + (-5) - 2 * (-1) = -13
n=6: a(9) = a(8) + a(7) - 2 * a(6) = (-13) + (-10) - 2 * (-5) = -13
n=7: a(10) = a(9) + a(8) - 2 * a(7) = (-13) + (-13) - 2 * (-10) = -6 


n=0: a(0) = 1
n=1: a(1) = 2
n=2: a(2) = 3
k = n - 3
a(n) = a(k+2) + a(k+1) - 2 * a(k)
n=3, k=0: a(3) = a(2) + a(1) - 2 * a(0) = 3 + 2 - 2 * 1 = 3
n=4, k=1: a(4) = a(3) + a(2) - 2 * a(1) = 3 + 3 - 2 * 2 = 2
n=5, k=2: a(5) = a(4) + a(3) - 2 * a(2) = 2 + 3 - 2 * 3 = -1
n=6, k=3: a(6) = a(5) + a(4) - 2 * a(3) = (-1) + 2 - 2 * 3 = -5
n=7, k=4: a(7) = a(6) + a(5) - 2 * a(4) = (-5) + (-1) - 2 * 2 = -10
n=8, k=5: a(8) = a(7) + a(6) - 2 * a(5) = (-10) + (-5) - 2 * (-1) = -13
n=9, k=6: a(9) = a(8) + a(7) - 2 * a(6) = (-13) + (-10) - 2 * (-5) = -13
n=10, k=7: a(10) = a(9) + a(8) - 2 * a(7) = (-13) + (-13) - 2 * (-10) = -6  

[Pphantom]

Угу. А теперь смотрите: вы каждый раз используете три уже вычисленных ранее значения, двигаясь в сторону роста номера до тех пор, пока не добираетесь до нужного. После этого процесс останавливается и на выход выдается последний результат. Сможете теперь описать функцию, которая "реализует" одну строчку ваших выкладок?

[gogoshik]

В общем получается что-то такое:

seQ n | n >= 0      = seqHelp n 3 2 1 
      | otherwise   = error "arg must be >= 0"

seqHelp 0 _ _ pp = pp
seqHelp 1 _ p _  = p
seqHelp 2 c _ _  = c
seqHelp n c p pp = let q = c + p - 2 * pp in seqHelp (n - 1) q c p

*Test> seQ 301
1276538859311178639666612897162414
(0.02 secs, 8240640 bytes)

Спасибо!

[Pphantom]

Да. Это не единственный возможный вариант, но вполне подходящий.

[arseniiv]

Да, я бы его немножко подсократил и заодно скрыл бы хелпер от глаз других функций того же модуля, окажись их много:

Используется синтаксис Haskell

a n | n >= 0    = go n 1 2 3
    | otherwise = error "a: arg must be nonnegative"
    where
      go 0 a0 _  _  = a0
      go n a0 a1 a2 = go (n - 1) a1 a2 (a2 + a1 - 2 * a0)

More is less. Чем меньше можно нечайно сломать, тем лучше.

UPD: Учёл совет warlock66613 ниже.

[warlock66613]

Я бы ещё переименовал h в go - это общепринятое название для функции-шага хвостовой рекурсии и его использование упростит чтение кода другими людьми.