Информатика · ЕГЭ · 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.
- Выпиши начальное значение и все ветви правила.
- Отмечай отдельную строку для каждого вызова.
- Отличай число вызовов, напечатанные значения и возвращаемый результат: это разные вопросы.
Что запомнить
Сначала дойди до остановки, затем верни результаты наружу. Для каждого вызова сохраняй его собственные данные и ожидающее действие.
Попробовать на Алгосе
Программирование на Python для ЕГЭ
В теме «Рекуррентные выражения» проследи вызовы вручную до перехода к программному вычислению.
Перейти к курсу Все курсы