Задание 16 ЕГЭ по информатике. Рекурсивные функции

Что такое рекурсия

Функция может вызывать другую функцию. Но функция также может вызывать и саму себя — это и есть рекурсия. Простейшая иллюстрация:

def short_story():
    print("У попа была собака, он ее любил.")
    print("Она съела кусок мяса, он ее убил,")
    print("В землю закопал и надпись написал:")
    short_story()  # бесконечный рекурсивный вызов

Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция — рекурсивной.

Классический пример: факториал

Хорошо известно, что 0! = 1, 1! = 1. Для n > 1 используем соотношение n! = n · (n − 1)! — пока не дойдём до базы 0!.

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

print(factorial(5))

Проблемы рекурсии

• Бесконечная рекурсия: цепочка вызовов «уходит вниз», пока не закончится стек. Частые причины:
  • Нет корректного условия выхода (базового случая).
  • Рекурсивный вызов сделан с неправильными параметрами (например, не уменьшаем аргумент).
• Ограничение глубины: RecursionError: maximum recursion depth exceeded in comparison — по умолчанию предел около 1000 вызовов. Решение из презентации: увеличить лимит стека.

import sys
sys.setrecursionlimit(10_000)

Ускорение вычислений: кэширование (мемоизация)

Рекурсивные функции часто пересчитывают одни и те же значения. Кэширование (мемоизация) устраняет повторные вычисления.

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(50))  # очень быстро благодаря кэшированию

Использование кэша и предварительных вычислений

Пример с «глубокой» рекурсией и большим числом однотипных вызовов:

import sys
sys.setrecursionlimit(50_000)

def f(n):
    if n < 20:
        return n
    else:
        return (n - 6) * f(n - 7)
for i in range (1, 47):
    f(i)
print((f(47872) - 290 * f(47865)) / f(47858))

Чтобы избежать повторных вычислений, предложено предварительно заполнить кэш (через цикл) и использовать @lru_cache:

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n < 20:
        return n
    else:
        return (n - 6) * f(n - 7)

for i in range(20, 47973):
    f(i)  # прогрев кэша

print((f(47872) - 290 * f(47865)) / f(47858))

Примечание: в презентационных примерах деление / используется буквально; для целочисленной рекурсии в Python 3 при необходимости применяйте //

Примеры решений заданий

Задание 1

Условие: Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число:

• F(0) = 0;
• F(n) = F(n / 2), если n > 0 и при этом чётно;
• F(n) = 1 + F(n − 1), если n нечётно.

Сколько существует таких чисел n, что 1 ≤ n ≤ 1000 и F(n) = 3? :contentReference[oaicite:7]{index=7}

def f(n):
    if n == 0:
        return 0
    elif n % 2 == 0:
        return f(n / 2)   # в презентации — деление /; при желании замените на //
    else:
        return 1 + f(n - 1)

cnt = 0
for n in range(1, 1001):
    if f(n) == 3:
        cnt += 1
print(cnt)

Задание 2

Условие (из презентации): Алгоритм вычисления F(n), где n — натуральное:

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

Чему равно F(5)? В ответе запишите только натуральное число. :contentReference[oaicite:8]{index=8}

def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    else:
        return f(n - 1) * n + f(n - 2) * (n - 1)

print(f(5))

Задание 3

Условие (из презентации): Обозначим mod(a, b) — остаток от деления натурального a на натуральное b. Алгоритм F(n), где n — целое неотрицательное:

• F(0) = 0;
• F(n) = F(n / 3), если n > 0 и mod(n, 3) = 0;
• F(n) = mod(n, 3) + F(n − mod(n, 3)), если mod(n, 3) > 0.

Назовите минимальное значение n, для которого F(n) = 9. :contentReference[oaicite:9]{index=9}

def f(n):
    if n == 0:
        return 0
    elif n % 3 == 0:
        return f(n / 3)          # как в презентации; при необходимости используйте //
    else:
        return n % 3 + f(n - n % 3)

for n in range(0, 1000):
    if f(n) == 9:
        print(n)
        break

Задание 4

Условие (из презентации):

• F(0) = 0;
• F(n) = F(n − 1) + 1, если n нечётно;
• F(n) = F(n / 2), если n > 0 и n чётно.

Укажите количество таких значений n < 1 000 000 000, для которых F(n) = 3. В презентации дано пояснение: эта рекурсивная функция фактически считает число единиц в двоичной записи n, то есть ищем числа, у которых ровно три «1». Число 1 000 000 000 имеет 30 двоичных разрядов ⇒ разместить 3 единицы в 30 позициях: C(30,3). :contentReference[oaicite:10]{index=10}

import math
def C(n, k): return math.comb(n, k)
print(C(30, 3))

Практические ремарки

• В заданиях, где деление указано как «/», это цитата из презентации. В рабочих решениях на Python целочисленную рекурсию корректнее писать с //, чтобы не превращать аргументы в float и не усложнять кэширование. :contentReference[oaicite:11]{index=11}
• При больших глубинах вызовов используйте sys.setrecursionlimit и/или @lru_cache (как показано выше). :contentReference[oaicite:12]{index=12}