Рекурсия помогает решать задачи, разбивая их на более простые шаги, и часто встречается в задании № 16 ЕГЭ по информатике. В статье разберём, как правильно строить рекурсивные функции, чтобы они не уходили в бесконечные вызовы, и какие элементы для этого необходимы. Покажем типичные ошибки и способы их избежать. Также рассмотрим примеры задач и приёмы ускорения с помощью кеширования.
Термины, которые будем использовать: рекурсия, кеш, кеширование, предел рекурсии, точка выхода (базовый случай), шаг рекурсии.
Что такое рекурсия
Рекурсия — это функция, которая вызывает саму себя.
def hello():
print(«Привет»)
hello()
# Вызывает саму себя
Такая рекурсия будет выполняться бесконечно, пока память не будет исчерпана либо пока не будет достигнут максимальный предел рекурсии.
Предел рекурсии — количество вызовов одной рекурсии. По умолчанию в Python предельная глубина рекурсии равна 1000.
Это значит, что если функция будет вызывать саму себя больше 1000 раз подряд, интерпретатор остановит выполнение и выдаст ошибку RecursionError: maximum recursion depth exceeded.
Это ограничение защищает программу от аварийного завершения. Каждый рекурсивный вызов занимает место в памяти (в стеке вызовов), и, если позволить рекурсии углубляться бесконечно, память может переполниться, что приведёт к серьёзному сбою. Значение 1000 — это безопасный порог, который работает на большинстве систем
Изменение предела рекурсии
Предел рекурсии можно изменить на любое другое число с помощью библиотеки sys и метода setrecursionlimit(), в качестве аргумента которому передаётся новое значение предела (обязательно int).
import sys
sys.setrecursionlimit(3000)
def hello():
print(«Привет»)
hello() # Вызывает саму себя
Теперь функция будет вызывать саму себя 3000 раз вместо 1000, пока не появится ошибка RecursionError, и программа завершится. Увеличение предела рекурсии не помогает избавиться от бесконечного вызова функции самой себя.
Что изменить, чтобы рекурсия не была бесконечной
Точка выхода — момент, когда функция перестаёт вызывать себя и возвращает конкретный ответ.
Шаг рекурсии (рекурсивный вызов) — вызов функции с изменёнными (упрощёнными) данными. Аналогия: «Скажи, сколько раз моргнуть? Если ноль раз — стоп. Если больше — моргни один раз и повтори с числом на один меньше».
Но наличия точки выхода недостаточно, чтобы остановить бесконечную рекурсию, например:
def f(x):
if x < 0:
return “stop”
return f(x+1)
Казалось бы, есть точка выхода (при отрицательном числе) и рекурсивный вызов с изменённым параметром. Но что произойдёт, если изначально вызывать функцию от положительного числа? Такое число с увеличением на единицу никогда не станет отрицательным.
def f(x):
if x < 0:
return “stop”
return f(x-1)
Такой базовый случай (точка выхода) будет достигнут всегда.
Кеширование
В большинстве случаев для вычисления каждого нового значения функции требуется найти (или знать) значение от другого предыдущего аргумента. По умолчанию рекурсия рассчитывает каждое значение заново — неважно, встретилось оно в первый раз или в десятый, но рекурсию можно улучшить, подключив кеширование.
@lru_cache — это декоратор, который автоматически кеширует (то есть сохраняет) результаты вызова функции для тех аргументов, с которыми она уже вызывалась. Если функция будет вызвана с теми же аргументами повторно, она не будет пересчитывать результат заново, а просто возьмёт его из кеша.
LRU расшифровывается как Least Recently Used («давно не использовавшийся»). Кеш хранит ограниченное количество результатов (по умолчанию 128) и при переполнении удаляет самые «старые» (реже всего использовавшиеся) записи.
@lru_cache() необходимо размещать непосредственно перед той функцией, к рекурсии которой он должен быть применён.
from functools import lru_cache
@lru_cache(3)
def square(x):
print(f»Вычисляем {x}^2…»)
return x * x
# Используем
print(square(2)) # Вычисляем 4
print(square(2)) # Берём из кеша 4
print(square(3)) # Вычисляем 9
print(square(4)) # Вычисляем 16
print(square(5)) # Вычисляем 25 (вытеснил 2 из кеша)
print(square(2)) # Снова вычисляем (уже нет в кеше)
Если задать параметр равным None, то в кеше будут сохраняться все вычисленные значения без ограничений.
Заключение
Теперь ты понимаешь, как работает рекурсия и из каких частей она состоит. Ты умеешь задавать базовый случай и делать шаг рекурсии так, чтобы функция не зацикливалась, можешь находить ошибки в рекурсивных функциях и при необходимости ускорять их с помощью кеширования. Эти знания помогут тебе выполнять задания с рекурсией из ЕГЭ по информатике. Решай больше задач — с практикой рекурсия станет намного понятнее.
Практикум
Задача 1
Напишите рекурсивную функцию возведения числа в степень.
def power(base, exponent):
# Базовый случай: любое число в степени 0 равно 1
if exponent == 0:
return 1
# Шаг рекурсии: base^exp = base * base^(exp-1)
return base * power(base, exponent — 1)
# Примеры использования
print(power(2, 0)) # 1
print(power(2, 3)) # 8
print(power(5, 4)) # 625
print(power(10, 2)) # 100
# Более эффективная версия (бинарное возведение в степень)
def power_fast(base, exponent):
if exponent == 0:
return 1
# Если степень чётная: a^n = (a^(n/2))^2
if exponent % 2 == 0:
half = power_fast(base, exponent // 2)
return half * half
# Если степень нечётная: a^n = a * a^(n-1)
else:
return base * power_fast(base, exponent — 1)
print(power_fast(2, 10)) # 1024
print(power_fast(3, 8)) # 6561
Обычная рекурсия делает n вызовов. Для больших степеней (например, 1000) может быть RecursionError. Используй быструю версию или циклы для больших чисел.
Задача 2
Напишите рекурсивную проверку, является ли строка палиндромом. Считать, что в строке нет пробелов и используется один регистр для всех букв.
def is_palindrome(s):
# Базовый случай 1: пустая строка или один символ — это палиндром
if len(s) <= 1:
return True
# Базовый случай 2: если первый и последний символы разные — не палиндром
if s[0] != s[-1]:
return False
# Шаг рекурсии: проверяем строку без первого и последнего символов
return is_palindrome(s[1:-1])
# Примеры использования
print(is_palindrome(«казак»)) # True
print(is_palindrome(«мадам»)) # True
print(is_palindrome(«шалаш»)) # True
print(is_palindrome(«привет»)) # False
# Версия с дополнительными параметрами (без создания новых строк)
def is_palindrome_efficient(s, left, right):
if left >= right:
return True
if s[left].lower() != s[right].lower():
return False
return is_palindrome_efficient(s, left + 1, right — 1)
# Использование эффективной версии
def check_palindrome(s):
return is_palindrome_efficient(s, 0, len(s) — 1)
print(check_palindrome(«топот»)) # True
print(check_palindrome(«радар»)) # True
print(check_palindrome(«python»)) # False
Первая версия создаёт новые строки (s[1:-1]), что тратит память. Вторая версия с индексами более эффективна.
Задача 3
Выведите все числа от A до B без циклов, используя рекурсию.
def print_range(a, b):
# Печатаем текущее число
print(a)
# Базовый случай: если достигли B, останавливаемся
if a == b:
return
# Шаг рекурсии: движемся в нужную сторону
if a < b:
print_range(a + 1, b) # Возрастающая последовательность
else:
print_range(a — 1, b) # Убывающая последовательность
# Примеры
print(«От 1 до 5:»)
print_range(1, 5) # 1 2 3 4 5
print(«\nОт 10 до 6:»)
print_range(10, 6) # 10 9 8 7 6
Эта задача отлично показывает, как рекурсия может заменить цикл, но для реального кода всегда используй for i in range(a, b + 1) — это быстрее и безопаснее.
Автор статьи
