ЕГЭ. Вопрос 16. Рекуррентные функции. Решение рекурсивной функцией

Задача

Дано:

• F(1)=1 при n <= 1
• F(n)=n+F(n−1) при n>1
• n - натуральное число

Найти: F(2023)−F(2020)

---

Решение рекурсивной функцией. Разбор

Принцип: Функция вызывает саму себя согласно рекуррентному соотношению

Рекурсия — это метод, когда функция вызывает саму себя с изменёнными аргументами до тех пор, пока не достигнет базового случая​

В данной задаче:

• Базовый случай: F(1)=1 — это "якорь" (база), где рекурсия останавливается​

• Рекурсивный случай: F(n)=n+F(n−1) — функция вызывает сама себя с меньшим аргументом

Как работает рекурсивный вызов (дерево вызовов):

F(2023) → нужно вычислить 2023 + F(2022)
  ↓
  F(2022) → нужно вычислить 2022 + F(2021)
    ↓
    F(2021) → нужно вычислить 2021 + F(2020)
      ↓
      F(2020) → нужно вычислить 2020 + F(2019)
        ↓
        ... (продолжается вниз)
        ↓
        F(3) → нужно вычислить 3 + F(2)
          ↓
          F(2) → нужно вычислить 2 + F(1)
            ↓
            F(1) → возвращает 1 (базовый случай!)

Затем начинается "раскрутка" назад:
F(1) = 1
F(2) = 2 + F(1) = 2 + 1 = 3
F(3) = 3 + F(2) = 3 + 3 = 6
F(4) = 4 + F(3) = 4 + 6 = 10
...
F(2020) = 2020 + F(2019) = ... (большое число)
F(2021) = 2021 + F(2020) = ...
F(2022) = 2022 + F(2021) = ...
F(2023) = 2023 + F(2022) = ...

Код на Python:

def F(n):
  if n == 1: return 1
  else:
    return n + F(n - 1)

print(F(2023) - F(2020))

Строка if n == 1: — проверка базового случая, без которого рекурсия будет бесконечной
Строка return n + F(n - 1) — рекурсивный вызов: функция вызывает саму себя с аргументом n−1n−1, что гарантирует постепенное приближение к базовому случаю
Строка print(F(2023) - F(2020)) — вычисление разности двух независимых рекурсивных вызовов

Пошаговое выполнение:

1. Сначала вычисляется F(2023):
   • Вызов F(2023) → 2023 + F(2022)
   • Вызов F(2022) → 2022 + F(2021)
   • Вызов F(2021) → 2021 + F(2020)
   • Вызов F(2020) → вычисляется полностью до F(1)
2. Затем вычисляется F(2020) заново (неэффективно!)
3. Вычитание: F(2023) - F(2020)

---

Минусы

Стек вызовов — это область памяти, где хранятся данные о всех незавершённых вызовах функций​

При вызове F(2023):

1. Создаётся запись для F(2023) в стеке

2. Затем для F(2022) (первый вызов ещё не завершён!)

3. Затем для F(2021), и так далее...

4. В итоге в стеке одновременно хранятся 2023 записи​

Проблема: В Python по умолчанию максимальная глубина рекурсии — около 1000 вызовов. При попытке вызвать F(2023) возникнет ошибка:

RecursionError: maximum recursion depth exceeded

Решение: Можно увеличить лимит с помощью:

import sys
sys.setrecursionlimit(3000)

Но это только откладывает проблему — для очень больших nn рекурсия всё равно непрактична

Избыточные вычисления:

• F(2020) вычисляется ДВАЖДЫ:

  • первый раз внутри F(2023)

  • второй раз отдельно для вычитания

Время выполнения: O(n) для каждого вызова, итого O(n²) в худшем случае.

---

Преимущества рекурсивного подхода

Простота реализации: Код максимально близок к математическому определению функции​

Понятность: Легко понять логику — каждый шаг соответствует одному рекурсивному соотношению​

Отладка: При малых значениях n легко проследить выполнение функции​

---

Когда использовать рекурсию

Рекурсивный подход оправдан для:

• Небольших значений n<100

• Обучения и понимания структуры задачи​

• Прототипирования решения перед оптимизацией​

Для больших n (как в задаче с 2023) лучше использовать динамическое программирование или аналитическую формулу
 

---

Оптимизация: мемоизация

Чтобы избежать повторных вычислений, можно сохранять уже вычисленные значения в словаре:​

cache = {}

def F(n):
    if n == 1:
        return 1
    if n in cache:  # Если уже вычисляли
        return cache[n]
    
    result = n + F(n - 1)
    cache[n] = result  # Сохраняем результат
    return result

print(F(2023) - F(2020))

 Это улучшает эффективность при множественных вызовах с одинаковыми аргументами

​