Роботландский Университет 99/00
Азы программирования
Турнир Кукарачи
р а з б о р  п о л е т о в
--------------------------------

                     Уважаемые коллеги!

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

Будем считать этот материал началом обсуждений конкурсного опыта.

Материал довольно не полный, уверен вопросов, которые интересно
осветить, гораздо больше.

Кроме того, излагая свой взгляд, я не думаю, что все с ним согласятся.
Скорее даже уверен в обратном. Возникнет полезная дискуссия.


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

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

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

Посмотрите на решение первой задачи конкурса:

ЭТО вход
  шаг
  ЕСЛИ + ТО { ВВЕРХ ВНИЗ вход ВЛЕВО }
  ИНАЧЕ ЕСЛИ НЕ ПУСТО ТО вход
  ИНАЧЕ ВВЕРХ
КОНЕЦ

ЭТО шаг
  ВНИЗ
  ВПРАВО
  ВВЕРХ
КОНЕЦ

Казалось бы, зачем выделять в процедуру код "ВНИЗ ВПРАВО ВВЕРХ", если
он встречается в программе ровно один раз?

Команда "шаг" лучше отражает суть действий, чем безликий набор "ВНИЗ
ВПРАВО ВВЕРХ".

Часто имеет смысл выделить в отдельную процедуру даже одну команду.
В решении задачи 6 написано:

                                   │
ЭТО текст                          │Состояние (текст).
 ВВЕРХ                             │Устанавливаем исполнитель в конец
КОНЕЦ                              │записи.
                                   │

Имя процедуры соответствует названию состояния "текст" на
диаграмме переходов. Не важно, что это состояние содержит в программе
только одну команду. Безликая по отношению к логике программы, команда
ВВЕРХ не может сравниться с содержательным вызовом "программа".
Поэтому, с точки зрения правописания программ, экономить на процедуре
"текст" не стоит.

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

ПОВТОРИ 2 ВЛЕВО или  ВЛЕВО ВЛЕВО?
- - - - - - - - - - - - - - - - -
Мне кажется, что с точки зрения правописания программ, обе формы
записи имеют место на существование.

Для чего вводится в языке команда ПОВТОРИ? Для сокращения записи.
Никакой другой смысловой нагрузки, в отличие, например, от команды
ПОКА эта конструкция не несет.

ПОВТОРИ 2 ВЛЕВО всегда эквивалентна ВЛЕВО ВЛЕВО

ПОКА ПУСТО ВЛЕВО иногда эквивалента СТОЯТЬ, иногда ВЛЕВО, иногда
ВЛЕВО ВЛЕВО.

Итак, команда ПОВТОРИ не имеет другого смысла, кроме как сокращения
записи.

Поэтому ПОВТОРИ 2 ВЛЕВО и ВЛЕВО ВЛЕВО почти эквивалентны. Дело вкуса
программиста, какому варианту отдать предпочтение. А вот записи
ПОВТОРИ 3 ВЛЕВО, ПОВТОРИ 4 ВЛЕВО, ... имеют явные преимущества.

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

Нижний регистр для имен процедур позволяет разрушить однородность
программного текста, внести в него "шершавость". Эта шершавость,
благодаря содержательным именам процедур, образуется в правильных
местах программного полотна, именно там, где мы наметили структурные
узлы:

ЭТО вход
  шаг
  ...
КОНЕЦ

ЭТО шаг
...

КОНЕЦ


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

Вот реальный пример кода из конкурсной работы:

ЭТО ТЕКСТ
ШАГ
ЕСЛИ а ТО СЛОВО
ИНАЧЕ ЕСЛИ м ТО СЛОВО                  
ИНАЧЕ ОШИБКА                           
КОНЕЦ
ЭТО СЛОВО                              
ШАГ
ЕСЛИ а ТО СЛОВО
ИНАЧЕ ЕСЛИ м ТО СЛОВО
ИНАЧЕ ЕСЛИ . ТО ОТВЕТ1                 
ИНАЧЕ ЕСЛИ _ ТО СЛОВО1                 
ИНАЧЕ ЕСЛИ , ТО СЛОВО1
ИНАЧЕ ЕСЛИ ПУСТО ТО ОТВЕТ
ИНАЧЕ ОШИБКА                           
КОНЕЦ
ЭТО СЛОВО1
ШАГ
ЕСЛИ а ТО СЛОВО
ИНАЧЕ ЕСЛИ м ТО СЛОВО
ИНАЧЕ ОШИБКА
КОНЕЦ                                  

У вас зарябило в глазах? Уверен, что если вам нужно вникнуть в этот
текст, то, для начала, вы раздвинете процедуры. А еще, конечно,
неплохо внести структурные отступы, изменить регистр имен процедур.
Получится так:

ЭТО текст
  шаг
  ЕСЛИ       а ТО слово
  ИНАЧЕ ЕСЛИ м ТО слово
  ИНАЧЕ           ошибка
КОНЕЦ

ЭТО слово
  шаг
  ЕСЛИ       а     ТО слово
  ИНАЧЕ ЕСЛИ м     ТО слово
  ИНАЧЕ ЕСЛИ .     ТО ответ1
  ИНАЧЕ ЕСЛИ _     ТО слово1
  ИНАЧЕ ЕСЛИ ,     ТО слово1
  ИНАЧЕ ЕСЛИ ПУСТО ТО ответ
  ИНАЧЕ               ошибка
КОНЕЦ

ЭТО слово1
  ШАГ
  ЕСЛИ       а ТО слово
  ИНАЧЕ ЕСЛИ м ТО слово
  ИНАЧЕ           ошибка
КОНЕЦ

Это уже можно читать, правда?


запись переключателей
- - - - - - - - - - -
Так писать переключатель:

  ЕСЛИ +        ТО уборка ИНАЧЕ
  ЕСЛИ НЕ ПУСТО ТО слово  ИНАЧЕ ВВЕРХ

не надо! Кажется, что это не переключатель, а две условных команды.
Надо писать так:

  ЕСЛИ       +        ТО уборка
  ИНАЧЕ ЕСЛИ НЕ ПУСТО ТО слово
  ИНАЧЕ                  ВВЕРХ


Мне кажется, что такая запись переключателя:

ЭТО Слово
 Шаг
 ЕСЛИ а                                
  ТО Слово                             
  ИНАЧЕ ЕСЛИ м                         
         ТО Слово                      
         ИНАЧЕ ЕСЛИ .
                ТО Точка               
                ИНАЧЕ ЕСЛИ _           
                       ТО Текст
                       ИНАЧЕ ЕСЛИ ,
                              ТО Текст
                           ИНАЧЕ Ошибка
КОНЕЦ //Слово


тоже не является хорошей.

Для переключения в языках программирования существует специальная
команда switch, которая записывается не лесенкой:

   switch (выражение)
   {
     case значение1:
                    команды
                    break;

     case значение2:
                    команды
                    break;
     ....

     case значениеN:
                    команды
                    break;
     default:
                    команды

   }

В языке Кукарачи нет такой команды, и мы моделируем ее при помощи
ИНАЧЕ ЕСЛИ

В каком то смысле можно рассматривать это построение как особую
языковую конструкцию и записывать подобно switch.

В рекомендуемой ниже записи гораздо легче увидеть переключение, так
как происходит вертикальное выравнивание:

 ЕСЛИ       а ТО Слово
 ИНАЧЕ ЕСЛИ м ТО Слово
 ИНАЧЕ ЕСЛИ . ТО Точка
 ИНАЧЕ ЕСЛИ _ ТО Текст
 ИНАЧЕ ЕСЛИ , ТО Текст
 ИНАЧЕ           Ошибка
            │    │
            │    │
            │    │
     уровень     уровень
     условий     команд


куда прятать пружинку
- - - - - - - - - - -
Посмотрите на эти две процедуры:


ЭТО вверх               ЭТО вверх
 ЕСЛИ НЕ ПУСТО           ЕСЛИ НЕ ПУСТО
   ТО                      ТО
   {                       {
     ВНИЗ ВНИЗ ВПРАВО        ВНИЗ ВНИЗ ВПРАВО
     ВВЕРХ ВВЕРХ             ВВЕРХ ВВЕРХ
     вверх                   вверх
     ВЛЕВО                 }
   }                       ИНАЧЕ ВПРАВО
   ИНАЧЕ ВПРАВО          ВЛЕВО
КОНЕЦ                   КОНЕЦ

Вопрос для конференции un31@egroups.com:

В чем проявляется разница при выполнении этих процедур, чем она
объясняется и когда надо использовать ту или другую форму кода?

                              * * *

Роботландский Университет 99/00
Курс III "Азы программирования"
С русского на польский
24/10/99
-----------------------------------------

                     Уважаемые коллеги!


К сожалению, на мой призыв:

>    Вот тема для первой содержательной нити публикаций в нашей
> конференции: как Вы считаете, имеет ли Плюсик отношение к
> программированию, если да, то в каких разделах большой информатики без
> него никак не обойтись?

никто не откликнулся.

   Придется мне самому немного продолжить эту нить.

Запись выражения по-польски и стековые вычисления
-------------------------------------------------

   Самой первой темой  в  нашем университетском курсе "Азы прог-
раммирования" обозначен блок, связанный с исполнителем Плюсик.

   Помнится мне, что в прошлом году, кто-то из руководителей команд
сомневался в нужности Плюсика для этих самых азов программирования.
Мол, Плюсик с "настоящим" программированием никак не связан!
   Однако в именно в настоящем трансляторе без Плюсика никак не
обойтись.

   Плюсик - это модель стекового калькулятора. Среда исполните-
ля состоит из стека и вычислителя:

---------   ---------------
| Стек  |   | Вычислитель |
---------   ---------------

   Стек служит для хранения чисел.  Числа  помещаются  в стек по
одному, подобно  тому, как кольца детской пирамидки нанизываются
на стержень. За один раз взять из стека можно только  одно число
с вершины числовой пирамиды. Копия числа в стеке не сохраняется,
зато становится доступным следующее число, расположенное  "ниже"
взятого.

                 Система команд Плюсика

ЗАПОМНИ число - Число, записанное в команде отправляется на хра-
                нение в стек.

              | Все  эти  команды  работают одинаково: из  стека
              | последовательно извлекаются два  числа и отправ-
              | ляются в вычислитель для выполнения соответству-
 СЛОЖИ        | ющей арифметической  операции. Результат помеща-
 ВЫЧТИ        | ется в стек.
 УМНОЖЬ       | Второе число  из  извлеченной из стека пары, вы-
 ДЕЛИ         | числитель считает первым операндом операции.
              | Ситуация отказа возникает когда: в  стеке
              | меньше двух  чисел;  результат вычислений -
              | отрицательное число; или  выполняется деление на
              | 0.
              | Команда ДЕЛИ выполняет деление нацело.

ОЧИСТИ        - Выполнение этой команды приводит к  автоматичес-
                кому удалению всех чисел из стека.


   Сосчитать выражение типа 8-(2+3) задача не из легких! Практи-
чески все трансляторы для вычисления таких выражений сначала пе-
реводят его в обратную польскую запись, а уж потом, подобно Плю-
сику, вычисляют на стеке.

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

  Обычная запись операции:  a+b
  Обратная польская запись: ab+

  Обычная запись выражения:  a + b * (c + d/e)/f
  Обратная польская запись того же выражения: abcde/+*f/+

        Запись типа  +ab  выражения  a+b называется польской потому,
     что впервые была  введена  польским философом (!) Лукашевичем в
     связи с формулами символической  логики.  Соответственно запись
     типа ab+ для  суммы двух чисел называется обратной польской за-
     писью.
        Иными словами прямая польская запись базируется на структуре:

               <операция> <операнд> <операнд>

        А обратная  польская  запись  (которая  нас  интересует)  на
     структуре:

               <операнд> <операнд> <операция>

        В некоторых источниках обратная  польская  запись называется
     постфиксной, а  прямая  - префиксной. Этимология таких названий
     совершенно прозрачна.
        У.Маккиман, Дж.Хорнинг, Д.Уортман в книге "Генератор  компи-
     ляторов" называют обычную запись выражений - инфиксной записью,
     а польскую - суффиксной.

Сравните:
-  обычная запись выражения:  2 + 5 * (1 + 3/2)/7
-  обратная польская запись выражения:  2 5 1 3 2 / + * 7 / +
-  программа для Плюсика:
                         ЗАПОМНИ 2
                         ЗАПОМНИ 5
                         ЗАПОМНИ 1
                         ЗАПОМНИ 3
                         ЗАПОМНИ 2
                         ДЕЛИ
                         СЛОЖИ
                         УМНОЖЬ
                         ЗАПОМНИ 7
                         ДЕЛИ
                         СЛОЖИ

   Мы видим,  что  программа  для  Плюсика практически является
другой формой обратной  польской  записи выражения. Верно и об-
ратное: обратная польская запись является программой для вычис-
ления выражения  на  стеке.  Исполнитель, который выполняет эту
программу должен работать совершенно так же,  как Плюсик. Такие
исполнители содержатся практически в любом трансляторе.
   Одним словом,  вычислить выражение в обратной польской записи
совсем не трудно. Нужно построить  Плюсик.  И  этот  исполнитель
предельно прост. Выражение типа

                      2 5 1 3 2 / + * 7 / +

он должен рассматривать как запись программы работы со стеком
и вычислителем

   Алгоритм работы нового Плюсика должен быть таким:

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

     Пошаговое выполнение программы 2 5 1 3 2 / + * 7 / +
                   исполнителем Плюсик+


Выполнение программы     | Стек
-----------------------------------------------------------------
  2 5 1 3 2 / + * 7 / +  |стек пуст, исполнитель - перед записью
^                        |
  2 5 1 3 2 / + * 7 / +  |2
  ^                      |
  2 5 1 3 2 / + * 7 / +  |2 5
    ^                    |
  2 5 1 3 2 / + * 7 / +  |2 5 1
      ^                  |
  2 5 1 3 2 / + * 7 / +  |2 5 1 3
        ^                |
  2 5 1 3 2 / + * 7 / +  |2 5 1 3 2
          ^              |
  2 5 1 3 2 / + * 7 / +  |2 5 1 3/2
           ^             |
  2 5 1 3 2 / + * 7 / +  |2 5 1+3/2
              ^          |
  2 5 1 3 2 / + * 7 / +  |2 5*(1+3/2)
                ^        |
  2 5 1 3 2 / + * 7 / +  |2 5*(1+3/2) 7
                  ^      |
  2 5 1 3 2 / + * 7 / +  |2 5*(1+3/2)/7
                    ^    |
  2 5 1 3 2 / + * 7 / +  |2+5*(1+3/2)/7
                      ^  |
  2 5 1 3 2 / + * 7 / +  |2+5*(1+3/2)/7
                       ^ |

   Итак,  если  выражение  записано "по-польски", вычислить  его
совсем не трудно.
   А вот как построить программу для автоматического перевода обычной
записи в польскую?
   Этот вопрос не простой. Мы будем его касаться в теме "Задачи и
методы решения".

   В методичке по Плюсику написаны такие  рекомендации для пос-
троения программ (читай для перевода  обычной  записи  в  поль-
скую):

        Для преобразования обычного выражения в программу для Плюсика
     можно просматривать выражение последовательно слева направо, за-
     писывая команды
                           ЗАПОМНИ число
        Если после  очередной  записи команды ЗАПОМНИ выяснится, что
     над последними двумя числами в стеке  можно выполнить арифмети-
     ческую операцию, то записывается соответствующая команда.

   Хорошая рекомендация для человека! Будет хорошо, если Ваши дети ее
усвоят и будут переводить "с русского на польский" почти
автоматически. Ну, а рассмотрение формального алгоритма, пригодного
для робота, мы сделаем позднее.

                            * * *

Роботландский Университет 99/00
Курс III "Азы программирования"
Как на поле спрятать кубик. А нужно?
30/10/99
-----------------------------------------

                     Уважаемые коллеги!

Ольга Станиславовна (Челябинск, команда 3109) пишет:

>    Мы с ребятами на уроках работландии решили самостоятельно
> составлять задачки для "Кукарачи". К сожалению, при составлении задач
> на условный оператор встретились с трудностью: не знаем как на поле
> спрятать кубик. Помогите нам пожалуйста. Расскажите подробно как
> подготовить поле.

   Спасибо, Ольга Станиславовна за активный диалог! Всегда полезно и
куратору и другим командам знать, как идут дела, какие возникают
проблемы. А главное так просто: сел черкнул пару строк - и вот уже
возникает полезный разговор.

Как на поле спрятать кубик
--------------------------

   А нужно ли? Вообще говоря, нет. "Нет", для детей имеющих небольшой
опыт программирования.
   Кукарача проверяет надпись на кубике после того, как он его
толкнул. Не зависимо от того, "спрятана" надпись на кубике или нет.

#.а    ЕСЛИ а ТО        ... условие ложно
#.а    ВПРАВО ЕСЛИ а ТО ... условие будет ложно
#.а    ВПРАВО ВПРАВО ЕСЛИ а ТО ... после сдвига кубика с "а"
                                   условие истинно.

   (На рисунке: "#" - Кукарача, "." - пустая клетка, "а" - клетка с
кубиком, на котором есть надпись "a").

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

   Установка "скрытого" кубика описана в файле с документацией по
Кукараче:
Монитор
--Руководство
----Методика Плюсика и Кукарачи
------Кукарача 97. Инструкции пользователя
--------8.5. Редактор среды.

   Однако, та же информация появляется и по нажатию на F1 в то время,
когда курсор находится на рабочем поле исполнителя.
   К скрытым кубикам относятся две записи:

Перевернуть кубик - F10
Перемешать скрытые кубики - Tab

   Для того чтобы явный кубик сделать скрытым, нужно установить на
него курсор и нажать на клавишу F10. Надпись побелеет, а при смещении
курсора превратиться в знак вопрос.

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


                          * * *

Роботландский Университет 99/00
Курс III "Азы программирования"
Конкурс, мед и рекурсия
29/11/99
-----------------------------------------

           Уважаемые коллеги!

   В прошлом году Петров Владимир Анатольевич из Волгограда спрашивал
меня, как я придумываю задачи для Кукарачи и Корректора.
   Я ответил, что в день придумывания хожу в баню, хорошо парюсь и
после парилки обильно смазываю голову медом. После этого задачи
вылезают сами собой.
   Это не шутка. В прошедшую пятницу я снова проделал эту процедуру и
уже по дороге из бани домой, вылезли три задачи, которые я с
удовольствием записал. В субботу и воскресенье я записал еще 9 задач.
Так что к предстоящему турниру плацдарм готов.
   Задачи можно разделить на три цикла:
- разминочные (3 задачи);
- лексические анализаторы (4 задачи);
- геометрические задачи (5 задач).
   И как всегда, последнее задание конкурса -- придумать собственную
задачу для Кукарачи.

   Если Вы внимательно проработали решения задач конкурса прошлого
года и статью "Транслятор?.. Это очень просто!", то справиться с
заданиями будет совсем не трудно.

   Задачи и условия конкурса будут опубликованы в конце этой недели.

                        * * *

3115 Потешкина Галина Николаевна (команда 3115) пишет:

>    Меня очень заинтересовала программа Плюсик. Я считаю, что эта
> программа может занять достойное место в разделе изучения алгоритмов,
> как основ программирования.

   Я очень рад такому письму. Дело в том, что в прошлом году было
письмо от одного из учителей, который сомневался в нужности включения
Плюсика в наш курс "Азы программирования". В то время как стековая
обработка относиться к фундаментальным понятиям информатики.

   Табашин Николай Викторович Лукоянов (команда 3112) пишет:

>    Хотелось бы определиться с терминологией и классификацией типов
> рекурсии.
>
>    1. В курсе Роботландии (Роботландия, Ю.А.Первин, А.А.Дуванов, Я.Н.
> Зайдельман, М.А.Гольцман - :Москва, НЦПСО, 1991) рассматривается
> рекурсия в среде исполнителя Кукарача и дается определение: рекурсия
> - это такая ситуация, при которой программа вызывает сама себя. И
> рассматриваются два её вида - рекурсия и косвенная рекурсия.
>
>    2. В главе 6 Роботландского программирования уточняется, что
> рекурсия бывает: бесконечной рекурсией и конечной косвенной
> рекурсией, "литературной" текстовой и "телевизионной" графической
> рекурсией.
>
>    3. В статье : "Транслятор? ...Это очень просто?" (Информатика N42)
> также рассматривается вопрос рекурсии. И упоминается о прямой и
> косвенной рекурсиях.
>
>    На примере замечательных задач Лилитко Е.П. рассматривается новый
> вид рекурсии. Но никак не называется. (Проверено - работает даже на
> компьютере УК-НЦ).
>
>    4. При изучении языка Лого (Уроки информатики на ЛОГО, Ю.А.Первин,
> З.Н.Ермаков - :Москва, НЦПСО, 1991) даётся определение нескольких
> видов рекурсии для исполнителя черепашки.
>
>    Ситуация, в которой обращение к вызываемой процедуре сделано из
> вызываемой, называется косвенной рекурсией.
>
>    Рекурсивный вызов, выполняемый в конце тела процедуры, называют
> терминальным рекурсивным вызовом, или терминальной рекурсией.
> (Спирали Лого )
>    Рекурсивный вызов в начале или в в середине тела процедуры -
> нетерминальным вызовом, или нетерминальной рекурсией. (Деревья - на
> Лого, или процедура ОШИБКА в газете Информатика ?42)
>
>    Хотелось бы уточнить что предполагается под термином -
> терминальная? (Терминал - экран монитора, или что-то ещё)?
>
>    Видимо прямая рекурсия означает одно и тоже, что и терминальная
> рекурсия.
>
>    Тогда рекурсию в задачах предложенных Лилитко Е.П. видимо можно
> называть нетерминальной рекурсией.
>

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


Рекурсия
--------
   В рекурсии нет ничего загадочного. О рекурсии говорилось много.
Кратко об основном.

   В математике и информатике рекурсивной называют такую функцию или
процедуру, которая при своей работе обращается к себе самой, прямо
или косвенно. Соответственно говорят о прямой и косвенной рекурсии.
При прямой рекурсии процедура содержит вызов себя в своем собственном
теле, например:

ЭТО прямая
....
  ЕСЛИ ... ТО прямая
....
КОНЕЦ

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

ЭТО процедура0
....
 ... процедура1
....
КОНЕЦ

ЭТО процедура1
....
 ... процедура2
....
КОНЕЦ

ЭТО процедура2
....
 ... процедура0
....
КОНЕЦ

   В примере цепочка "процедура0--процедура1--процедура2--процедура0"
образует косвенную рекурсию. Процедура0 является рекурсивной, так как
вызывает сама себя. Правда этот вызов не прямой, а косвенный, через
обращение к процедурам "процедура1--процедура2".
   Как уже отмечалось, прямая рекурсия всегда предпочтительнее
косвенной не в смысле эффективности выполнения, а в смысле
наглядности записи. Читателю программы проследить косвенную рекурсию
сложнее. Транслятору языка, конечно, все равно какая рекурсия,
косвенная или прямая.
   Сама по себе косвенная рекурсия не содержит новых идей. Это просто
другая форма записи прямой рекурсии, если, конечно, промежуточные
процедуры не содержат других рекурсий. Поэтому, следует избегать
косвенной рекурсии всюду, где это возможно.
   Примером принципиальности косвенной рекурсии служат программы
лексических анализаторов, приведенные в статье "Транслятор" и в
решениях куратора задач турнира прошлого года. Лексический анализатор
представляет собой сложное переплетение косвенных рекурсивных
вызовов. Однако эта сложность скрадывается предварительным
построением синтаксической диаграммы.
   Когда синтаксическая диаграмма построена, мы формально переводим
ее в программу, даже не задумываясь о том, сколько сложных косвенных
рекурсий мы при этом монтируем в простой с виду программный код.
   Это то самое исключение их правил, когда косвенная рекурсия не
затрудняет понимание алгоритма работы программы. Правда, только
потому, что предварительно построена синтаксическая диаграмма. Вся
сложность перенесена из программы на ее графическую схему.
   Но при построении диаграммы нам приходится думать рекурсивно. Без
этого диаграмму (а значит и программу) не построить.
   Рассмотрим синтаксическую диаграмму из "Транслятора" (третья
часть):


           ПУСТО                0,1,2         остальное
 (ответ) <------ (выражение) <-------- (вход) -----------> (ошибка)
                     |   |               ^                    ^
                     |   | +             |                    |
            остальное|   |               |                    |
                     |   -----------------                    |
                     ------------------------------------------

   На этой схеме изображены 4 процедуры "ответ", "выражение", "вход"
и "ошибка".
   Процедура "ответ" рекурсивной не является
   Процедура "ошибка" на схеме рекурсивной не показана (хотя, как вы
помните, алгоритм ее работы содержит прямую рекурсию с отложенной
командой для перемещения исполнителя к месту обнаруженной ошибки).
   Процедуры "выражение" и "вход" содержат вызов друг друга, значит
образуют цепочку косвенной рекурсии.


   Рассмотрим более сложную синтаксическую диаграмму из того же
"Транслятора" (третья часть):

                                        (ошибка)
                                           ^
                                  остальное|
                                           | ----
                                           | |  | )
                       ------------------| | |  |
                       |                 V | |  V  ПУСТО
                       |                 (скобка))--------> (ответ)
                       |)                  |+,-
                       |                   |
                       |                   |
           ПУСТО       |        цифра      V      остальное
(ответ) <---------- (число) <---------- (  вход  ) -----------> (ошибка)
                     |   |              ^ |   ^
                     |   | +,-          | |   |
            остальное|   |              | |   |
(ошибка) <------------   ---------------  |   |
                                          |(  |
                                          |   |
                                          -----

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

Если косвенную рекурсию
ЭТО А
  ....
  ..Б
  ....
КОНЕЦ
             (*)
ЭТО Б
 А
КОНЕЦ

легко превратить в прямую:
ЭТО А
  ....
  ..А
  ....
КОНЕЦ

   То так сделать со схемой лексического анализатора нельзя!
   Надо всячески избегать косвенных рекурсий типа (*), превращая их в
прямые.

Терминальные и не терминальные рекурсии
---------------------------------------
   Терминал - это оконечное устройство, концевик. В частности,
терминалом называют монитор (часто вместе с клавиатурой) как
оконечное устройство компьютера для диалога с пользователем. Раньше,
когда работали на больших ЭВМ типа ЕС или БЭСМ, терминалы
(монитор+клавиатура) выносили в отдельные залы, где несколько
пользователей одновременно работали на отдельных терминалах с одной
ЭВМ. Иногда, такой терминал имел свой процессор и небольшую память.
Таким образом получалось, что терминал -- это небольшой компьютер.
Но это не мешало быть ему терминалом, так как он работал не
самостоятельно, а служил оконечным устройством другой ЭВМ.

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

   Рассмотрим программу из первой части "Транслятора". Эта программа
реализует первую синтаксическую диаграмму в тексте этого письма.
Вправда в нее добавлены дополнительные процедуры для подсчета баланса
круглых скобок:

ЭТО вход0
 ОБМЕН
 ПИШИ ПУСТО
 ОБМЕН
 вход
КОНЕЦ


ЭТО вход
 ВПРАВО
 ЕСЛИ       0 ТО выражение
 ИНАЧЕ ЕСЛИ 1 ТО добавить1
 ИНАЧЕ ЕСЛИ 2 ТО добавить2
 ИНАЧЕ ошибка
КОНЕЦ

ЭТО выражение
 ВПРАВО
 ЕСЛИ       +     ТО вход
 ИНАЧЕ ЕСЛИ ПУСТО ТО ответ
 ИНАЧЕ ошибка
КОНЕЦ

ЭТО добавить1
 ОБМЕН
 ПЛЮС
 ОБМЕН
 выражение
КОНЕЦ



ЭТО добавить2
 ОБМЕН
 ПЛЮС ПЛЮС
 ОБМЕН
 выражение
КОНЕЦ

ЭТО ошибка
 ВПРАВО
 ЕСЛИ ПУСТО
  ТО ответ_ошибка
  ИНАЧЕ ошибка
 ВЛЕВО
КОНЕЦ

ЭТО ответ_ошибка
 ВПРАВО ПИШИ о
 ВПРАВО ПИШИ ш
 ПОВТОРИ 2 ВЛЕВО
КОНЕЦ


ЭТО ответ
 ВПРАВО ВПРАВО
 ПИШИ 0
 ОБМЕН
 ПОКА НЕ ПУСТО
 {
    МИНУС ОБМЕН
    плюс1
    ПОКА НЕ ПУСТО ВПРАВО
    ВЛЕВО ОБМЕН
 }
 ОБМЕН
 ПОКА НЕ ПУСТО ВЛЕВО
 ПИШИ =
КОНЕЦ

ЭТО плюс1
 ЕСЛИ 9 ТО    девять
        ИНАЧЕ ПЛЮС
КОНЕЦ

ЭТО девять
 ПОКА 9 { ПИШИ 0 ВЛЕВО }
 ЕСЛИ НЕ ЦИФРА
   ТО    ПИШИ 1
   ИНАЧЕ ПЛЮС
КОНЕЦ


   Процедура "вход" содержится в цепочке косвенной рекурсии
(вход)--(выражение)--(вход), Причем тип рекурсии, которая здесь
используется -- терминальная.
   Посмотрите на эти процедуры:

ЭТО вход
 ВПРАВО
 ЕСЛИ       0 ТО выражение
 ИНАЧЕ ЕСЛИ 1 ТО добавить1
 ИНАЧЕ ЕСЛИ 2 ТО добавить2
 ИНАЧЕ ошибка
КОНЕЦ

ЭТО выражение
 ВПРАВО
 ЕСЛИ       +     ТО вход
 ИНАЧЕ ЕСЛИ ПУСТО ТО ответ
 ИНАЧЕ ошибка
КОНЕЦ

   Кажется, что рекурсия не терминальная, но это не так!
   Я же не говорил, что после рекурсивного обращения в терминальной
рекурсии должно стоять ключевое слово "КОНЕЦ"!
   Говорилось, что после терминального вызова, других команд, которые
должны выполняться в процедуре, быть не должно. А здесь это именно
так. Например, в процедуре "вход" косвенная рекурсия обеспечивается
вызовом процедуры "выражение". Этот вызов стоит в условной команде,
после которой идет слово КОНЕЦ. Значит этот вызов терминальный.
 Прошу обратить внимание, что запись

 ЕСЛИ       0 ТО выражение
 ИНАЧЕ ЕСЛИ 1 ТО добавить1
 ИНАЧЕ ЕСЛИ 2 ТО добавить2
 ИНАЧЕ ошибка

является одной условной командой.

В отличие от записи

 ЕСЛИ       0 ТО выражение
 ЕСЛИ 1 ТО добавить1
 ЕСЛИ 2 ТО добавить2
 ИНАЧЕ ошибка

   В последней записи -- три команды и, если бы именно так было
записано в процедуре "вход", то рекурсивный вызов был бы уже не
терминальный, а значит процедура "вход" работала бы совсем по
другому. Она содержала бы две, "отложенные" в рекурсии команды:

 ЕСЛИ 1 ТО добавить1
 ЕСЛИ 2 ТО добавить2
 ИНАЧЕ ошибка

   Типичный пример не терминальной рекурсии содержит процедура
"ошибка":

ЭТО ошибка
 ВПРАВО
 ЕСЛИ ПУСТО
  ТО ответ_ошибка
  ИНАЧЕ ошибка
 ВЛЕВО
КОНЕЦ

   Здесь прямая не терминальная рекурсия. Не терминальная рекурсия
порождает отложенные команды, рекурсивные "пружинки". Как Вы знаете,
такие рекурсии выполняются совсем особым образом.

   Табашин Николай Викторович Лукоянов (команда 3112) пишет:

Почему в решениях записано так:

>
>     Возникает вопрос почему при решении задач из глав 4, 5 и т.д.
>  приводится конструкция переключателя вида:
>
>  ЭТО ЦИФРУ_В_НУЖНУЮ_СТРОКУ
>    ЕСЛИ       3 ТО ЦИФРА_3
>    ИНАЧЕ ЕСЛИ 4 ТО  ЦИФРА_4
>    ИНАЧЕ ЕСЛИ 5 ТО  ЦИФРА_5
>    ИНАЧЕ ЕСЛИ 6 ТО  ЦИФРА_6
>    ИНАЧЕ ЕСЛИ 7 ТО  ЦИФРА_7
>    ИНАЧЕ ЕСЛИ 8 ТО  ЦИФРА_8
>    ИНАЧЕ ЕСЛИ 9 ТО  ЦИФРА_9
>  КОНЕЦ


а не так:

>
>  ЭТО ЦИФРУ_В_НУЖНУЮ_СТРОКУ
>    ЕСЛИ 3 ТО ЦИФРА_3
>    ЕСЛИ 4 ТО ЦИФРА_4
>    ЕСЛИ 5 ТО ЦИФРА_5
>    ЕСЛИ 6 ТО ЦИФРА_6
>    ЕСЛИ 7 ТО ЦИФРА_7
>    ЕСЛИ 8 ТО ЦИФРА_8
>    ЕСЛИ 9 ТО ЦИФРА_9
>  КОНЕЦ


Ведь последняя запись проще!


Мой ответ на этот вопрос был таким:


   Допустим мы хотим увеличить x на 1, если x равен 3 и увеличить на
2, если он равен 4.
   Давайте напишем так:

ЕСЛИ x = 3 ТО x:=x+1       (1)
ЕСЛИ x = 4 ТО x:=x+2

и предположим, что перед вычислениями x равнялся 3.
Чему же он станет равен после работы этих двух команд?
Ведь не четырем, как хотелось, правда? Он станет равным 6.

Если мы запишем:

ЕСЛИ x = 3 ТО x:=x+1       (2)
ИНАЧЕ ЕСЛИ x = 4 ТО x:=x+2

то все будет честно.

   Итак, запись (1) на роль переключателя никак не годится. Она
совсем переключателем не является. И может привести к многочисленным
трудноуловимым ошибкам. Кроме того запись (1), несмотря на свою
простоту, приводит к неэффективным по времени выполнения программам.
В записи (1) все проверки работают _всегда_ не зависимо от значений
переменной. В записи (2) число проверок зависит от значения
переменной и может равняться 1.

   Теперь в дополнению к этому примеру можно сказать, что запись (1)
совсем не эквивалента записи (2) даже для Кукарачи, если в ней есть
рекурсия.
   Ведь в записи (1) рекурсия будет терминальной, а в записи (2) --
нет. Не терминальные рекурсии порождают отложенные команды. А такие
конструкции работают совсем по-другому!

   Наконец, осталось разобраться с конечной и бесконечной рекурсией.
Но здесь уж совсем ничего интересного нет. Как цикл может быть
конечным и бесконечным, так и рекурсия (это ведь тоже повторение!)
может быть бесконечной или нет. Для того чтобы не было бесконечных
повторений (циклических или рекурсивных), нужно устраивать проверки
на окончание.

Бесконечная прямая терминальная рекурсия:

ЭТО поход
 ВПРАВО
 поход
КОНЕЦ

   Кукарача кричит "не могу" на правом краю поля.


Конечная прямая терминальная рекурсия:

ЭТО поиск
  ВПРАВО
  ЕСЛИ ПУСТО ТО ПОИСК
КОНЕЦ

Кукарача толкает кубик с символом и останавливается.

Конечная прямая не терминальная рекурсия:

ЭТО поиск
  ВПРАВО
  ЕСЛИ ПУСТО ТО ПОИСК
  ВЛЕВО
КОНЕЦ

   Кукарача толкает кубик с символом и возвращается на прежнее место.

