                      Рекурсия другим манером

Дуванов Александр Александрович
kurs@robotland.users.botik.ru
декабрь, 1999 Переславль-Залесский


   Автор статьи "Транслятор?.. Это очень просто!" получил письмо. Та-
башин Николай Викторович из города Лукоянова пишет:

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

   Вопрос мне  показался  интересным,  и я  предлагаю ответ читателям
"Транслятора".


Прямая и косвенная рекурсия
- - - - - - - - - - - - - -

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

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

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

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

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

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

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


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

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

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

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

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

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

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

   То в схеме лексического анализатора так сделать нельзя!

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

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

   Посмотрите на процедуры:

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

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

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

 Прошу обратить внимание, что запись:

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

   является одной условной командой в отличие от записи:

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

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

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

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

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

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

Отступление о переключателях
- - - - - - - - - - - - - -

Почему нужно писать так:

ЭТО ЦИФРУ_В_НУЖНУЮ_СТРОКУ
  ЕСЛИ       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, если он равен 3, и на 2, если
x равен 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) --
нет. Нетерминальные  рекурсии  порождают  отложенные команды. А такие
конструкции работают совсем по-другому!


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

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

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

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


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

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

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

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

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

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