🧠 Задание 16: Рекурсивные алгоритмы

Полное руководство: от ручного счета до программирования на Python

1. Теория рекурсии

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

Три правила выживания в рекурсии:

Базовый случай (Терминальное условие): точка выхода, где рекурсия прекращается (например, if n == 1: return 1).
Рекурсивный шаг: вызов функции, который приближает нас к базовому случаю (например, уменьшение n).
Стек вызовов: память, где хранятся незавершенные вызовы функций.

2. Как работает дерево вызовов

Для понимания сложных функций удобно рисовать «дерево». Каждый вызов разветвляется на новые вызовы.

F(4)
├── F(3)
│   ├── F(2)
│   └── F(1)
└── F(2)

3. Решение через Python (Классика)

Большинство задач 16 решаются простым переносом условия в код:

import sys
# Если рекурсия слишком глубокая, увеличиваем лимит:
sys.setrecursionlimit(3000)

def F(n):
    if n == 1:
        return 1
    if n > 1:
        return n * F(n - 1)

print(F(5))

4. Оптимизация (Мемоизация)

Если функция делает слишком много одинаковых вычислений (например, F(n-1) + F(n-2)), программа может зависнуть. Используем кэширование:

from functools import lru_cache

@lru_cache(None) # Запоминает результаты вызовов
def F(n):
    if n <= 2:
        return n
    return F(n-1) + F(n-2)

# Теперь даже F(500) вычислится мгновенно!

5. Табличный метод (Ручной счет)

Если Python недоступен или функция простая, считаем снизу вверх (от меньших n к большим):

n	Вычисление	Результат F(n)
1	Базовый случай	1
2	2 + F(1) = 2 + 1	3
3	3 + F(2) = 3 + 3	6
4	4 + F(3) = 4 + 6	10

🧩 Ловушки ЕГЭ

Огромные числа: Если ответ больше 10¹⁸, ручной счет невозможен, используйте Python (он автоматически работает с длинной арифметикой).
Взаимная рекурсия: Когда F(n) вызывает G(n), а G(n) вызывает F(n). В коде просто пишем две функции.
Сумма цифр: Часто просят найти не само F(n), а сумму его цифр. Используйте sum(int(d) for d in str(F(n))).

✅ Чек-лист проверки

1 Проверь строгость знаков (n < 5 или n <= 5).
2 Убедись, что не перепутал + и * в формуле.
3 Если считаешь на Python, проверь setrecursionlimit.

← Вернуться к списку конспектов