Подпрограммы и рекурсия, 11 класс: примеры с решением

Рекурсия — способ описать задачу через её же более простую версию. Из жизни: два зеркала напротив друг друга, где отражение содержит отражение, и так далее. Или матрёшка: внутри неё лежит такая же, только меньше.

В программировании рекурсивная подпрограмма решает задачу так: если случай совсем простой, она сразу даёт ответ. Если сложный, она вызывает саму себя для случая поменьше и использует его результат.

Классический пример — факториал: n! = n × (n − 1)!, а 0! = 1. Чтобы найти 4!, нужно знать 3!, для него нужно 2!, и так до 0!, который известен сразу.

Подпрограмма — именованный кусок кода, который можно вызывать много раз с разными данными. Функция возвращает значение (в Python для этого служит return). Процедура только выполняет действия и ничего не возвращает. В Паскале они разные, в Python процедурой считают функцию без return.

Рекурсия возможна, потому что подпрограмма вправе вызвать любую подпрограмму, в том числе себя. Подробнее о синтаксисе функций и параметров можно прочитать в теме основы программирования. Общую идею разбиения задачи на шаги даёт тема алгоритмы и исполнители.

У корректной рекурсии есть две обязательные части:

• базовый случай — условие, при котором функция возвращает ответ, не вызывая себя (для факториала это n = 0);
• рекурсивный шаг — вызов себя с аргументом, который приближает задачу к базовому случаю (n − 1).

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

Глубина рекурсии — сколько вызовов одновременно ждут своего завершения. Для fact(5) цепочка fact(5), fact(4), …, fact(0) даёт глубину 6. В Python по умолчанию допустимо около 1000 вложенных вызовов, потом возникает RecursionError. Поэтому в задачах с большими n рекурсию иногда заменяют циклом.

Типичное задание для 11 класса и ЕГЭ: функция задана рекурсивно, нужно посчитать, для скольких n она принимает заданное значение. Разберём свои данные.

Условие. F(0) = 0; F(n) = F(n // 2), если n > 0 и n чётно; F(n) = 1 + F(n − 1), если n нечётно. Сколько чисел n от 1 до 100 имеют F(n) = 3?

Шаг 1. Понять функцию на примере. F(13): число нечётное, значит 1 + F(12). F(12) = F(6) = F(3). F(3) = 1 + F(2), F(2) = F(1), F(1) = 1 + F(0) = 1. Получаем F(3) = 2, а F(13) = 3.

Шаг 2. Записать функцию кодом. Базовый случай ставим первым.

def F(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        return F(n // 2)
    return 1 + F(n - 1)

Шаг 3. Перебрать числа. Правая граница в range не входит, поэтому пишем 101.

count = 0
for n in range(1, 101):
    if F(n) == 3:
        count += 1
print(count)

Шаг 4. Проверить ответ. Программа выводит 33. Проверка: F(n) равна количеству единиц в двоичной записи n (у 13 = 1101 их три). Чисел до 127 с тремя единицами C(7, 3) = 35, из них больше 100 только 104 и 112. Значит, 35 − 2 = 33. Перевод в двоичную систему разбирается в теме системы счисления.

• Нет базового случая или он стоит после рекурсивного вызова. Если в примере выше убрать проверку n == 0, то F(0) начнёт вызывать F(0) бесконечно, и программа упадёт с RecursionError.
• Шаг не приближает к базе. Вызов fact(n + 1) вместо fact(n - 1) уводит от нуля, и цепочка не закончится.
• Обычное деление вместо целочисленного. В Python n / 2 даёт дробь (например, 3 / 2 = 1.5), а нужен n // 2. Для условия «n делится на k» используют n % k == 0.
• Неверная граница в переборе. range(1, 5000) не включает 5000. Если в условии «от 1 до 5000», пиши range(1, 5001).
• Путаница в условиях ветвей. Ветви рекурсивной функции не должны пересекаться и должны покрывать все n. Прочитай условие и проверь, какая ветвь сработает для 0, 1 и для числа, подходящего под оба условия.

Чаще всего это рекурсивная функция, заданная несколькими условиями. Нужно либо найти ошибки в готовом коде, либо написать программу, которая считает, сколько чисел из диапазона дают нужное значение. На странице есть такое задание с полным ходом решения.

Найди в списке выше похожее на твоё и сравни ход решения со своим. Если подходящего нет, сфотографируй своё задание и отправь на сайт, чтобы получить решение по шагам.