По информатике есть достаточно простое (быстрореализуемое и понятное) задание с рекурсией № 16. Исходя из условия, функция, для которой требуется написать программу, вызывает сама себя и сразу напрашивается решение рекурсией.
Рекурсия традиционно считается темой сложной для новичков, хотя в самом понятии рекурсии ничего сложного и нет. Более того, когда смотришь на решение задачи с применением рекурсии всё понятно и красиво.
А вот увидеть решение рекурсией в новой задаче – не всегда очевидно. Однако в задании 16 рекурсия задана самим условием и просится на реализацию.
В демоверсии задание 16 выглядит следующим образом :
Дело в том, что при программировании вы наткнетесь на ограничение на глубину рекурсии (в Python глубина по умолчанию обычно 1000). Связанно это с возможным переполнением стека.
Т.е., если просто реализовать условие задачи — программа выдаст ошибку: maximum recursion depth exceeded in comparison.
Можно, конечно, написать директиву и увеличить глубину рекурсии (что увеличит потребление оперативной памяти и до бесконечности пользоваться этим приемом нельзя), тогда ошибки не будет. В рамках ЕГЭ такое решение вполне рабочее.
В программировании, чтобы избежать проблем с глубокой или широкой рекурсией, используется мемоизация (запоминание по-русски).
В вычислительной технике мемоизация — это метод оптимизации, используемый в первую очередь для ускорения программы, сохраняя результаты ранее вызванных функций и возвращая сохраненный результат при попытке вычислить ту же последовательность. Это также может называться кэшированием.
Суть метода — в создании структуры данных (в примере ниже — это словарь) для запоминания уже рассчитанных значений функции, чтобы не обращаться к рекурсии без надобности.
Можно использовать кэширование (мемоизацию) с помощью специально для этого предусмотренного декоратора Python
Выглядит решение с рекурсией просто. Но программируя, стоит знать, что рекурсивная функция работает медленнее обычного перебора (итерации), поэтому ркуурсию стоит применять, если решить задачу без этого сложно.
Решим задание ЕГЭ №16 без рекурсии
Создадим список (массив) из 2024+1 элементов (помним, что индексация в списке начинается с 0, и чтобы обратиться в списке к элементу 2024 потребуется как минимум список на 2024+1=2025 элементов). Для начала заполним его нулями. В python это удобно сделать помощью генератора:
f= [0 for i in range(2025)]
Из условия задачи:
f[1]=1, остальные элементы заполним с помощью цикла.
Если немного подумать, то необязательно хранить такой большой массив данных. Для ответа требуются всего три расчетные величины назовем их f24, f23, f22, и предыдущее значение f, используемое в цикле.
Любого решения, из приведенных выше, достаточно для ЕГЭ.
Задание 16 — это повод поговорить о способах реализации рекурсивной функции в Python, и альтернативной ее замене простой итерацией.
