16 номер. Рекурсия
Вычисление рекурсивной функции
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n)=1 при n=1
F(n) = n + F(n - 1) если n – чётно
F(n) = 2 · F(n - 2) если n > 1 и при этом n – нечётно.
Чему равно значение функции F(26)?
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Для чётного аргумента 26 используется F(26) = 26 + F(25). Аргумент 25 нечётный: здесь нужна другая ветвь, F(25) = 2 · F(23). Продолжая по нечётным аргументам, от 25 до 1 получаем 12 удвоений, поэтому выражение для ответа — 26 + 2^12 · F(1). База F(1) = 1.
Ответ: 4122.