Вспомогательные алгоритмы. Рекурсия: ЕГЭ по информатике

Вспомогательные алгоритмы (процедуры и функции) позволяют разбивать программу на подзадачи и повторно использовать код. Рекурсия — это вызов алгоритмом самого себя; в ЕГЭ по информатике встречается в заданиях на анализ рекурсивных функций, вычисление значений, построение дерева вызовов и перевод…

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

• Вспомогательный алгоритм — это именованная часть программы, которая может вызываться из других частей; в языках программирования реализуется как процедура или функция.
• Процедура выполняет действия и не возвращает значение; функция возвращает результат и может использоваться в выражениях.
• Параметры (аргументы) передаются вспомогательному алгоритму для обработки; различают формальные и фактические параметры.
• Рекурсия — приём, при котором алгоритм вызывает сам себя с другими аргументами.
• Для корректной рекурсии обязательно наличие базового случая (условия остановки), иначе будет бесконечная рекурсия и переполнение стека.
• Каждый рекурсивный вызов сохраняет своё состояние в стеке вызовов; глубина рекурсии ограничена размером стека.

Термины и понятия

• Вспомогательный алгоритм: поименованная часть программы, реализующая некоторую подзадачу и вызываемая из других частей программы.
• Процедура: вспомогательный алгоритм, который выполняет действия, но не возвращает значение.
• Функция: вспомогательный алгоритм, который возвращает значение и может использоваться в выражениях.
• Рекурсия: свойство алгоритма вызывать самого себя непосредственно или через другие алгоритмы.
• Базовый случай (условие остановки): случай, при котором рекурсивный алгоритм не вызывает себя, а возвращает результат напрямую.
• Шаг рекурсии: правило, по которому алгоритм вызывает себя с изменёнными аргументами.
• Стек вызовов: структура данных, хранящая информацию об активных вызовах функций (адрес возврата, локальные переменные, параметры).
• Глубина рекурсии: максимальное количество одновременно активных рекурсивных вызовов.

Частые ошибки

• Отсутствие базового случая или неверное условие остановки рекурсии, что приводит к бесконечной рекурсии.
• Неправильное изменение аргументов при рекурсивном вызове (например, забыли уменьшить n), что также ведёт к зацикливанию.
• Неучёт порядка вызовов и порядка выполнения операций после возврата из рекурсии (например, вывод до или после рекурсивного вызова).
• Ошибки при ручном вычислении рекурсивной функции: путаница в значениях, особенно при нескольких рекурсивных вызовах (как в числах Фибоначчи).

Как пройти тему

В курсе «Информатика» тема «Вспомогательные алгоритмы. Рекурсия» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Понятие алгоритма. Свойства алгоритмов. Способы записи
• Базовые алгоритмические конструкции: следование, ветвление, цикл
• Анализ алгоритмов. Определение результата работы алгоритма
• Поиск ошибок в алгоритмах. Отладка
• Обработка одномерных массивов: поиск, сортировка, статистика
• Обработка двумерных массивов (матриц)

← Предыдущая тема: Базовые алгоритмические конструкции: следование, ветвление, цикл
Следующая тема: Анализ алгоритмов. Определение результата работы алгоритма

Все темы: ЕГЭ по информатике