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

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

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

F(0) = 0.
F(1) = 0.
F(2) = 22 + F(2 − 1) = 22 + 0 = 1.
F(3) = 2 · F(3 − 1) + 2 = 2 · 1 + 2 = 4.
F(4) = 42 + F(4 − 1) = 42 + 4 = 6.
F(5) = 2 · F(5 − 1) + 2 = 2 · 6 + 2 = 14.
F(6) = 62 + F(6 − 1) = 62 + 14 = 17.
F(7) = 2 · F(7 − 1) + 2 = 2 · 17 + 2 = 36.
F(8) = 82 + F(8 − 1) = 82 + 36 = 40.
F(9) = 2 · F(9 − 1) + 2 = 2 · 40 + 2 = 82.
F(10) = 102 + F(10 − 1) = 102 + 82 = 87.
F(11) = 2 · F(11 − 1) + 2 = 2 · 87 + 2 = 176.
F(12) = 122 + F(12 − 1) = 122 + 176 = 182.
F(13) = 2 · F(13 − 1) + 2 = 2 · 182 + 2 = 366.
F(14) = 142 + F(14 − 1) = 142 + 366 = 373.
F(15) = 2 · F(15 − 1) + 2 = 2 · 373 + 2 = 748.
F(16) = 162 + F(16 − 1) = 162 + 748 = 756.
F(17) = 2 · F(17 − 1) + 2 = 2 · 756 + 2 = 1514.
F(18) = 182 + F(18 − 1) = 182 + 1514 = 1523.
F(19) = 2 · F(19 − 1) + 2 = 2 · 1523 + 2 = 3048.
F(20) = 202 + F(20 − 1) = 202 + 3048 = 3058.
F(21) = 2 · F(21 − 1) + 2 = 2 · 3058 + 2 = 6118.
F(22) = 222 + F(22 − 1) = 222 + 6118 = 6129.
F(23) = 2 · F(23 − 1) + 2 = 2 · 6129 + 2 = 12260.
F(24) = 242 + F(24 − 1) = 242 + 12260 = 12272.
F(25) = 2 · F(25 − 1) + 2 = 2 · 12272 + 2 = 24546.
F(26) = 262 + F(26 − 1) = 262 + 24546 = 24559.

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

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

Ответ: 24559.