ЕГЭ 16. Рекурсия

Сегодня разберём задачу, которая часто встречается на экзаменах и олимпиадах по информатике. На первый взгляд она простая, но таит в себе подводные камни. Мы пройдём путь от наивного решения до оптимального, а заодно разберёмся, что такое рекурсия, кэширование и динамическое программирование. Поехали! Дана функция F(n), где n — натуральное число. Она определена так: Требуется вычислить значение выражения F(3027) − F(3023). Казалось бы, чего проще — написать функцию на Python и вызвать её. Но не тут-то...

Рекурсия – это один из самых мощных и одновременно самых загадочных инструментов в программировании. Этот термин может вызывать ассоциации с бесконечным зацикливанием или сложными математическими формулами, но на самом деле рекурсия – это просто способ решения задач, который может сделать код более элегантным и понятным. Рекурсия – это процесс, при котором функция вызывает саму себя в своем теле. Это может показаться странным, но это мощный метод, который позволяет решать задачи, которые можно разбить на более мелкие, аналогичные задачи...