Алгоритмы и программирование · 1 балл

Рекурсия

Вызовы функций

Вычислить значение рекурсивной функции или количество вызовов.

Алгоритмы целое число

Что проверяет

Рекурсия, рекурсивные процедуры и функции.

Основание: проект спецификации и кодификатора КИМ 2027. Открыть документы

Теория

Что нужно знать

Задание 16 проверяет рекурсию: значение функции F(n), количество вызовов, сумму или количество выведенных символов, иногда — неизвестный параметр. В базе Kompege по теме 1 011 задач, 70 решений (61 программное и 9 текстовых) и 260 видеоразборов (161 YouTube, 66 VK, 33 Rutube). В 2027 году тема сохраняется без изменения номера.

Минимум для задания 16

базовый случай и рекурсивный шаг
дерево вызовов и порядок обхода
линейная рекурсия F(n−1) и F(n−2)
рекурсия вперёд: F(n+1), F(n+2), F(2n)
ветвление по чётности, делимости и значению предыдущего вызова
две и более взаимно рекурсивные функции
таблица значений и динамика снизу вверх
мемоизация: @lru_cache, @cache, словарь
ограничение размера кэша и вытеснение значений
подсчёт количества вызовов и узлов дерева
вывод на экран: звёздочки, числа и порядок print
суммы значений, арифметическая прогрессия и большие n
целочисленное деление //, остаток % и отрицательные n
обратная задача: найти x или границу
проверка ответа и ограничение глубины рекурсии

Рекурсивная функция и её части

Рекурсивная функция вызывает саму себя с другим аргументом. В задании 16 всегда есть базовый случай, который не делает нового вызова, и рекурсивный шаг. Без базы вычисление не завершится, а неверная база даст неверный ответ.

Базовый случай возвращает значение сразу: обычно при n ≤ b или n ≥ N.
Рекурсивный шаг приближает аргумент к базе: n−1, n−2, n//2 или n+1 при базе сверху.
Условия в записи читаются сверху вниз; срабатывает первая подходящая ветвь.
Ветвь может зависеть от n, от n % 2, от n % 3 или от значения F(n−1).
Аргументов может быть несколько: F(a, b), F(n, s), F(n, flag).

F(n) = база, если условиеF(n) = выражение с F(...), иначе

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

Каждый вызов — узел дерева. Листья — базовые случаи. Значение считается снизу вверх: сначала листья, затем родители. Дерево помогает не потерять ветвь и посчитать количество вызовов.

Корень — исходный вызов F(n).
Дети — вызовы, которые делает текущий вызов.
Лист — вызов, попавший в базовый случай.
Количество вызовов — число узлов дерева, включая корень и листья.
Глубина дерева — максимальная длина цепочки вызовов.
Для больших n дерево не рисуют полностью, а сворачивают в таблицу или формулу.

вызовов = 1 + Σ вызовов в детяхзначение = шаг(значения детей)

Линейная рекурсия

Если в правой части один вызов, вычисление идёт цепочкой. Если два вызова, появляется ветвление. Цепочку раскрывают подстановкой, пока не дойдут до базы, а затем считают снизу вверх.

F(n) = n + F(n−1) даёт сумму n + (n−1) + … + F(b).
F(n) = n·F(n−2) даёт произведение чисел той же чётности.
При базе n ≤ b подстановку останавливают на первом n из базы.
Шаг n−2 сохраняет чётность: чётные и нечётные цепочки не пересекаются.
Для произведения следите за нулём: F(0) = 0 обнулит всю цепочку.

F(n) = n + (n−1) + … + (b+1) + F(b)F(n) = n·(n−2)·…·(b+2)·F(b)

Рекурсия вперёд

Если база задана при n ≥ N, а шаг увеличивает аргумент, вычисляют в обратном порядке: от границы базы вниз к нужному n. Таблицу заполняют с конца.

Определите границу базы: n ≥ N, n > N или n = N.
Начинайте с наибольшего n и двигайтесь вниз.
При шаге 2n значения нужны только для степеней двойки.
Если аргумент уходит за границу, срабатывает база.
Для F(5) при шаге 2n цепочка: 5 → 10 → 20 → … до базы.

F(N) = база; F(N−1), F(N−2), … — обратный ходF(2n) требует значения только в точках 2^k·n

Ветвление по условиям

В задании 16 ветвь часто выбирается по чётности n, остатку от деления или значению предыдущего вызова. Сначала вычислите условие, затем выбирайте формулу. Порядок условий важен: ветви могут пересекаться.

n % 2 == 0 — чётное; n % 2 == 1 — нечётное.
n % 3 == 0 — делится на 3; проверяйте остатки 0, 1 и 2.
Условие может смотреть на F(n−1): «если F(n−1) чётно».
Для отрицательных n в Python остаток неотрицательный: −3 % 10 = 7.
Если условие не выполнено ни для одной ветви, функция не определена — проверьте базу.

ветвь 1, если условие 1ветвь 2, если условие 2ветвь 3, иначе

Таблица и динамика

Вместо рекурсии значения хранят в массиве или словаре и заполняют по порядку. Это снимает повторные вычисления и риск переполнения стека. Для рекурсии вперёд порядок заполнения обратный.

Заведите массив на диапазон от базы до нужного n.
Сначала заполните базовые значения.
Затем применяйте формулу для n по возрастанию или по убыванию.
Для F(n−2) нужны два предыдущих значения, для F(n−5) — пять.
Для двух функций храните два массива или пары значений.
Проверка: f[n] должно совпадать с рекурсивным вызовом на малых n.

f[n] = выражение(f[n−1], f[n−2], …)f[n] = f[n−1] + f[n−2] — числа Фибоначчи

Мемоизация

Мемоизация кэширует результат для каждого аргумента. Один и тот же F(k) не вычисляется повторно, поэтому дерево превращается в граф зависимостей и работает за число различных аргументов.

from functools import lru_cache; @lru_cache(None) ставится перед def.
В Python 3.9+ доступен @cache как короткий вариант.
Кэш работает только для хешируемых аргументов: int, tuple, str.
Для больших n прогрейте кэш циклом или увеличьте глубину рекурсии.
Мемоизация не меняет значение функции, только скорость.
Не используйте кэш, если функция зависит от внешней изменяемой переменной.
@lru_cache(maxsize=N) ограничивает кэш N значениями; при переполнении старые вытесняются.
Если в задаче задан размер кэша, эмулируйте его вручную: dict и очередь вытеснения, иначе количество повторных вычислений будет неверным.
Для точного количества вызовов при ограниченном кэше декоратор может дать неверный ответ: часть вызовов пересчитается.

@lru_cache(None)@lru_cache(maxsize=100)from functools import cache

Количество вызовов

Количество вызовов — это не значение функции, а размер дерева. Для одного вызова это 1 плюс число вызовов детей. Если считают только рекурсивные вызовы, корень может не учитываться — уточняйте формулировку.

Если считают все обращения к функции, каждый узел даёт 1.
Для F(n) = F(n−1) + F(n−2) число вызовов растёт как числа Фибоначчи.
Мемоизация уменьшает число вычислений, но не число обращений в наивной программе.
Для процедуры с print считайте каждый вход в процедуру.
Формулу удобно проверить на малых n вручную.
Ответ может быть очень большим; в Python он не переполняется.

C(n) = 1, если базаC(n) = 1 + C(n−1) + C(n−2)

Что выводит процедура

В задачах со звёздочками и числами важен порядок команд: print до рекурсивного вызова выполняется при каждом входе, print после — при возврате. Суммируйте вклад текущего вызова и детей.

Один print внутри процедуры — одна единица вклада на каждый вызов.
print после рекурсивного вызова тоже выполняется, но позже.
Если print стоит под if, он добавляется только при истинном условии.
Для звёздочек: S(n) = вклад текущего вызова + S(детей).
Для чисел складывайте напечатанные значения, а не аргументы.
Порядок вывода влияет на последовательность, но не на сумму и количество.

S(n) = print_сейчас + S(n−1) + S(n−2)количество = сумма вкладов всех вызовов

Суммы и большие n

Если нужна сумма F(k) на отрезке или значение при большом n, рекурсию сворачивают в формулу. Часто помогают арифметическая прогрессия, суммы квадратов и периодичность.

Сумма арифметической прогрессии: (a₁ + aₖ)·k / 2.
Сумма первых m нечётных чисел равна m².
Сумму значений F на отрезке считают циклом по таблице.
Для больших n ищите шаг и повторяющийся блок.
В Python большие целые точны; избегайте float для точных ответов.
Если ответ просят по модулю, берите остаток на каждом шаге.

S = (a₁ + aₖ)·k / 21 + 3 + … + (2m−1) = m²

Несколько функций

Взаимная рекурсия: F вызывает G, G вызывает F. Значения вычисляют парами, а таблицу заполняют одновременно для обеих функций.

База задаётся для каждой функции отдельно.
Храните пару (F(n), G(n)) или два массива.
При шаге назад начинайте с базы и идите вверх.
При шаге вперёд идите от границы вниз.
В Python кортежное присваивание F, G = …, … вычисляет правую часть до записи.

(F(n), G(n)) = Φ(F(n−1), G(n−1))F(n) = G(n−1), G(n) = G(n−2) + 1

Количество n по условию

Иногда нужно не одно значение, а число аргументов, для которых F(n) обладает свойством: является квадратом, содержит заданную цифру или кратно числу. Тогда F(n) считают для каждого n из диапазона и проверяют свойство.

Определите границы диапазона: включительно или нет.
Заполните таблицу F(n) до верхней границы.
Свойство проверяйте после вычисления значения.
Полный квадрат: x ≥ 0 и int(x**0.5)**2 == x.
Наличие цифры: str(x).count('7') > 0.
Кратность: x % m == 0.
Разные n могут давать одно и то же F(n); считают именно n.

количество = |{n ∈ [a; b] : P(F(n))}|

Обратная задача и проверка

Иногда требуется найти параметр x или границу, при которых выполняется условие. Сначала упростите выражение, затем переберите x в разумных пределах и проверьте ответ.

Выразите разность F(a) − F(b) через несколько шагов рекурсии.
Для линейного x получается уравнение A + B·x = C.
Диапазон перебора берите из условия; при отсутствии — от −10⁵ до 10⁵.
Проверьте, что x целый и входит в допустимую область.
Убедитесь, что рекурсия завершается и не уходит в бесконечность.
Сверьте ответ с ключом на малых аналогах задачи.

F(a) − F(b) = A + B·xx = (C − A) / B

Разбор примера

Учебный пример: F(10) и F(9) при шаге n−2

Функция задана так: F(n) = 2 при n ≤ 2, F(n) = n·F(n−2) при n > 2. Нужно найти F(10) − F(9).

Значения функции для n = 1…10
n	1	2	3	4	5	6	7	8	9	10
F(n)	2	2	6	8	30	48	210	384	1 890	3 840

База: F(1) = F(2) = 2.
Чётная цепочка: F(4) = 4·F(2) = 8, F(6) = 6·F(4) = 48, F(8) = 8·F(6) = 384, F(10) = 10·F(8) = 3 840.
Нечётная цепочка: F(3) = 3·F(1) = 6, F(5) = 5·F(3) = 30, F(7) = 7·F(5) = 210, F(9) = 9·F(7) = 1 890.
Цепочки не пересекаются: шаг n−2 сохраняет чётность аргумента.
Считаем разность: 3 840 − 1 890 = 1 950.

Ответ1 950.

Способы решения

Выберите метод под формулировку

Методы собраны по решениям задания 16 из базы Kompege. Начните с того, что именно нужно найти в условии.

когда n небольшое

Прямая подстановка

Когда использовать: n измеряется десятками, а формула содержит один или два вызова — быстрее раскрыть вручную, чем писать программу.

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

Пример

F(n) = 4 при n ≤ 16; F(n) = n·F(n−2) при n > 16. Найдём F(24).

def f(n):
    return 4 if n <= 16 else n * f(n - 2)

print(f(24))  # 760320

Ответ760 320: 24·22·20·18·4.

Задача № 10929 (база Kompege).

когда n большое

Таблица значений снизу вверх

Когда использовать: n — сотни или тысячи, рекурсия линейная или содержит немного ветвей. Таблица убирает повторные вызовы и переполнение стека.

Определите базу и правую границу.
Создайте массив или словарь.
Заполните базовые значения.
Идите по n в нужном направлении и применяйте формулу.
Возьмите готовое значение или разность значений.

Пример

F(n) = n при n ≤ 6; F(n) = 2n + 3 + F(n−1) при n > 6. Найдём F(6188) − F(6185).

f = {n: n for n in range(1, 7)}
for n in range(7, 6189):
    f[n] = 2 * n + 3 + f[n - 1]

print(f[6188] - f[6185])  # 37131
print(6 * 6188 + 3)       # 37131

Ответ37 131: разность трёх соседних шагов даёт 6n + 3.

Задача № 11235 (база Kompege).

когда подзадачи повторяются

Мемоизация через lru_cache

Когда использовать: Ветвление снова и снова вызывает одни и те же аргументы, а вручную строить таблицу неудобно.

Импортируйте lru_cache из functools.
Поставьте декоратор перед функцией.
Опишите базу и шаг в естественном виде.
При необходимости прогрейте кэш циклом.
Сравните результат с таблицей на малых n.

@lru_cache(None) хранит все вычисленные значения; @cache делает то же самое.
@lru_cache(maxsize=N) хранит только N последних значений: при переполнении старые вытесняются.
Если условие ограничивает размер кэша, декоратор с maxsize может пересчитывать часть значений — эмулируйте кэш вручную, если считаете вызовы.
Для точного количества обращений при ограниченном кэше используйте dict и очередь вытеснения, а не готовый декоратор.

Пример

F(n) = n при n ≤ 3; F(n) = n(n−1) + F(n−1) + F(n−2) при n > 3. Найдём F(3333) − F(3332) − F(3331).

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n <= 3:
        return n
    return n * (n - 1) + f(n - 1) + f(n - 2)

for i in range(1, 3334):
    f(i)

print(f(3333) - f(3332) - f(3331))  # 11105556

Ответ11 105 556; разность равна 3333·3332.

Задача № 13952 (база Kompege).

когда база при n ≥ N

Рекурсия вперёд

Когда использовать: Шаг увеличивает аргумент: n+1, n+2 или 2n, а база задана при больших n.

Найдите границу базы.
Заполняйте значения от границы вниз.
Для n+2 сохраняйте чётность аргумента.
Не вызывайте функцию «в лоб»: глубина может превысить 1000.
Проверьте значения рядом с границей.

Пример

F(n) = n при n > 18; F(n) = 3·F(n+1) + n + 8 при n ≤ 18. Найдём F(9).

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n > 18:
        return n
    return 3 * f(n + 1) + n + 8

print(f(9))  # 1874798

Ответ1 874 798.

Задача № 273 (база Kompege).

когда есть n % 2 или n % 3

Ветвление по чётности и делимости

Когда использовать: Формула зависит от остатка или от чётности предыдущего значения.

Выпишите условия и порядок ветвей.
Определите базу для каждого остатка.
Помните: шаг n−2 сохраняет чётность, шаг n−1 меняет.
Считайте по таблице или с кэшем.
Проверьте обе ветви на малых n.

Пример

F(n) = 1 при n ≤ 1; F(n) = n·F(n−1) при чётных n > 1; F(n) = n + F(n−2) при нечётных n > 1. Найдём F(84).

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n <= 1:
        return 1
    if n % 2 == 0:
        return n * f(n - 1)
    return n + f(n - 2)

print(f(84))  # 148176

Ответ148 176.

Задача № 598 (база Kompege).

когда заданы F(n) и G(n)

Две взаимно рекурсивные функции

Когда использовать: F ссылается на G, а G — на F. Значения нужно считать одновременно, парой.

Выпишите базу для F и для G.
Храните пару значений или два массива.
Идите от n = 1 вверх, если шаг назад.
Используйте значения предыдущего шага.
Проверьте обе функции на малых n.

Пример

F(1) = G(1) = 1; F(n) = F(n−1) − 2·G(n−1); G(n) = F(n−1) + 2·G(n−1). Найдём G(21).

n = 21
F, G = 1, 1          # n = 1
for i in range(2, n + 1):
    F, G = F - 2 * G, F + 2 * G

print(G)  # 802165

Ответ802 165.

Задача № 591 (база Kompege).

когда спрашивают «сколько раз»

Количество вызовов

Когда использовать: Нужно не значение функции, а число её вызовов или выполнений.

Определите, считается ли корневой вызов.
Для базы возьмите 1 — сам вызов.
Для шага сложите 1 и количество вызовов детей.
Решите рекуррентность по таблице.
Проверьте на n = 3, 4, 5 вручную.

Пример

F(n) = 2 при n ≤ 2; F(n) = F(n−1) − 2·F(n−2) при n > 2. Сколько вызовов при F(57)?

from functools import lru_cache

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

print(calls(57))  # 730870592323

Ответ730 870 592 323 вызова.

Задача № 4328 (база Kompege).

когда печатаются звёздочки

Сколько символов выведет процедура

Когда использовать: Процедура печатает символы, а нужно узнать их количество.

Посчитайте, сколько символов печатает один вызов.
Определите, при каких n печать повторяется.
Сложите вклад вызова и всех детей.
Не забывайте про print после рекурсивного вызова.
Проверьте на маленьком n, нарисовав дерево.

Пример

Процедура печатает один символ, при n ≥ 1 печатает второй и вызывает F(n−1) и F(n−2). Сколько символов выведет F(28)?

from functools import lru_cache

@lru_cache(None)
def stars(n):
    if n < 1:
        return 1          # один print('*')
    return 2 + stars(n - 1) + stars(n - 2)

print(stars(28))  # 2496118

Ответ2 496 118 символов.

Задача № 600 (база Kompege).

когда процедура печатает числа

Сумма выведенных чисел

Когда использовать: Нужно найти сумму чисел, которые выведет рекурсивная процедура.

Запишите, какие числа печатает текущий вызов.
Проверьте условие печати отдельно.
Сложите числа текущего вызова с суммами детей.
Для базы учтите только гарантированную печать.
Проверьте на n = 2 и n = 3.

Пример

Процедура печатает 2n+1; при n > 1 печатает ещё 3n−8 и вызывает F(n−1), F(n−4). Найдём сумму для F(50).

from functools import lru_cache

@lru_cache(None)
def total(n):
    s = 2 * n + 1
    if n > 1:
        s += (3 * n - 8) + total(n - 1) + total(n - 4)
    return s

print(total(50))  # 170480034

Ответ170 480 034.

Задача № 604 (база Kompege).

когда нужна сумма F(k)

Сумма значений на отрезке

Когда использовать: Условие просит сумму значений функции для k из диапазона, а не одно значение.

Заполните таблицу значений до правой границы.
Для каждого k из диапазона примените формулу.
Сложите значения.
Не включайте лишние границы.
Проверьте количество слагаемых: b − a + 1.

Пример

F(n) = n + 3 при n ≤ 3; дальше F(n) = F(n−2) + n или +2n в зависимости от чётности F(n−1). Найдите сумму F(40)…F(50).

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n <= 3:
        return n + 3
    if f(n - 1) % 2 == 0:
        return f(n - 2) + n
    return f(n - 2) + 2 * n

print(sum(f(n) for n in range(40, 51)))  # 8508

Ответ8 508.

Задача № 928 (база Kompege).

когда n десятки тысяч

Аналитика и большие n

Когда использовать: Прямой перебор слишком долог, но шаг образует арифметическую прогрессию или повторяющийся блок.

Раскройте несколько первых шагов.
Найдите общий вид суммы или произведения.
Примените формулу прогрессии.
Подставьте границы и проверьте на малом n.
Для точности используйте целые числа.

Пример

H(x) = 1 при x < 3; H(x) = 2x − 1 + H(x−2) при x > 2. Найдём H(3033).

N = 3033
count = (N - 3) // 2 + 1
S = (3 + N) * count // 2
print(2 * S - (N - 1) // 2 + 1)  # 4601061

Ответ4 601 061.

Задача № 9865 (база Kompege).

когда нужно найти x

Обратная задача: параметр x

Когда использовать: Известно значение выражения с параметром x, и нужно найти сам параметр.

Выразите разность через несколько шагов рекурсии.
Соберите коэффициенты при x.
Решите линейное уравнение.
Проверьте x подстановкой.
Если аналитика сложна, переберите x в диапазоне.

Пример

F(n) = n при n ≥ 3000; F(n) = n + x + F(n+2) при n < 3000. Найдите целое x, если F(2984) − F(2988) = 5916.

def f(n, x):
    if n >= 3000:
        return n
    return n + x + f(n + 2, x)

for x in range(-100, 100):
    if f(2984, x) - f(2988, x) == 5916:
        print(x)  # -27
        break

Ответx = −27.

Задача № 12779 (база Kompege).

когда нужен перебор аргументов

Количество n по условию

Когда использовать: Спрашивают, сколько n из диапазона дают нужное свойство значения функции.

Определите диапазон и включение границ.
Заполните таблицу F(n) до верхней границы.
Для каждого n проверьте свойство.
Увеличьте счётчик при выполнении условия.
Проверьте края диапазона отдельно.

Пример

F(n) = G(n−1); G(n) = n при n < 10; G(n) = G(n−2) + 1 при n ≥ 10. Сколько n на отрезке [1; 100] дают полный квадрат?

from functools import lru_cache

@lru_cache(None)
def G(n):
    if n < 10:
        return n
    return G(n - 2) + 1

def F(n):
    return G(n - 1)

count = 0
for n in range(1, 101):
    x = F(n)
    if x > 0 and int(x ** 0.5) ** 2 == x:
        count += 1

print(count)  # 12

Ответ12 значений n.

Задача № 11948 (база Kompege).

Шпаргалка: формулировка → метод

В условии	Что делать
«Чему равно F(n)», n небольшое	подстановка и дерево вызовов
«n = 10³…10⁶»	таблица значений снизу вверх
«F(n−1) + F(n−2)»	два предыдущих значения, Фибоначчи
«F(n+1)», «F(2n)»	считать от базы вниз
«n % 2», «n % 3»	ветвление по остаткам
«если F(n−1) чётно»	сначала вычислить предыдущее значение
«F(n) и G(n)»	пара значений на каждом шаге
«сколько вызовов»	C(n) = 1 + C(детей)
«сколько символов *»	вклад каждого вызова
«сумма выведенных чисел»	складывать напечатанное
«сумма F(k) на отрезке»	цикл по таблице значений
«F(n) / F(k)»	сократить общие множители
«F(a) − F(b)»	раскрыть разность через шаги
«сколько n подходят»	перебор n и проверка свойства
«большое n и прогрессия»	формула суммы
«найти x»	уравнение или перебор
«ответ по модулю»	брать остаток на каждом шаге
«глубина > 1000»	setrecursionlimit или таблица
«отрицательные n»	проверить базу и n % 10
«проверка»	малое n и ручное дерево

Видеоразборы по теме

Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.

По базе Kompege: 1 011 задач, 70 решений (61 программное и 9 текстовых) и 260 видеоразборов (161 YouTube, 66 VK, 33 Rutube) по заданию 16. Для методов отобраны решения задач № 10929, 11235, 13952, 273, 598, 591, 4328, 600, 604, 928, 9865, 12779 и 11948; дополнительные примеры и видеоразборы — задачи № 15, 217, 308, 499, 602, 603 и 19706; примеры переработаны в учебные.

Разборы из видео

Задачи, которые разбирают в курсе

Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.

№ 5537

разбор из видео · 2027

Отношение F(2023) / F(2020)

F(1) = 1; F(n) = n·F(n−1) при n > 1. Чему равно значение выражения F(2023) / F(2020)?

from functools import *
@lru_cache(None)
def f(n):
    if n == 1:
        return 1
    return n * f(n - 1)

for i in range(1, 2020):
    f(i)
print(f(2023) / f(2020))

Ответ8266912626

Смотреть с 06:05

Полный архив

Все фрагменты видеоразборов

По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.

Показать все фрагменты (31)

2024 · 00:00 Приветствие

(№ 5537) (Демо-2023) Алгоритм вычисления значения функции F(n), где п — натуральное число, задан следующими соотношениями:

def f(n):
if n<=1:
return 1
return f(n-1)+f(n-2)
print(f(4))

Смотреть с 00:00

2024 · 01:45 Как работае рекурсия?

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 01:45

2024 · 25:50 Запись рекурсии 1

A 3) Алгоритм вычисления функции (и) задан следующими соотношениями: Чему равно значение функции F(39)?

Смотреть с 25:50

2024 · 31:12 Запись рекурсии 2

a 17) Алгоритм вычисления функции F(7) задан следующими соотношениями: F(x) = (n+ 2)-For4), если и = 3 и делится на 3, F(n) = n+ Fort) +2-F(r-2), если и = 3 и не делится на 3. Чему равно значение функции F(20)?

Смотреть с 31:12

2024 · 39:05 Запись рекурсии 3

18) Алгоритм вычисления функций F(t) и С(и) задан следующими соотношениями: Чему равно значение (14) + G(14)?

def f(n):
if i return 1
def g(n):
print((14)+g(14))

Смотреть с 39:05

2024 · 45:35 Число звёздочек

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 45:35

2024 · 55:30 Сумма чисел

A 42) Алгоритм вычисления функций Е(м) и С(и) задан следующими соотношениями: Чему равна сумма цифр значения функции F(50)?

Смотреть с 55:30

2024 · 59:55 Мемоизация рекурсии

42) Алгоритм вычисления функций Fn) и G(n) задан следующими соотношениями: Чему равна сумма цифр значения функции (50)?

def
return f(n-1)+34g(n-1) m
def g(n):
print(sum(int(d) for d in str(s)))

Смотреть с 59:55

2024 · 1:21:30 РЕКЛАМА

Джобс) Алгоритм вычисления функции F(m), где mn — целое число, задан следующими F(n) = - F(n- 1) для остальных случаев. Чему равно значение F(20)?

Смотреть с 1:21:30

2024 · 1:24:15 Сдвиг границы рекурсии

Джобс) Алгоритм вычисления функции F(7), где и — целое число, задан следующими Ее) =-Е(1- 1) для остальных случаев. Чему равно значение F(20)?

Смотреть с 1:24:15

2024 · 1:42:10 Проверка диапазона 1

Я 58) Алгоритм вычисления функции Е(п) задан следующими соотношениями: F(n) =2 - Еон-1) + F(n+4), при чётных я < 30 F(n) = F(r+2) + 3 - F(n+5), при нечётных и < 30 содержит не менее двух значащих цифр 0 (в любых разрядах).

Смотреть с 1:42:10

2024 · 1:48:00 Проверка диапазона 2

58) Алгоритм вычисления функции Е(м) задан следующими соотношениями: F(n) =2 - Еон-1) + F(r+4), при чётных n < 30 F(n) = F(r+2) + 3 - F(n+5), при нечётных и < 30 содержит не менее двух значащих цифр 0 (в любых разрядах).

def f(n):
for n in range(1,1001):
print(k)

Смотреть с 1:48:00

2024 · 1:53:00 Проверка диапазона 3

я 89) Алгоритм вычисления функции Ё("), где 2 — натуральное число, задан следующими F(n) = F(n/3)-1, когда п >2 и делится на 3, F(n) = Еи- 1) + 17, когда и > 2 и не делится на 3.

Смотреть с 1:53:00

2024 · 2:04:40 Проверка диапазона 4

A 89) Алгоритм вычисления функции Ё( ), где 2 — натуральное число, задан следующими F(n) = F(n/3) — 1, когда и > 2 и делится на 3, F(n) = Еи- 1) + 17, когда п > 2 и не делится на 3.

def f(n):
if
print(k)

Смотреть с 2:04:40

2024 · 2:08:45 Прикладная рекурсия 1

Уфа) Определите количество различных натуральных значений я таких, чт &

if m= 0:
else: if m= 0 then return 1;
return a return n*F(n,m-1) ;

Смотреть с 2:08:45

2024 · 2:13:30 Прикладная рекурсия 2

Уфа) Определите количество различных значений я таких, что я и т — натуральные числа, а значение F(x, 71) равно числу 30.

else: if m — 0 then return 0;
return d else return ntF(n,m-1) ;
def f(n, t):
else: d = n+f(n,m-1)
return d .
for n in range(1,100):
for m in range(1,100):
if (n,m) == 30:
print(k)

Смотреть с 2:13:30

2024 · 2:19:55 Неопределённые значения 1

a 82) Алгоритм вычисления функции F(n), где и — целое число, задан следующими соотношениями: Ея) =п + F(n/2-1), когда п > 5 и делится на 4, NBecteo ree hes pas Назовите максимальное значение и, для которого возможно вычислить F(z).

Смотреть с 2:19:55

2024 · 2:28:05 Неопределённые значения 2

if £(n)>1000:
print(n)

Смотреть с 2:28:05

2024 · 2:35:40 Окончание и напутствия

и 81) Алгоритм вычисления функции (п), где и — целое число, задан следующими соотношениями: Е) = п + Еб/5 +1), когда > 5 и делится на, есь ноз ина pool F(n) =п + F(n + 6), когда п > 5 и не делится на 5: Назовите минимальное значение и, для которого Е(и) определено и больше 1000.

if f(n)>1000:
print(n)

Смотреть с 2:35:40

2027 · 00:00 Приветствие

Смотреть с 00:00

2027 · 06:05 Задание I

(№ 5537) (Демо-2023) Алгоритм вычисления значения функции F(n), где п — натуральное число, задан следующими соотношениями: Чему равно значение выражения F(2023) / F(2020)?

def f(n)
from functools import *
return n*f(n-1)
f = {}
f[1] = 1
for n in range(2,2024):
f[n] = f[n-1]*n
print(f[2023]/f[2020])

Смотреть с 06:05

2027 · 18:55 Задание II 6756

(№ 6756) (ЕГЭ-2023) Алгоритм вычисления функиии Fn), где п — натуральное число, задан следующими соотношениями: Чему равно значение выражения Е(3027) — F(3023)?

def f(n):
return 2*n+5+f(n-2)
f[1]=3
f[2]=3
f[n] = 2*n+5+f[n-2]

Смотреть с 18:55

2027 · 26:35 Задание III (убывание)

Шастин) Алгоритм вычисления значения функции Ё (п), где т - целое число, задан следующими соотношениями:

Смотреть с 26:35

2027 · 41:40 Задание IV

(№ 7524) (ЕГЭ-2024) Алгоритм вычисления значения функции F(n), где п — натуральное число, задан следующими соотношениями: Чему равно значение выражения (Е(2024)/

from functools import *
def
return 2ensf(n-1)
print( (f(2024)//16 - f(2023))/f(2022) )
print( (+[2024]//16 - +[2023])/+[2022] )

Смотреть с 41:40

2027 · 53:50 Задание V (убывание)

Алгоритм вычислен вариант 20264уровень: Базовый) > X Чему равно значение выражения (F(247563)/519 — 477 x F(247560)) /F (247557)? ия функции Р(п), дет - целое число, задан следующими соотношениями:

Смотреть с 53:50

2027 · 1:01:40 Задание VI (ограничение размера кэша)

Алгоритм вычисления значения функции F(n), где п — натуральное следующими соотношениями: Чему равно значение выражения F(2025) - F(1000)?

Смотреть с 1:01:40

2027 · 1:24:00 Задание VII

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:24:00

2027 · 1:31:10 Задание VIII 29970

Алгоритм вычисления значения функции (п) и G(n), где п - целое число, задан следующими соотношениями: Чему равно значение выражения Р(37811)?

Смотреть с 1:31:10

2027 · 1:39:10 Задание IX (две функции)

Алгоритм вычисления значения функции Е(п) и С(п), где п - целое число, задан следующими соотношениями: Чему равно значение выражения F (37811)?

S96 = 2.615
return g(n-3)+1

Смотреть с 1:39:10

2027 · 1:50:15 Задание X (две функции)

def g(n):
def f(n):
return f(n-8)+1095
print(f(548))
for n in range(22600,0,-1):
else: f[n] = f[n-8]+1095
print(f[548])

Смотреть с 1:50:15

2027 · 2:00:05 Окончание и напутствие 8937

def g(n):
def f(n):
return f(n-8)+1095
print(f(548))
for n in range(22600,0,-1):
f = {}
for n in range(8,549):

Смотреть с 2:00:05

Типичные ошибки

неверный базовый случай
не считаются вызовы
потеря ветви
ошибка в целочисленном делении

Ключевые формулы

F(n) = база при n ≤ b; F(n) = шаг(F(n−1), F(n−2), …) при n > b
C(n) = 1 + C(n−1) + C(n−2)
S = (a₁ + aₖ)·k / 2

Практика

ФИПИОткрытый банк заданий Навигатор · 2026Алгоритмы ДемоверсияКИМ 2027 МетодикаРазбор ошибок 2026

Навигатор и методические рекомендации опубликованы в 2026 году: номера заданий в них могут отличаться от нумерации 2027 года. Ориентируйтесь на тему.