Рекурсия — практикум

10 класс, углублённый уровень. Занятие двенадцатое. Функция, которая зовёт сама себя: база и шаг, стек вызовов, печать на спуске и на подъёме, дерево вызовов, как у фрактала, и функция, заданная формулой, — как в задании 16 ЕГЭ.

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

Часть 1. Тренажёр: как работает рекурсия

Шесть типов задач, по одной на каждый. Считать в уме или на бумаге: выпиши вызовы столбиком — каждый следующий ступенькой правее, — дойди до базы, а потом поднимайся и подставляй ответы снизу вверх. Ответ — всё напечатанное через пробел, или число, о котором спрашивают. Ошибся — ниже появится разбор рисунком: вызовы лесенкой по глубине стека, что каждый вернул, где была печать, — и кнопка «Новые числа»: реши такую же ещё раз.

0 верно из 6

Часть 2. Как устроена рекурсия

База и шаг

Сумма цифр 3815 — это сумма цифр 381 плюс 5. Задача сведена к такой же, но меньшей, — и так до однозначного числа, у которого ответ известен. Без базы вызовы не кончатся; шаг, который к базе не ведёт, — то же самое.

Стек вызовов

Спуск	Что ждёт в стеке	Подъём
`digsum(3815)`	ждёт `digsum(381)`, потом + 5	12 + 5 = 17
`digsum(381)`	ждёт `digsum(38)`, потом + 1	11 + 1 = 12
`digsum(38)`	ждёт `digsum(3)`, потом + 8	3 + 8 = 11
`digsum(3)`	база — ответ сразу	3

Каждый незаконченный вызов лежит в стеке со своим n и помнит, что ему осталось сделать. Ответ отдаётся тому, кто лежит под ним. Глубина стека — сколько вызовов ждут одновременно; у Python предел около тысячи, дальше — RecursionError.

Печать до и после вызова

print до вызова срабатывает на спуске, после — на подъёме, в обратном порядке. Остатки от деления на 2 появляются с конца, а стек сам разворачивает их в правильный порядок.

Два вызова в теле — дерево

Один вызов в теле даёт цепочку, два — дерево вызовов, как у фрактала: каждая ветка повторяет целое в уменьшенном виде. tree(3) — это 1 + 2 + 4 + 8 = 15 вызовов. Так рисуют дерево Пифагора, снежинку Коха, треугольник Серпинского.

Функция по формуле — задание 16 ЕГЭ

Формула переписывается в функцию дословно: случаи — это if, база — первый случай. Две функции могут звать друг друга — порядок def не важен, лишь бы оба стояли выше вызова. Считать на бумаге удобнее снизу вверх таблицей: F(1), F(2), F(3)…

Три ошибки рекурсии

Нет базы. Вызовы без конца — RecursionError.
Шаг мимо базы. f(n - 2) с базой n == 0 из нечётного числа проскакивает ноль: база должна ловить все концы — n <= 0.
Забыт return. Сумма посчитана и выброшена, наверх уходит None — следующий вызов падает на None + n.

Часть 3. Три программы

Сохраняй решения в свою папку под именами zadanie1.py … zadanie3.py. Заведи для этой пары новую папку — в прошлой были свои zadanie1.py.
Обе функции обязательны, с теми именами, что в задании, и рекурсивные. Функция зовёт сама себя (в задании 3 — себя или напарницу) и обходится без циклов for и while. Цикл вместо рекурсии или готовое (bin, sum по строке) задание не сдаёт, даже если вывод верный.
Оболочка вырезает из файла твои def и зовёт каждую функцию напрямую на своих числах. Функция печатает вместо return — задание не принято.
Никаких приглашений в input(). Пиши input(), а не input("Введите число: ") — вывод читает машина.
Выводи ровно то, что просят: те же слова, тот же порядок строк.
Шапка (# Ввод:, # Вывод:, # Пример:) — по желанию. Если она есть, пример в ней оболочка проверит запуском.

Задание 1 Цифровой корень

Сложим цифры числа, потом цифры суммы — и так, пока не останется одна цифра: 99 → 18 → 9. Эта цифра — цифровой корень. Напиши две рекурсивные функции: возвращает сумму цифр , а — цифровой корень, через . Программа читает натуральное число (до 10¹²) и печатает сумму его цифр и цифровой корень.

Функции: и — обе возвращают число, обе рекурсивные, без циклов.

Вход

Вывод

Сумма цифр: 18
Цифровой корень: 9

Проверяется: рекурсия в обеих функциях; digsum и digroot напрямую — однозначные, 10, 99, двенадцать девяток, триллион.

Если застрял

: база — однозначное число, оно само себе сумма цифр; шаг — . : однозначное число — само себе корень, иначе .

Ловушка, ради которой это задание. Один вызов — ещё не корень: у 99 сумма цифр 18, двузначная. Рекурсия в и повторяет сложение столько раз, сколько нужно.

Задание 2 Двоичная запись

Последняя двоичная цифра числа — , остальные — двоичная запись . Напиши две рекурсивные функции: возвращает двоичную запись , записанную как обычное число (11 → 1011), а — сколько единиц в этой записи. Программа читает целое (0 ≤ n ≤ 1000000) и печатает его двоичную запись и число единиц. Функцию не использовать.

Функции: и — обе возвращают число, обе рекурсивные, без циклов.

Вход

Вывод

Двоичная запись: 1011
Единиц: 3

Проверяется: рекурсия в обеих функциях; to_bin и ones напрямую — 0, 1, 2, 8, 255, 1024, миллион.

Если застрял

: база — (0 и 1 записываются сами собой); шаг — : запись остальных цифр сдвигается на разряд влево, и справа приписывается последняя. : база , шаг .

Ловушки, ради которых это задание. База не ловит ноль: зовёт без конца. Приписать цифру не с той стороны — и запись выйдет задом наперёд.

Задание 3 Две функции по формуле

Так звучит задание 16 ЕГЭ. Функции заданы формулами:

F(1) = 1, G(1) = 1;
F(n) = F(n − 1) + 2·G(n − 1) при n > 1;
G(n) = F(n − 1) + G(n − 1) при n > 1.

Напиши функции и — дословно по формулам. Программа читает натуральное (1 ≤ n ≤ 15) и печатает F(n) и G(n).

Функции: и — обе возвращают число, зовут себя и друг друга, без циклов.

Вход

Вывод

F: 17
G: 12

Проверяется: рекурсия в обеих функциях; F и G напрямую — n = 1, 2, 3, 5, 8, 12.

Если застрял

Каждый случай формулы — ветка: , иначе . Так же G. Проверь на бумаге: F(2) = 1 + 2 = 3, G(2) = 1 + 1 = 2.

Ловушки, ради которых это задание. База нужна обеим функциям. Внутри G — значения от : вызов оттуда уходит в вечный спуск. На n = 15 вызовов десятки тысяч — дерево ветвится; это ещё быстро, но для n = 40 такую рекурсию уже считают снизу вверх.

Часть 4. Сдача

Файлы zadanie1.py … zadanie3.py лежат в твоей папке, отладочные print из них убраны.
В общей папке двойной щелчок по Проверка.bat.
«Найти мои файлы» → «Проверить всё».
Покажи учителю два экрана: тренажёр наверху этой страницы и итог оболочки.

Если вместо окна открылся текст программы — файл открылся в IDLE как код. Нажми F5, окно появится.

Оболочка показывает, на каких данных программа ошиблась и что должна была вывести, есть ли в функциях рекурсия и нет ли циклов, а если не так ведёт себя функция — какой вызов что вернул и что должен был. Исправляй и проверяй снова, попыток сколько угодно. Отметка: три задания — «5», два — «4», одно — «3».

Подсказка: рекурсия

База и шаг

Рекурсивная функция зовёт сама себя. База — случай, где ответ даётся сразу, без вызова себя. Шаг — та же задача, но меньше: digsum(n // 10) + n % 10. Шаг обязан вести к базе.

Стек вызовов

Незаконченные вызовы ждут в стеке, у каждого своё n. Ответ отдаётся тому, кто лежит ниже. Глубина — сколько вызовов ждут одновременно; предел Python — около тысячи, дальше RecursionError.

Спуск и подъём

print до вызова — на спуске, сверху вниз; print после вызова — на подъёме, в обратном порядке. Остатки n % 2, напечатанные после вызова p(n // 2), дают двоичную запись по порядку.

Дерево вызовов

Два вызова в теле — дерево, как у фрактала: 1 + 2 + 4 + … вызовов. Считаются все вызовы, и те, что сразу упираются в базу.

Формула — задание 16 ЕГЭ

Случаи формулы — ветки if, база — первый случай. Две функции могут звать друг друга. На бумаге считать снизу вверх таблицей: F(1), F(2), F(3)…

Три ошибки

Нет базы — RecursionError. Шаг мимо базы (через два из нечётного) — то же. Забыт return — наверх уходит None и TypeError на None + n.

Материалы подготовлены с использованием технологий искусственного интеллекта.