+Оглавление
Разбираем задачу №11 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Описание очень лаконичное: умение исполнить рекурсивный алгоритм. Задание базового уровня сложности, но предполагает около 5 минут на выполнение. Это значит, скорее всего, придётся делать много простых шагов. (Те, кто не понаслышке знаком с рекурсией, меня поддержат)
Довольно необычное для школьника индуктивное (рекурсивное) определение объекта можно дать на забавном примере: новый "орбит" со вкусом "орбита" - попробуй рекурсию на вкус. Или вот так: чтобы понять, что такое рекурсия, надо сначала понять, что такое рекурсия.
Немного о рекурсии
Формально, оба эти определения нарушают одно из главных правил рекурсии - в них нет условия завершения. Но по-простому, на пальцах объясняют, что это такое.
Вообще, когда я был маленький и только начал изучать высокоуровневые языки программирования, я уже понимал, что для того, чтобы алгоритм исполнить, надо иметь его полное описание. Но когда алгоритм вдруг в середине вызывал сам себя, у меня это вызвало ступор. Позже я, разумеется, разобрался во всём, но запомнил на всю жизнь, как впервые удивился такой "магии".
Сейчас я могу на пальцах объяснить:
Первым делом, в рекурсии важно условие её завершения. Это однозначное соответствие конкретного значения аргумента и значения функции (либо процедурного действия). Вот, например, сказали тебе, что если тебе дали число 5, то ты должен срочно ответить: 12. И всё. На этом конец.
Во вторую голову, в рекурсии важно, что делать, если нам подсунули аргумент, не дающий права сказать "на этом конец". Этот пункт и есть сама рекурсия. Здесь всегда есть указание на обработку аргумента в точно таком же алгоритме. Например, если нам дали не 5, а 7, то мы должны ещё раз прогнать, но число на 1 меньше (это уже шестёрку). Как изменять аргумент и сколько раз обрабатывать, нам должны указать.
И наконец, мы должны знать, что делать вне зависимости от того, какой аргумент нам подсунули. Часто в функциях этого вообще нет, а в процедурах - бывает.
Вообще говоря, рекурсивный алгоритм - точно такой же, как и прочие, и отлично "дебажится" с помощью таблиц трассировки или, как я учил, через прямоугольнички. Но в этом случае придётся на каждый новый "виток" свою таблицу заводить. Это очень неудобно.
Раскрытие рекурсий
Самый простой, на мой взгляд, способ обработки рекурсивных вызовов - построить граф - дерево. В нашей функции каждый раз выполняется два вызова. Первый вызов пойдёт направо, второй - налево. Итак.
Мы вызываем F(5). При этом вызове функция будет выглядеть так:
Выполняем этот алгоритм, и наносим на граф результат:
Обратите внимание, я выписываю: чему равно n, что напечатается и истинность условия в операторе if...then. Именно в таком порядке, потому что именно в таком порядке оно будет выполняться.
В условном операторе есть два рекурсивных вызова (функция вызывает сама себя два раза по очереди). Первый пойдёт направо. Теперь важно: пока этот вызов не завершится до конца, второй срабатывать не будет. Ведём линию вправо:
Условие ложно, поэтому дальнейших вызовов не будет производиться - машина их проскочит. Каждый "end;" возвращает нас на уровень вверх. На предыдущем уровне мы не закончили, пока обработали лишь F(5 div 2); Осталось обработать F(5 - 1). Его, как договорились, ведём влево:
Напечатали 5,2,4
Условие истинно, поэтому отсюда мы должны снова дважды вызвать функцию. Первый раз - направо по F(4 div 2);
Условие ложно, поэтому дальнейших вызовов не будет производиться. Снова "end;" возвращает нас на уровень вверх. На предыдущем уровне мы не закончили, пока обработали лишь F(4 div 2); Осталось обработать F(4 - 1). Его, как договорились, ведём влево:
Условие истинно, поэтому отсюда мы должны снова дважды вызвать функцию. Первый раз - направо по F(3 div 2);
Условие ложно, поэтому дальнейших вызовов не будет. Ещё раз "end;" возвращает нас на уровень вверх. На предыдущем уровне мы не закончили, пока обработали лишь F(3 div 2); Осталось обработать F(3 - 1). Его, как договорились, ведём влево:
Условие ложно, поэтому дальнейших вызовов не будет производиться - машина их проскочит. Не в последний раз "end;" возвращает нас на уровень вверх. На предыдущем уровне мы закончили, поэтому идём снова вверх - снова закончили. И, наконец, выходим из рекурсии. Обход графа выглядит так:
Обходим граф, "держась правой рукой за стенку", от зелёного к красному
Ответ:5242312
Каким бы ни был этот граф, его обход займёт у вас всего пару секунд. Сама сложность - построить его. Тут важны два правила:
1. соблюдать порядок действий. Бывают задания, в которых печатание находится, например, между вызовами. Тогда печатать мы будем только когда первый раз вернулись в узел, до того, как пошли по новой ветке.
2. соблюдать порядок обхода и направления. Это поможет нам разобраться с тем, что мы уже сделали, а что - ещё нет.
Заключение
Методов раскрытия рекурсии много. Авторы ЕГЭ предлагают использовать таблицу рекуррентных вызовов, основанную на анализе алгоритма, или таблицу трассировки (там же отмечается, что это будет трудновато). На мой взгляд, графическая трассировка даёт существенное преимущество в наглядности работы рекурсии. Для работы с косвенной рекурсией (когда есть две функции, вызывающие друг друга) этот метод применим на 100%, надо лишь не забывать, что на разных уровнях у нас будут разные функции: на чётных - одна, на нечётных - другая.
Есть ещё один хитрый метод. Можно записать программу, заменив рекурсивные вызовы прямо на куски кода. Трудоёмко, но гарантировано верно. Да и в 5 минут, после хорошей тренировки, уложиться можно:
Ну и отладку в среде разработки никто не отменял
PS
Любопытно проследить многолетнюю тенденцию для этих заданий. Вот выдержки из аналитических отчётов ФИПИ за разные годы:
2015 (выполнение 25,7 %), 2016 (выполнение 36,3 %)
Видимо, проблема заключается в том, что разъяснению понятия рекурсии и механизма осуществления рекурсивного вызова было уделено недостаточно внимания
2017 (выполнение 57,1 %)
Следует отметить положительную тенденцию последних лет на увеличение процента выполнения такого рода заданий. По-видимому, она обусловлена улучшением преподавания темы «Рекурсия»
2018 (выполнение 35,7 %), 2019 (выполнение 38,6 %) - без уточнений:
Основная содержательная ошибка при выполнении такого типа заданий базового уровня – неспособность построить верную последовательность косвенных рекурсивных вызовов.