Задание EGEINF1644D5: Рекурсия и рекуррентные зависимости

Дано: аргумент n — натуральное число. Правила вычисления:
F(n) = 1 при n ≤ 2.
F(n) = F(n − 2) − F(n − 1) при n ≥ 3 и n чётно.
F(n) = 2 · F(n − 1) − F(n − 2) при n ≥ 3 и n нечётно.
Найти R = F(18).

Рекурсия ссылается только на меньшие аргументы. Поэтому вычисляем значения по возрастанию n, начиная с базы. Для каждого нового n сначала определяем его чётность, затем выбираем ровно соответствующую формулу. Значения предыдущих аргументов уже известны; менять местами чётную и нечётную ветви нельзя.

F(1) = 1.
F(2) = 1.
F(3) = 2 · F(3 − 1) − F(3 − 2) = 2 · 1 − 1 = 1.
F(4) = F(4 − 2) − F(4 − 1) = 1 − 1 = 0.
F(5) = 2 · F(5 − 1) − F(5 − 2) = 2 · 0 − 1 = -1.
F(6) = F(6 − 2) − F(6 − 1) = 0 − (−1) = 1.
F(7) = 2 · F(7 − 1) − F(7 − 2) = 2 · 1 − (−1) = 3.
F(8) = F(8 − 2) − F(8 − 1) = 1 − 3 = -2.
F(9) = 2 · F(9 − 1) − F(9 − 2) = 2 · (−2) − 3 = -7.
F(10) = F(10 − 2) − F(10 − 1) = (−2) − (−7) = 5.
F(11) = 2 · F(11 − 1) − F(11 − 2) = 2 · 5 − (−7) = 17.
F(12) = F(12 − 2) − F(12 − 1) = 5 − 17 = -12.
F(13) = 2 · F(13 − 1) − F(13 − 2) = 2 · (−12) − 17 = -41.
F(14) = F(14 − 2) − F(14 − 1) = (−12) − (−41) = 29.
F(15) = 2 · F(15 − 1) − F(15 − 2) = 2 · 29 − (−41) = 99.
F(16) = F(16 − 2) − F(16 − 1) = 29 − 99 = -70.
F(17) = 2 · F(17 − 1) − F(17 − 2) = 2 · (−70) − 99 = -239.
F(18) = F(18 − 2) − F(18 − 1) = (−70) − (−239) = 169.

Требуемое значение: R = F(18) = 169.

Проверка. Начальные значения совпадают с базой из условия. Каждая следующая строка использует только уже вычисленные значения и свою ветвь по чётности. Повторный расчёт по зависимостям от искомого аргумента к базовым даёт тот же результат 169. Никакие значения в таблице не округляются.

Ответ: 169.