ЕГЭ·ОГЭ

Рекурсивные функции: задание 16 ЕГЭ

Теория

Рекурсивная функция определяется через свои значения при меньших аргументах и базовый случай. Считать удобнее снизу вверх: — каждое значение по уже найденным.

Алгоритм решения

  1. Выпиши базовый случай.
  2. Посчитай значения по порядку (или программой с кэшем).
  3. Возьми .

Задачи по подтипам (10)

Рекурсивная функция · 10

  1. №1Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  2. №2Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  3. №3Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  4. №4Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  5. №5Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  6. №6Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  7. №7Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  8. №8Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  9. №9Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?
  10. №10Алгоритм вычисления функции , где — натуральное число: при ; при . Чему равно значение ?

Тренировка по подтипу

Тест по этим заданиям

10 новых задач подряд, ответы проверяются в конце — как на экзамене.

Вопросы и ответы

Почему рекурсия в Python бывает медленной?
Без кэша одни и те же значения пересчитываются много раз; @lru_cache это исправляет.