Равным образом можно сказать, что информация должна восстанавливаться в порядке, обратном тому, в котором она запоминалась. Это замечание сразу же подсказывает два решения:
а) Поведение информации, которое мы только что выявили, точно совпадает с поведением информации, управляемой в стеке, функциональная специфика которого уточняет, что данные извлекаются из стека в порядке, обратном их засылке в стек. Рекурсия реализуется, таким образом, путем установления соответствия стека указателю выполнения, каждому параметру (в частности, тому, который представляет результат подпрограммы, если он имеет место) и каждой локальной переменной. Запоминание выполняется с помощью операции засылки в стек; восстановление - с помощью выборки из стека. По завершении поколения остается завершить предшествующее поколение в том и только в том случае, когда стек не пуст.
б) Стек, однако, не является необходимым в случае, когда ре¬курсивный вызов заменяет значение параметра или локальную переменную, например A, на новое значение A1 = f(A), такое, что A может быть вновь вычислено в зависимости от A1, т. е. что функция f имеет обратную .В этом случае нет необходимости хранить A в стеке; достаточно применить при рекурсивном вызове присваивание
A:=f(A),
а при соответствующем возврате
A= (A).
Например, в случае с Ханойской башней при каждом рекурсивном вызове n заменяется на n - 1. Поэтому отпадает надобность связывать стек с n: достаточно, чтобы каждому рекурсивному вызову предшествовало
n:=n — 1
и чтобы при каждом рекурсивном возврате выполнялось обратное присваивание
n:=n + 1
Однако при этом способе возникает проблема, так как, кроме операций «сохранение» и «восстановление», нам нужно дать средство проверки, пуст ли «стек», т.е. существует ли предшествующее поколение у рассматриваемого. Здесь, например, n будет соответствовать поколению, которое является предком всех других в том и только в том случае, когда n = , где есть начальное значение n при первом вызове Ханоя. Следует, таким образом, сначала запомнить.
В общем случае функция f, вязанная с параметром, не обяза¬тельно является той же самой для всех рекурсивных вызовов, связанных с этим же поколением; при возврате, однако, анализ указа¬теля выполнения позволяет найти функцию, обратную к примененной. Таким образом, для Ханойской башни констатируем, что три последних параметра рекурсивного вызова строки (2), [A,C,B] выводятся из [A,B,C] путем перестановки B и C, а параметры рекурсивного вызова строки (4), [C,B,A] выводятся из [A,B,C] путем перестановки A и C. Тогда для операции
переставить (а,b)
обратной операцией является она сама, поскольку
переставить (а,b), переставить (а,b)
равноценно пустому действию (конкретно переставить (а,b) можно записать:
C:=A, A:=B, B:=C)
К тому же нет необходимости связывать стеки с параметрами A,B,C: просто перед каждым вызовом строки (2) ставится:
переставить (B,C)
а перед каждым вызовом строки (4)
переставить (A,B)
При рекуррентном возврате анализ указателя выполнения, взятого из стека, позволит установить, какая из операций
переставить (B,C)
или
переставить (A,C)
является обратной по отношению к применяемой.
Поступайте к нам!
Уважаемые абитуриенты! Мы рады приветствовать Вас на нашем сайте и сегодня сообщаем Вам о том, что Вы всё ещё можете подавать заявления и поступать в ВФ МГИУ. Напоминаем, что на некоторые специальности Вы можете поступить по результатам ЕГЭ. Помните, у нас Вы сможете получить прекрасное образование по следующим направлениям: "Прикладная информатика в экономике", "Бухгалтерский учёт, анализ и аудит", Автомобиле- и тракторостроение", "Менеджмент организации"!
