Олимпиадный тренинг

Задача . L3-T7. Количество вызовов при взаимной рекурсии F и G


Задача

Темы:

Функции F(n) и G(n), где n — натуральное число, вычисляются по правилам:

F(n) = 1 при n ≤ {1}
F(n) = F(n − 1) + G(n − 2) при n > {1};
G(n) = 1 при n ≤ {2}
G(n) = G(n − 1) + F(n − 1) при n > {2}.

Вычисления выполняются без сохранения промежуточных результатов. Сколько всего вызовов функций F и G, включая первоначальный, произойдёт при вычислении F({3})?


Статистика успешных решений по компиляторам
Комментарий учителя