Файл с текстом параграфа

[Поляков]

Скачать файл: Рекурсия

[bonzo]

Параграф про рекурсию я бы начал с объяснения, зачем это нужно -- Вы уже писали ранее про принцип "разделяй и властвуй", который приводит к появлению функций. Теперь можно сказать, что с помощью этого принципа сложная задача разбивается на несколько более простых (откуда возникает идея функции), но есть и вторая ситуация -- сложная задача сводится к задаче меньшей размерности (так, чтобы найти максимум из трех чисел, надо найти два максимума из двух чисел). Если программировать такой алгоритм, то возникнет ситуация, когда написанная функция максимума вызывает сама себя. Эта ситуация и есть рекурсия. Далее можно продолжать как у Вас про факториал.

На третьей странице вводится термин итеративный с латинским объяснением, что уже было сделано в предыдущих параграфах.

Объяснение про стеки я бы несколько сократил -- детали про адреса возврата и регистры на этом уровне излишни. Мне кажется, достаточно сказать, что при каждом вызове выделяется специальная область для хранения локальных переменных функции и служебных нужд организации самого вызова и возврата из него. Эта память и называется стеком. Больше деталей это дополнительный урок.

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

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

"В языке Python хвостовая рекурсия не оптимизируется." -- главное, чтобы они Jit не успели вставить до выхода учебника

Вижу, что в задачах с массивами появилось упоминание сведения к подзадаче -- еще одна причина вставить такой текст в самое начало.

[Neket]

1. "Любой рекурсивный алгоритм может быть запрограммирован без использования рекурсии" -- утверждение довольно сильное, я не уверен в его справедливости в общем случае, особенно с учетом только той функциональности циклов, которая была разобрана на предыдущих уроках. Лучше уточнить объект утверждения до рекурсии с одним рекурсивным вызовом (если не хочется вводить понятие хвостовой рекурсии в пункте без звездочки).

2. Размышления про бесконечную цепочку вызовов наверное лучше заменить на более практически применимые рассуждения о максимальной глубине рекурсии -- достичь его вполне реально, и обусловлено оно дополнительной памятью, в то время как максимальное число итераций цикла ограничивается только временем, отведенным на его работу.

3. К задаче 1 у меня несколько вопросов. Во-первых, в рекурсивном решении используется вещественное деление, а в итеративном -- целочисленное. Во-вторых, из-за скорости роста функции, вычисления производятся в длинных числах, которые не упоминались, и вопросов о которых на данном этапе скорее всего хотелось бы избежать. Плюс ко всему, если подобный пример будет разбираться в рамках другого языка программирования, там он с большой вероятностью работать не будет. Возможно, стоит подобрать функцию с меньшей скоростью роста, чтобы ее результат при достижении максимальной глубины рекурсии все еще убирался в целочисленный тип.

[nikolay]

1. В определении косвенной рекурсии возможно стоит добавить, что в противном случае рекурсия называется прямой.

2. Пример с факториалом, в нем описыватеся исключение. Возможно вынести это в раздел со звездоской, а в простом варианте обойтись просто проверкой? А то сейчас вводится понятие исключения, которое не относиться к рекурсии и возможно возникнет путанница в понимании.

3. На фоне остальных параграфов данный выглядит довольно сложным и много понятий. В блоке про стек есть много понятий "стек вызовов", "стековый кадр", возможно для школьного текста дать короткое интуитивное описание перед формальным (например, стек — "память, куда компьютер складывает незавершённые вызовы функций в виде "стопки" (спотки тарелок или что-то типа того).

[volkov]

1. "Любой рекурсивный алгоритм может быть запрограммирован без использования рекурсии" -- утверждение довольно сильное, я не уверен в его справедливости в общем случае

Вроде же это просто соответствует утверждению про алгоритмическую полноту по Тьюрингу лямбда-исчисления?

, особенно с учетом только той функциональности циклов, которая была разобрана на предыдущих уроках.

Но вот это да.

[volkov]

Несколько соображений.

Может иметь смысл провести параллель с методом математической индукции, например, просто виде сноски - иногда тем школьникам, кто про неё знает, это помогает.

Введение понятия стека вызовов как бы мимоходом в процессе объяснения накладных расходов на вызов функции (какой? только рекурсивной) кажется, скорее всего будет понято не очень. Как самый минимум, я бы нарисовал серию картинок, поясняющих, как, например, будет вычисляться fact(3) или что-то ещё - тогда хоть что-то будет понятно. Иначе, похоже, было бы достаточно общих слов, что каждый вызов функции - это некоторые дополнительные расходы на создание памяти её переменных и вспомогательной информации (например - "запоминания" адреса возврата - но соглашусь с коллегами, не уверен, насколько эта деталь важна).

Ещё один методический вопрос, который возникает - а знают ли школьники к этому моменту уже про вообще само понятие стека? По-хорошему, стоит тогда вначале напомнить понятие стека (или рассказать где-то раньше, ну и очереди заодним).

У школьников точно есть путаница с памятью одной и той же переменной функции в eё разных экзмеплярах вызова (не уверен, что такой термин существует, но я пытаюсь использовать такое словосочетание, когда рассказываю школьникам - и вот каждому на данный момент вызванному экземпляру соответствует кадр стека). В принципе, у школьников наблюдается даже путаница по поводу переменных с одним и тем же именем из разных функций.

В идеале (хотя, возможно, для "базового" учебника это и too much) я бы всё-таки описал качественно программный стек уже в разделе про подпрограммы - как механизм реализации, возможно, упомянув, что такой подход позволяет поддерживать и рекурсивные вызовы, про которые будет речь отдельно.

Для школьников я рисую программный стек (качественно) - примерно как прикрепил на фото (про рекурсию под рукой фото доски не нашлось, тут у нас было что-то про указатели и неправильные реализации функции swap). Может быть, что-то в таком изобразить?

"Быстрая сортировка" - с одной стороны важный алгоритм, с другой - мне кажется, для базового учебника даже, возможно, более необходим пример бинарного поиска (пусть его несложно написать и не рекурсивно): потому что он даже просто "в жизни" вживую вполне применим "человечески" - можно начать с примера, как его можно использовать в поиском в книжке-справочнике, где имена расположены по порядку (по алфавиту).

Ещё один возможный полезный пример - это что если написать вычисление элемента последовательности Фибоначчи "в лоб" по рекурсивной формуле, то это приведёт к весьма неэффективному алгоритму.

Возможно, "обработку массивов" лучше ввести как обработку последовательности вообще - обработали её начальный элемент и, рекурсивно, все остальные, просто проиллюстрировать эту более общую идею идею, действительно, питоновским списком-массивом.

Вместо перевода в двоичную с.с. я бы, пожалуй, предпочёл увидеть алгоритм возведения и алгоритм быстрого возведения в степень (их сопоставление как раз хорошо иллюстрирует силу подхода "разделяй и властвуй" и понятно школьникам) - но соглашусь, что это дело вкуса.