Информатика · ЕГЭ · 4 мин чтения

Как проследить рекурсию в задаче по информатике?

Редакция Алгоса · Обновлено

Короткий ответ

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

Найди правило остановки до вычислений

Пусть F(1) = 1, а для целых n > 1 задано F(n) = F(n − 1) + n. Запись F(4) означает просьбу вычислить результат при входе 4. Но для этого сначала нужно узнать F(3), затем F(2), затем F(1). Последнее значение уже дано и не требует нового обращения.

Что запоминает незавершённый вызов?

Вызов F(4) ждёт результат F(3), чтобы прибавить к нему 4. Вызов F(3) отдельно ждёт F(2) и помнит свою тройку. Каждое ожидание сохраняет своё значение n; переход к меньшему n не стирает данные предыдущего вызова.

Спускайся по вызовам, поднимайся по результатам

Нарисуй две части вычисления. Сначала входное число, или аргумент, уменьшается: 4 → 3 → 2 → 1. Затем известный результат 1 начинает возвращаться наружу. Каждое отложенное сложение выполняется, когда получено нужное число. В нашем примере результат F(4) равен сумме чисел от 1 до 4.

Полное разворачивание
Вызовы: F(4) → F(3) → F(2) → F(1).
F(1) = 1.
F(2) = 1 + 2 = 3.
F(3) = 3 + 3 = 6.
F(4) = 6 + 4 = 10.
Проверка обычной суммой: 1 + 2 + 3 + 4 = 10.

Смотри, где стоит вывод или сложение

Команда до обращения к самой себе выполняется на пути вниз, команда после него — после возвращения. Поэтому одинаковые вызовы могут печатать числа в разном порядке. Также проверь приближение к остановке: правило с n + 1 вместо n − 1 не достигнет 1 при старте с 4.

  1. Выпиши начальное значение и все ветви правила.
  2. Отмечай отдельную строку для каждого вызова.
  3. Отличай число вызовов, напечатанные значения и возвращаемый результат: это разные вопросы.

Что запомнить

Сначала дойди до остановки, затем верни результаты наружу. Для каждого вызова сохраняй его собственные данные и ожидающее действие.

Попробовать на Алгосе

Программирование на Python для ЕГЭ

В теме «Рекуррентные выражения» проследи вызовы вручную до перехода к программному вычислению.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы