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

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

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

F(0) = 0.
F(1) = 0.
F(2) = 2 · F(2 − 1) = 2 · 0 = 0.
F(3) = 2 · 3 + F(3 − 1) = 2 · 3 + 0 = 6.
F(4) = 2 · F(4 − 1) = 2 · 6 = 12.
F(5) = 2 · 5 + F(5 − 1) = 2 · 5 + 12 = 22.
F(6) = 2 · F(6 − 1) = 2 · 22 = 44.
F(7) = 2 · 7 + F(7 − 1) = 2 · 7 + 44 = 58.
F(8) = 2 · F(8 − 1) = 2 · 58 = 116.
F(9) = 2 · 9 + F(9 − 1) = 2 · 9 + 116 = 134.
F(10) = 2 · F(10 − 1) = 2 · 134 = 268.
F(11) = 2 · 11 + F(11 − 1) = 2 · 11 + 268 = 290.
F(12) = 2 · F(12 − 1) = 2 · 290 = 580.
F(13) = 2 · 13 + F(13 − 1) = 2 · 13 + 580 = 606.
F(14) = 2 · F(14 − 1) = 2 · 606 = 1212.
F(15) = 2 · 15 + F(15 − 1) = 2 · 15 + 1212 = 1242.
F(16) = 2 · F(16 − 1) = 2 · 1242 = 2484.
F(17) = 2 · 17 + F(17 − 1) = 2 · 17 + 2484 = 2518.
F(18) = 2 · F(18 − 1) = 2 · 2518 = 5036.
F(19) = 2 · 19 + F(19 − 1) = 2 · 19 + 5036 = 5074.
F(20) = 2 · F(20 − 1) = 2 · 5074 = 10148.
F(21) = 2 · 21 + F(21 − 1) = 2 · 21 + 10148 = 10190.
F(22) = 2 · F(22 − 1) = 2 · 10190 = 20380.

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

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

Ответ: 20380.