Пример 1
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n при n ≤ 3
F(n) = F(n–3) + F(n/3) + n, если n > 3 и кратно трём,
F(n) = F(n–1) + F(n–2), если n > 3 и не кратно трём.
Чему равно значение функции F(50) + F(65)?
Знак / обозначает операцию целочисленного деления.
Решить данное задание проще всего с использованием программы. Необходимо просто переписать данное рекуррентное соотношение в виде рекурсивной функции.
Базовым случаем является случай, когда
n ≤ 3, в этом случае функция должна вернуть просто значение
n.
Две другие строчки: вычисляющие
F(n), будут рекурсивными случаями, когда мы будем вызывать саму функцию с другими параметрами, зависящими от предыдущих и возвращать результат вычисления.
Основная программа будет вызывать рекурсивную функцию со значением
F(50) и
F(65). Результаты вычисления функции с этими параметрами складываются и выводится на экран.