Функции и рекурсия в Python: полный разбор для ЕГЭ
Функции и рекурсия — одна из ключевых тем кодификатора ЕГЭ по информатике. Без понимания того, как определять функции, передавать параметры и использовать рекурсию, невозможно решить задачи высокого уровня сложности. В этом разборе вы узнаете, что такое функции в Python, как работают локальные и глобальные переменные, и как применять рекурсию на практике. Материал рассчитан на учеников 10-11 классов и сопровождается реальными примерами из ЕГЭ. Если вам нужна индивидуальная помощь или разбор сложной задачи, обратитесь к AI-репетитору Наставник — он объяснит любую тему голосом персонажа, который вам нравится.
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.
Определение функции (def)
Функция в Python — это именованный блок кода, который выполняет определённое действие. Она определяется с помощью ключевого слова def, после которого идёт имя функции, круглые скобки с параметрами (если они есть) и двоеточие. Тело функции пишется с отступом. Функция может возвращать результат с помощью оператора return. Если return не указан, функция возвращает None.
Пример простой функции:
def greet(name):
return "Привет, " + name
Функция вызывается по имени с передачей аргументов: greet("Анна") вернёт "Привет, Анна".
На ЕГЭ важно уметь читать и писать функции, особенно в задачах на обработку чисел и строк. Часто встречаются функции, которые вычисляют факториал, сумму цифр или проверяют простоту числа.
Напишите функцию, которая принимает целое число n и возвращает сумму его цифр. Пример: sum_digits(123) → 6.
def sum_digits(n):
s = 0
while n > 0:
s += n % 10
n //= 10
return s
Шаг 1: Определяем функцию sum_digits с параметром n.
Шаг 2: Инициализируем переменную s = 0 для хранения суммы.
Шаг 3: В цикле while, пока n > 0, добавляем последнюю цифру (n % 10) к s, затем отбрасываем её (n //= 10).
Шаг 4: Возвращаем сумму s.
Параметры и возвращаемое значение
Параметры функции — это переменные, которые получают значения при вызове. В Python параметры могут быть обязательными и необязательными (со значениями по умолчанию). Возвращаемое значение — это результат, который функция передаёт в место вызова. Можно вернуть несколько значений, перечислив их через запятую (на самом деле возвращается кортеж).
Пример возврата нескольких значений:
def min_max(a, b):
return min(a, b), max(a, b)
Вызов: mn, mx = min_max(5, 3) → mn=3, mx=5.
На ЕГЭ часто встречаются задачи, где нужно написать функцию, которая принимает список и возвращает, например, количество чётных элементов. Или функцию, которая по двум числам возвращает их наибольший общий делитель.
Напишите функцию gcd(a, b), которая возвращает наибольший общий делитель чисел a и b с помощью алгоритма Евклида. Пример: gcd(12, 8) → 4.
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
Шаг 1: Определяем функцию с двумя параметрами.
Шаг 2: Пока b не равно 0, в цикле присваиваем a значение b, а b — остаток от деления a на b.
Шаг 3: Когда b станет 0, a содержит НОД. Возвращаем a.
Локальные и глобальные переменные
Переменные, определённые внутри функции, называются локальными. Они существуют только во время выполнения функции и не видны за её пределами. Переменные, определённые вне функции, — глобальные. Они доступны внутри функции, но для изменения глобальной переменной внутри функции нужно использовать ключевое слово global.
Пример:
x = 10
def change():
global x
x = 20
После вызова change() глобальная x станет 20.
На ЕГЭ важно понимать, как изменение переменных внутри функции влияет на внешний код. Часто в задачах требуется проанализировать, что выведет программа с учётом областей видимости.
Что выведет следующая программа?
a = 5
def func():
a = 10
print(a)
func()
print(a)
Шаг 1: Глобальная переменная a = 5.
Шаг 2: Внутри функции func создаётся локальная переменная a = 10, которая не влияет на глобальную.
Шаг 3: Вызов func() печатает 10.
Шаг 4: После вызова печатается глобальная a = 5.
Ответ: 10 и 5.
Рекурсия и её ограничения
Рекурсия — это вызов функцией самой себя. Каждый рекурсивный вызов должен приближать задачу к базовому случаю, при котором рекурсия прекращается. Без базового случая рекурсия станет бесконечной и вызовет ошибку переполнения стека (RecursionError).
Пример рекурсивной функции факториала:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
Рекурсия удобна для задач с рекуррентными соотношениями, обхода деревьев, но имеет ограничения: глубина рекурсии в Python по умолчанию ограничена 1000 вызовами. При превышении возникает ошибка. Это важно учитывать на ЕГЭ: если задача требует большого числа рекурсивных вызовов, лучше использовать цикл.
На ЕГЭ рекурсия часто встречается в задачах на вычисление чисел Фибоначчи, факториала, а также в задачах на обработку последовательностей (например, функция Аккермана).
Напишите рекурсивную функцию fib(n), которая возвращает n-е число Фибоначчи (нумерация с 0). Пример: fib(6) → 8.
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
Шаг 1: Базовые случаи: fib(0)=0, fib(1)=1.
Шаг 2: Для n>1 возвращаем сумму двух предыдущих чисел.
Недостаток: экспоненциальная сложность. Для ускорения можно использовать мемоизацию или цикл.
Дана рекурсивная функция:
def f(n):
if n < 3:
return 1
else:
return f(n-1) + f(n-2)
Чему равно f(5)?
Шаг 1: Вычислим f(0)=1, f(1)=1, f(2)=1 (так как n<3).
Шаг 2: f(3) = f(2)+f(1) = 1+1 = 2.
Шаг 3: f(4) = f(3)+f(2) = 2+1 = 3.
Шаг 4: f(5) = f(4)+f(3) = 3+2 = 5.
Ответ: 5.
Разбор типовых задач ЕГЭ на функции и рекурсию
В ЕГЭ по информатике задачи на функции и рекурсию могут быть как в первой части (тестовые), так и во второй (развёрнутый ответ). Рассмотрим несколько примеров повышенной сложности, которые помогут подготовиться к экзамену.
Напишите рекурсивную функцию, которая определяет, является ли строка палиндромом. Используйте только срезы и рекурсию. Пример: is_palindrome("radar") → True.
def is_palindrome(s):
if len(s) <= 1:
return True
if s[0] != s[-1]:
return False
return is_palindrome(s[1:-1])
Шаг 1: Базовый случай: если длина строки 0 или 1, это палиндром.
Шаг 2: Если первый и последний символы не совпадают, возвращаем False.
Шаг 3: Иначе вызываем функцию для подстроки без первого и последнего символов.
Дана рекурсивная функция:
def F(n):
if n > 2:
return F(n-1) + F(n-2)
else:
return n
Найдите значение F(5).
Шаг 1: F(0)=0, F(1)=1, F(2)=2 (так как n<=2).
Шаг 2: F(3) = F(2)+F(1) = 2+1=3.
Шаг 3: F(4) = F(3)+F(2) = 3+2=5.
Шаг 4: F(5) = F(4)+F(3) = 5+3=8.
Ответ: 8.
Частые вопросы
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.