Рекурсия помогает решать задачи, разбивая их на более простые шаги, и часто встречается в задании № 16 ЕГЭ по информатике. В статье разберём, как правильно строить рекурсивные функции, чтобы они не уходили в бесконечные вызовы, и какие элементы для этого необходимы. Покажем типичные ошибки и способы их избежать. Также рассмотрим примеры задач и приёмы ускорения с помощью кеширования.
Термины, которые будем использовать: рекурсия, кеш, кеширование, предел рекурсии, точка выхода (базовый случай), шаг рекурсии.
Что такое рекурсия
def hello():
print(«Привет»)
hello()
# Вызывает саму себя
Такая рекурсия будет выполняться бесконечно, пока память не будет исчерпана либо пока не будет достигнут максимальный предел рекурсии.
Это значит, что если функция будет вызывать саму себя больше 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) — это быстрее и безопаснее.
