16 задание. Рекурсивные алгоритмы

16 задание. Рекурсивные алгоритмы Это задание проверяет умение работать с рекурсивными алгоритмами и вычислять значения функций, заданных рекуррентными соотношениями. Требуется найти значение большого числового выражения, подставляя правила из условия.  Используется рекурсия, то есть функция, которая вызывает саму себя от других (обычно меньших) аргументов. Решается в основном на Python: Напрямую через написание функции с помощью def. Часто даются числа большие, и программа может закончиться ошибкой, так как стандартная глубина рекурсии меньше той, которая необходима. И тогда применяется модуль sys, который позволяет задать лимит глубины рекурсии побольше через setrecursionlimit. Изменить лимит можно еще с помощью декоратора @sys.setrecursionlimit Другой вариант это использование кеш, то есть сохранение результатов работы рекурсивной функции, для чего используют декоратор  @functools.lru_cache. Можно совместить эти способы.  Ну и ещё один вариант это заменить  рекурсию на обычный цикл (динамическое программирование). Но в этом случае нужно понимать что ищет данная в задании рекурсия.  Ну и наконец, в этом задании тоже можно применить аналитический способ через ручной расчет. Этот способ можно применять для решения задач, в которых вычисления получаются не громоздкими, то есть или мало ходов, или есть возможность сократить дроби, или можно найти  закономерности (например, арифметической прогрессии). Такие вычисления выручают при огромных аргументах в условиях ограничения времени. Но эти типы заданий нужно знать.  Я же рекомендую все же использовать первый способ. Пока не попадалось заданий, где бы он не работал.