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

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

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

F(1) = 1.
F(2) = 2 + F(2 − 1) = 2 + 1 = 3.
F(3) = 2 · F(3 − 2) = 2 · 1 = 2.
F(4) = 4 + F(4 − 1) = 4 + 2 = 6.
F(5) = 2 · F(5 − 2) = 2 · 2 = 4.
F(6) = 6 + F(6 − 1) = 6 + 4 = 10.
F(7) = 2 · F(7 − 2) = 2 · 4 = 8.
F(8) = 8 + F(8 − 1) = 8 + 8 = 16.
F(9) = 2 · F(9 − 2) = 2 · 8 = 16.
F(10) = 10 + F(10 − 1) = 10 + 16 = 26.
F(11) = 2 · F(11 − 2) = 2 · 16 = 32.
F(12) = 12 + F(12 − 1) = 12 + 32 = 44.
F(13) = 2 · F(13 − 2) = 2 · 32 = 64.
F(14) = 14 + F(14 − 1) = 14 + 64 = 78.
F(15) = 2 · F(15 − 2) = 2 · 64 = 128.
F(16) = 16 + F(16 − 1) = 16 + 128 = 144.
F(17) = 2 · F(17 − 2) = 2 · 128 = 256.
F(18) = 18 + F(18 − 1) = 18 + 256 = 274.
F(19) = 2 · F(19 − 2) = 2 · 256 = 512.
F(20) = 20 + F(20 − 1) = 20 + 512 = 532.
F(21) = 2 · F(21 − 2) = 2 · 512 = 1024.
F(22) = 22 + F(22 − 1) = 22 + 1024 = 1046.
F(23) = 2 · F(23 − 2) = 2 · 1024 = 2048.
F(24) = 24 + F(24 − 1) = 24 + 2048 = 2072.

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

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

Ответ: 2072.