16 номер. Рекурсия
Вычисление рекурсивной функции
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0)=1, F(1)=3, F(2)=2
F(n) = F(n-1) · F(n-3) при n>2
Чему равно значение функции F(7)?
В ответе запишите только целое число.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Для вычисления F(7) нужны F(6) и F(4). В свою очередь, F(6) = F(5) · F(3), F(5) = F(4) · F(2), F(4) = F(3) · F(1), F(3) = F(2) · F(0). Подставляйте в обратном порядке, начиная с заданных F(0) = 1, F(1) = 3, F(2) = 2; сохраняйте F(3) и F(4), поскольку они используются повторно.
Ответ: 144.