Рекурсия в Python: от факториала до задач ЕГЭ — тренажёр

Пример 1. Функция задана правилом: f(1) = 1; для n > 1 верно f(n) = f(n - 1) * 2. Что вернёт f(10)? Запиши число.

Подсказка. f(1) = 1, f(2) = 2, f(3) = 4 — ловишь закономерность?

Как решать. Каждый шаг удваивает значение: f(10) — это 2 в степени 10 - 1. Иди от базы f(1) = 1 и удваивай.

Ответ: 512

Пример 2. Функция k(n) при n > 0 дважды вызывает k(n - 1); при n = 0 она возвращает 1, не вызывая себя. Сколько всего вызовов k произойдёт при вычислении k(1)? Включай и сам вызов k(1).

Подсказка. Считай снизу: k(0) — один вызов, k(1) — три, k(2) — семь.

Как решать. Пусть C(n) — число вызовов: C(0) = 1, дальше C(n) = 2 * C(n - 1) + 1. Отсюда C(1) = 2 в степени 1 + 1, минус 1.

Ответ: 3

Пример 3. Сумма цифр через рекурсию: s(n) возвращает n при n < 10, иначе n % 10 + s(n // 10). Что вернёт вызов s(64)?

Подсказка. Первый же шаг рекурсии отрезает последнюю цифру числа.

Как решать. Число 64 не однозначное: шаг отрезает последнюю цифру 4, а остаток — 6, и 6 уже меньше десяти, это база. Итог: 6 + 4.

Ответ: 10

Пример 4. Функция задана правилом: f(1) = 3; для n > 1 верно f(n) = f(n - 1) + 2 * n - 1. Что вернёт f(9)? Запиши число.

Подсказка. Сумма первых нечётных чисел — известный квадрат.

Как решать. Шаг прибавляет нечётные числа 3, 5, 7...: нечётные суммы складываются в квадраты. f(1) = 3 = 1 + 2, значит f(9) = 9 * 9 + 2. Проверь: f(2) = 3 + 3 = 6 = 4 + 2.

Ответ: 83

Пример 5. Функция задана правилом: f(1) = 1; для n > 1 верно f(n) = f(n - 1) * 2. Что вернёт f(3)? Запиши число.

Подсказка. f(1) = 1, f(2) = 2, f(3) = 4 — ловишь закономерность?

Как решать. Каждый шаг удваивает значение: f(3) — это 2 в степени 3 - 1. Иди от базы f(1) = 1 и удваивай.

Ответ: 4

Пример 6. Функция k(n) при n > 0 дважды вызывает k(n - 1); при n = 0 она возвращает 1, не вызывая себя. Сколько всего вызовов k произойдёт при вычислении k(7)? Включай и сам вызов k(7).

Подсказка. Считай снизу: k(0) — один вызов, k(1) — три, k(2) — семь.

Как решать. Пусть C(n) — число вызовов: C(0) = 1, дальше C(n) = 2 * C(n - 1) + 1. Отсюда C(7) = 2 в степени 7 + 1, минус 1.

Ответ: 255

Пример 7. Сумма цифр через рекурсию: s(n) возвращает n при n < 10, иначе n % 10 + s(n // 10). Что вернёт вызов s(21)?

Подсказка. Первый же шаг рекурсии отрезает последнюю цифру числа.

Как решать. Число 21 не однозначное: шаг отрезает последнюю цифру 1, а остаток — 2, и 2 уже меньше десяти, это база. Итог: 2 + 1.

Ответ: 3

Пример 8. Функция задана правилом: f(1) = 3; для n > 1 верно f(n) = f(n - 1) + 2 * n - 1. Что вернёт f(6)? Запиши число.

Подсказка. Сумма первых нечётных чисел — известный квадрат.

Как решать. Шаг прибавляет нечётные числа 3, 5, 7...: нечётные суммы складываются в квадраты. f(1) = 3 = 1 + 2, значит f(6) = 6 * 6 + 2. Проверь: f(2) = 3 + 3 = 6 = 4 + 2.

Ответ: 38

Пример 9. Функция задана правилом: f(1) = 1; для n > 1 верно f(n) = f(n - 1) * 2. Что вернёт f(7)? Запиши число.

Подсказка. f(1) = 1, f(2) = 2, f(3) = 4 — ловишь закономерность?

Как решать. Каждый шаг удваивает значение: f(7) — это 2 в степени 7 - 1. Иди от базы f(1) = 1 и удваивай.

Ответ: 64

Пример 10. Функция k(n) при n > 0 дважды вызывает k(n - 1); при n = 0 она возвращает 1, не вызывая себя. Сколько всего вызовов k произойдёт при вычислении k(4)? Включай и сам вызов k(4).

Подсказка. Считай снизу: k(0) — один вызов, k(1) — три, k(2) — семь.

Как решать. Пусть C(n) — число вызовов: C(0) = 1, дальше C(n) = 2 * C(n - 1) + 1. Отсюда C(4) = 2 в степени 4 + 1, минус 1.

Ответ: 31

Пример 11. Функция задана правилом: f(1) = 1; для n > 1 верно f(n) = f(n - 1) * 2. Что вернёт f(12)? Запиши число.

Подсказка. f(1) = 1, f(2) = 2, f(3) = 4 — ловишь закономерность?

Как решать. Каждый шаг удваивает значение: f(12) — это 2 в степени 12 - 1. Иди от базы f(1) = 1 и удваивай.

Ответ: 2048

Пример 12. Сумма цифр через рекурсию: s(n) возвращает n при n < 10, иначе n % 10 + s(n // 10). Что вернёт вызов s(79)?

Подсказка. Первый же шаг рекурсии отрезает последнюю цифру числа.

Как решать. Число 79 не однозначное: шаг отрезает последнюю цифру 9, а остаток — 7, и 7 уже меньше десяти, это база. Итог: 7 + 9.

Ответ: 16

Пример 13. Функция задана правилом: f(1) = 3; для n > 1 верно f(n) = f(n - 1) + 2 * n - 1. Что вернёт f(2)? Запиши число.

Подсказка. Сумма первых нечётных чисел — известный квадрат.

Как решать. Шаг прибавляет нечётные числа 3, 5, 7...: нечётные суммы складываются в квадраты. f(1) = 3 = 1 + 2, значит f(2) = 2 * 2 + 2. Проверь: f(2) = 3 + 3 = 6 = 4 + 2.

Ответ: 6

Пример 14. Функция k(n) при n > 0 дважды вызывает k(n - 1); при n = 0 она возвращает 1, не вызывая себя. Сколько всего вызовов k произойдёт при вычислении k(8)? Включай и сам вызов k(8).

Подсказка. Считай снизу: k(0) — один вызов, k(1) — три, k(2) — семь.

Как решать. Пусть C(n) — число вызовов: C(0) = 1, дальше C(n) = 2 * C(n - 1) + 1. Отсюда C(8) = 2 в степени 8 + 1, минус 1.

Ответ: 511

Пример 15. Сумма цифр через рекурсию: s(n) возвращает n при n < 10, иначе n % 10 + s(n // 10). Что вернёт вызов s(28)?

Подсказка. Первый же шаг рекурсии отрезает последнюю цифру числа.

Как решать. Число 28 не однозначное: шаг отрезает последнюю цифру 8, а остаток — 2, и 2 уже меньше десяти, это база. Итог: 2 + 8.

Ответ: 10

Вопрос 1. Функция задана правилом: F(1) = 1; F(2) = 2; при n > 2 верно F(n) = 2 * F(n - 1) + F(n - 2). Что выведет print(F(5))?

Ответ: 29

Пояснение. Иди от базы вверх: F(3) = 2 2 + 1 = 5, F(4) = 2 5 + 2 = 12, F(5) = 2 * 12 + 5 = 29.

Вопрос 2. Какие утверждения о мемоизации верны?

Ответ: functools.lru_cache хранит результаты прошлых вызовов и отдаёт их при повторном запросе; с lru_cache каждый конкретный fib(k) реально вычисляется не более одного раза; без мемоизации число вызовов fib(n) растёт примерно как сами числа Фибоначчи

Пояснение. lru_cache лишь кэширует готовые значения и не трогает формулу, а без кэша дерево вызовов ветвится: вызовов выходит порядка самих чисел Фибоначчи.

Вопрос 3. Функция fib задана наивно: fib(1) = 1; fib(2) = 1; fib(n) = fib(n - 1) + fib(n - 2). Сколько всего вызовов fib произойдёт при вычислении fib(6)? Считай и сам вызов fib(6). Запиши число.

Ответ: 15

Пояснение. Число вызовов живёт по своей рекурсии: C(1) = C(2) = 1, дальше C(n) = C(n - 1) + C(n - 2) + 1: C(3) = 3, C(4) = 5, C(5) = 9, C(6) = 15.

Вопрос 4. Расставь события трассировки f(3), где f(n) = 1 при n <= 1 и n * f(n - 1) иначе, в порядке их наступления.

Ответ: вызов f(3): база не сработала, нужен f(2) → вызов f(2): снова рекурсивный шаг, нужен f(1) → f(1) срабатывает как база и возвращает 1 → f(2) получает 1 и возвращает 2 1 = 2 → f(3) получает 2 и возвращает 3 2 = 6

Пояснение. Сначала вызовы погружаются: f(3), затем f(2). На f(1) срабатывает база, и значения возвращаются обратно: f(2) даёт 2, f(3) даёт 6.

Вопрос 5. Сопоставь термин и его смысл.

Пояснение. Четыре опоры любой рекурсии: дно, шаг, учёт кадров стека и кэш против повторов.

Вопрос 6. Разложи задачи по корзинам: где цикл справится честнее, а где рекурсия естественнее.

Пояснение. Ровные данные одной размерности складываются в цикле, а вложенные структуры и самоподобные головоломки вроде Ханойских башен просятся в рекурсию.

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

Ответ: базовый → меньшего → RecursionError

Пояснение. База останавливает вызовы, шаг уменьшает задачу, а превышение лимита глубины стека даёт RecursionError.