Вернемся назад, к общим проблемам рекурсии.
Мы уже видели, что некоторые рекурсивные алгоритмы –
Фактически, нетрудно заменить любой цикл рекурсией. Рассмотрим произвольный цикл, данный здесь без указания инвариантов и варианта (хотя позже мы познакомимся с рекурсивными двойниками):
from Init until Exit loop Body end
Мы можем заменить его на
Init
loop_equiv
Здесь введена процедура:
loop_equiv
— Используется условие выхода Exit и тело цикла Body.
do
if not Exit then
Body
Loop_equiv
end
end
В функциональных языках (таких как Lisp, Scheme, Haskell, ML) рекурсивный стиль является предпочитаемым, даже если доступны циклы. Мы могли бы также использовать рекурсию с первых шагов нашего курса, рассмотрев, например, анимацию линии метро, перемещающую красную точку, как рекурсивную процедуру:
Line8.start
animate_rest (Line8)
Вот как могла бы выглядеть сама процедура:
animate_rest (line: LINE)
— Анимация станций линии метро, начиная от текущей позиции курсора
do
if not line.after then
show_spot (line.item.location)
line.forth
animate_rest (line)
end
end
(более полная версия должна восстанавливать текущую позицию курсора).
Рекурсивная версия выглядит элегантно, но нет особых причин в рамках нашего курса предпочитать ее форме с применением циклов, мы и в дальнейшем будем использовать циклы.
Но даже чисто теоретически важно понимать, что циклы не являются обязательной принадлежностью языка программирования и могут быть заменены рекурсией. Хорошим примером является программа paradox, демонстрирующая неразрешимость проблемы остановки. Рекурсия позволяет задать более выразительную версию:
recursive_paradox
— Завершается, если и только если не завершается.
do
if terminates ("C:\your_project") then
recursive_paradox
end
end
Знание того, что всякий цикл может быть заменен рекурсией, немедленно порождает вопрос, а верно ли обратное – можно ли рекурсивную процедуру заменить процедурой, использующей циклы?
С примерами замены мы уже встречались – те же has и put для бинарных деревьев. Другие рекурсивные процедуры – hanoi, height, print_all – не имели свободного от рекурсии эквивалента. Для понимания того, что точно может быть сделано, необходимо более глубоко познакомиться со свойствами и смыслом рекурсивных программ.
Приобретенный опыт построения рекурсивных программ позволяет нам более глубоко исследовать смысл рекурсивных определений.
Прежде всего, вернемся назад и зададим весьма невежливый вопрос: а не является ли рекурсия "голым королем"? Другими словами, стоит ли что-либо за рекурсивным определением? Примеры, особенно примеры рекурсивных программ, свидетельствуют в их пользу, но некоторая доля сомнений все же остается. Мы все же находимся в опасной близости к определениям, не имеющим смысла, – к каким-то неправильным циклам. Рекурсия позволяет определять понятие в терминах самого понятия. Но, когда говорится:
Информатика занимается изучением информатики
то это общее место,
Информатика занимается изучением программирования, структур данных, алгоритмов, приложений, теоретическими вопросами и другими областями информатики
В определение добавлены полезные элементы, но оно все еще не является удовлетворительным определением. Подобным образом могут оказаться бесполезными и рекурсивные программы, такие как эта:
p (x: INTEGER)
— Что в этом хорошего?
do p (x) end
Эта программа выполняется для любых целочисленных аргументов, не производя никакого результата, работая бесконечно долго.
Как избежать такого очевидного ошибочного использования рекурсии? Если попытаться понять, почему рекурсивные определения, с которыми мы сталкивались, кажутся интуитивно имеющими смысл, то можно выделить три интересных свойства.
Полезное рекурсивное определение должно удовлетворять следующим требованиям:
| R1 | должна присутствовать хотя бы одна нерекурсивная ветвь; |
| R2 | каждый вызов рекурсивной ветви должен иметь контекст, отличающийся от контекста, в котором эта ветвь была вызвана; |
| R3 | для каждой рекурсивной ветви изменение контекста (R2) приближает к одному из нерекурсивных случаев (R1). |
Для рекурсивных программ изменение контекста (R2) может заключаться в том, что вызов использует различное значение аргумента, как в вызове r(n -1) в программе r(n:INTEGER). Этот вызов применим к различным целям – x.r(n), где x не является текущим объектом. Изменение контекста может также означать, что вызов встречается после того, как программа изменила по меньшей мере одно поле по меньшей мере одного объекта.
Все рекурсивные программы, рассмотренные нами ранее, удовлетворяют этим требованиям.
Hanoi(n, …) включает условный оператор if n > 0 then … end, где все рекурсивные вызовы сосредоточены в then-ветви оператора, но поскольку else-ветвь отсутствует, то эта "пустая" ветвь при n = 0 определяет нерекурсивный вариант (R1). Рекурсивные вызовы имеют форму Hanoi(n - 1, …), изменяя первый аргумент и порядок других аргументов (R2). Замена n на n – 1 приближает контекст к нерекурсивному случаю n = 0 (R3).x = item, для x < item, если нет x > item, если нет правого поддерева (R1). Рекурсивные вызовы имеют другую цель – left или right, отличающуюся от текущего объекта (R2). Каждый такой вызов приближается к height.animate_rest – рекурсивной версии обхода линии метро, – когда курсор находится в положении after, срабатывает нерекурсивная ветвь (R1), ничего не делающая. Рекурсивные вызовы не изменяют аргумент, но в процессе работы вызывается метод line.forth, изменяющий состояние линии (R2); при этом курсор передвигается ближе к состоянию after, где рекурсия заканчивается (R3).Для рекурсивных понятий, не связанных с программами, условия R1, R2, R3 также должны выполняться.
STOP, являются рекурсивными благодаря ссылкам, которые могут иметь значение void. В void служат в качестве Каждая рекурсивная программа должна быть объявлена с ассоциированным с рекурсией вариантом, целочисленной величиной, связанной с каждым вызовом, такой, что:
v для варианта, то значение варианта v1 для любого рекурсивного вызова удовлетворяет условию 0 <= v1 < v.Вариант может включать аргументы
Hanoi(n, …) вариантом является n.has, height, print_all и других node_height – наибольшая длина пути от текущего узла до одного из animate_rest вариантом является, как и для соответствующего цикла, Line8.count – Line8.index +1.Специального синтаксиса для вариантов Hanoi(n, …):
— variant n
Хорошо определенные правила кажутся настолько разумными, что мы можем думать, что они являются не только достаточными, но и необходимыми правилами, чтобы рекурсивное определение имело смысл. Это и в самом деле справедливо для первых двух правил.
| R1 | Если все ветви определения являются рекурсивными, то невозможно выработать какой-либо экземпляр, который не был бы уже известен. В случае рекурсивных программ такое определение приводит к бесконечным вычислениям, на практике аварийно заканчивающимся из-за переполнения памяти. |
| R2 | Если рекурсивная ветвь применяется к оригинальному контексту, то она не может выработать экземпляр, который не был бы уже известен. Для рекурсивной программы (например, p(x: T) с ветвью, которая вызывает p(x) для того же x, что и в начальном вызове, и где ничего не менялось), это приводит опять-таки к зацикливанию вычислений. Если речь не идет о программах и вычислениях, то такая ветвь бесполезна. |
Другая ситуация – с правилом R3, где правило требует существования варианта у рекурсии, такого как аргумент n у Hanoi. Некоторые рекурсивные программы, которые завершаются, нарушают это свойство. Приведу два примера. Они не имеют практических применений, но высвечивают общие свойства, которые следует знать.
Функция 91 Маккарти была спроектирована Джоном Маккарти, профессором университета в Стэнфорде, создателем языка
mc_carthy (n: INTEGER): INTEGER
— Функция 91 Маккарти.
do
if n > 100 then
Result := n – 10
else
Result := mc_carthy (mc_carthy (n + 11))
end
end
Для целых n, больших 100, она возвращает значение n – 10. Это понятно. Значительно менее понятно из-за двойного рекурсивного вызова, какое же значение вернет функция для n, меньших 100, в том числе и для отрицательных значений, и вообще – закончатся ли вычисления. Оказывается, что во всех случаях, когда n меньше 100, функция завершает работу и возвращает значение 91, из-за чего функция и получила такое имя. Но очевидного варианта здесь нет, и внутренний n.
Вот еще один пример знаменитой программы и знаменитой проблемы, не получившей решения до настоящего момента:
bizarre (n: INTEGER): INTEGER
— Функция, всегда возвращающая 1 для n нечетного и большего 1.
require
positive: n >= 1
do
if n = 1 then
Result := 1
elseif even (n) then
Result := bizarre (n // 2)
else — для нечетных n, больших 1
Result := bizarre ((3*n + 1) // 2)
end
end
Здесь используются операция // – деление нацело, и even(n), истинное для четных n. Два вхождения этой операции дают точное значение, поскольку применяются к четным числам. Понятно, что если функция возвращает результат, то он может быть только 1, производимой единственной нерекурсивной ветвью. Но завершается ли эта программа для любых n? Ответ кажется очевидным: "да" (можно написать программу и проверить ее на возможном диапазоне чисел. Доказана ее завершаемость на очень больших числах, но общего решения пока нет). Явного варианта рекурсии здесь нет, и видно, что в одной из ветвей рекурсивного вызова аргумент (3*n +1)//2 больше, чем n.
Эти интересные примеры являются экзотикой, но необходимо принимать в расчет их существование для общего понимания рекурсии. Они означают, что существуют некоторые рекурсивные определения, которые не удовлетворяют, казалось бы, разумным методологическим правилам, обсужденным выше, и все же вырабатывают хорошо определенные результаты.
Заметьте, что такие примеры, завершающиеся для каждого возможного аргумента, должны иметь вариант, так как для любого выполнения число рекурсивных вызовов определено и конечно, и следовательно, определяется состоянием программы во время вычисления, так что оно является функцией состояния, которая и может служить вариантом. Беда в том, что эта функция неизвестна, мы не можем ее выразить, а раз так, то ее теоретическое существование мало что дает практике.
На практике мы такие примеры оставляем без внимания и ограничиваем себя рекурсивными определениями, которые обладают всеми тремя свойствами – R1, R2, R3. В частности, когда вы пишете рекурсивную программу, следует всегда, как в оставшихся примерах этой лекции, явно задавать вариант в рекурсии.
Даже с хорошо определенными правилами и наличием варианта у рекурсии мы все же не можем спать спокойно, используя рекурсию. Проблема в том, что рекурсивное определение не является определением в обычном смысле, поскольку оно может быть креативным – творческим.
Аксиома в математике является креативной: она говорит нам нечто такое, что не может быть выведено из известных уже фактов. Примером является аксиома о целых в математике, которая говорит, что для числа n', следующего за n, справедливо n < n'. Фундаментальные законы в естественных науках также креативны, например, закон, утверждающий о невозможности двигаться со скоростью, превышающей скорость света.
Теоремы в математике, так же как и аналогичные результаты в физике, с рассматриваемой точки зрения "творческими" не являются, поскольку могут быть выведены из аксиом и известных уже законов. Они интересны сами по себе и позволяют нам более просто выводить новые утверждения, но они не добавляют новых предположений, являясь следствиями уже сделанных ранее.
Определение, так же как и теорема, не должно быть творческим. Определение дает новое имя объекту нашего мира, но все утверждения, которые можно выразить с использованием определения, могут быть сделаны и без помощи этого определения. Мы хотим более просто выражать утверждения, используя введенное определение, а иначе зачем бы понадобилось его вводить. Но мы знаем, что можно обойтись и без определения. Пусть сказано:
$$\text{Определим }x^2\text{ для любого x, как x * x}$$Ничего нового такое определение в математику не добавляет: просто разрешается использовать новую нотацию для умножения. Любое свойство, которое может быть доказано с использование новой нотации, может быть доказано и без нее, по сути, заменой $$x^2$$ в соответствии с определением.
Символ $$\triangleq$$, который мы использовали для обозначения "определено как" (начиная с
Здесь some_expression включает f. Теперь наш принцип больше не выполняется! Всякая попытка заменить f в определении some_expression на some_expression не устраняет f, так что реально мы ничего не определили. До тех пор, пока мы не найдем удобного, некреативного смысла для определений, подобных формуле (5.1), мы должны быть терминологически аккуратны. По этой причине символ $$\triangleq$$ будет использоваться только для нерекурсивных определений, а такое свойство, как (5.1), будет задаваться равенством
Это равенство можно рассматривать как уравнение, решением которого выступает f. Говоря о рекурсивных "определениях", для корректности будем заключать второе слово в кавычки.
Изолировав пока рекурсию и поместив ее в карантинную зону, полезно посмотреть на рекурсивные программы и рекурсивные "определения" в целом с позиции "снизу вверх". Я надеюсь, что это удалит легкое головокружение, которое остается, когда видишь определения программ, которые – частично – сами себя вызывают.
Рекурсивные "определения" пишутся "сверху вниз", определяя смысл понятия в терминах того же понятия для "меньшего" контекста – меньшего с точки зрения варианта рекурсии. Например, Fibonacci для n выражается через Fibonacci для n – 1 и n – 2.
Взгляд "снизу-вверх" предоставляет другую интерпретацию того же определения, трактуя это другим способом, как механизм, который создает новое значение на основе уже существующих. Начнем с рассмотрения функции. Для любой функции f можно построить граф этой функции как множество пар [x, f(x)] для каждого применимого x. Граф для функции Fibonacci задается множеством
Он содержит все пары [n, Fibonacci(n)] для всех неотрицательных n. Этот граф содержит всю информацию о функции. Визуально этот граф можно представить в следующей форме:
(рис 9.1) Граф функции (Фибоначчи)
В верхней строчке показаны возможные аргументы функции, в нижней – соответствующие значения функции.
Дать функции рекурсивное определение – это все равно, что сказать, что ее граф F – как множество пар – удовлетворяет некоторому свойству
Здесь h рассматривается как некоторая функция, применимая к такому множеству пар. Это подобно уравнению, которому F должна удовлетворять, и известному как уравнение неподвижной точки. Неподвижной точкой – решением такого уравнения – является некоторый математический объект, в данном случае функция, который остается инвариантом при некоторых трансформациях, в данном случае – задаваемых функцией h.
Определим рекурсивно функцию Fibonacci:
$$fib (0) = 0\\fib (1) = 1\\fib (i) = fib (i – 1) + fib (i – 2)\qquad \text{— Для }i >1$$Такое определение эквивалентно тому, что граф F, рассматриваемый как множество пар, удовлетворяет уравнению неподвижной точки (5.4), где h – это функция, которая, получив множество пар, вырабатывает новое множество, содержащее следующие пары:
| G1 | каждую пару, уже содержащуюся в F |
| G2 [0, 0] | — Пару для n = 0: [0, |
| G3 [1, 1] | — Пару для n = 1: [1, |
| G4 | каждую пару в форме [i, a + b)] для некоторого i, такого, что F содержит пары [i-1, a] и [i-2, b] |
Мы можем использовать эту точку зрения, чтобы дать рекурсивному "определению" точный смысл, свободный от всякой рекурсивной загадочности. Мы начинаем с графа $$F_0$$, который пуст (не содержит пар). Далее мы определяем
$$F_1\triangleq h(F_0)$$Оно имеет смысл и означает, что $$F_1$$ задается множеством {[0, 0], [1, 1]} – парами, определяемыми правилами G2 и G3. Правила G1 и G4 в данном случае неприменимы, так как $$F_0$$ пусто. Затем мы снова применяем $$h$$, чтобы получить
$$F_2\triangleq h(F_1)$$Здесь G2 и G3 нам не дают ничего нового, так как пары [0, 0] и [1, 1] уже присутствуют в $$F_1$$, но G4 создает новую пару из существующих – [2, 1]. Продолжая, мы определяем последовательность графов, начиная с $$F_0$$ и определяя $$F_i = h(F_{i – 1})$$. Теперь рассмотрим $$F$$ как бесконечное объединение:
$$\bigcup\limits_{i\in N}F_i$$Здесь $$N$$ – это множество натуральных чисел. Достаточно просто видеть, что $$F$$ удовлетворяет свойству (5.4).
Такова нерекурсивная интерпретация – семантика, – которую мы дали рекурсивному "определению" функции Fibonacci.
В общем случае уравнение неподвижной точки в форме (5.4) на графах функции, устанавливающее эквивалентность $$F$$ и $$h(F)$$, представляет решение в виде графа функции
$$F\triangleq\bigcup\limits_{i\in N}F_i$$Здесь $$F_i$$ – это последовательность графов функции:
$$F_0\triangleq \{ \}\qquad\qquad\text{ — Пустое множество пар}\\F_i\triangleq h(F_{i-1})\qquad\text{ — Для }i > 0$$Подход, основанный на неподвижной точке, является базисом интерпретации "снизу вверх" рекурсивных вычислений. Он частично удаляет загадочность из этих определений, поскольку рассматривает рекурсивное определение как уравнение неподвижной точки и допускает решение, полученное как результат объединения (подобно пределу последовательности в математическом анализе) последовательности графов функции.
Данный подход редуцирует рекурсивное "определение" к хорошо известному, традиционному понятию индуктивного определения последовательности.
Функция Фибоначчи является хорошим примером для понимания концепции, но, вероятно, она не поражает впечатления. Во всех учебниках по математике она определяется индуктивно как последовательность чисел. Это в компьютерном мире мы рассматриваем ее как рекурсивную функцию. Так что мы не узнали ничего нового о самой функции, а просто познакомились с разными точками зрения. Давайте посмотрим, можно ли научиться чему-нибудь на других примерах.
Понимая природу "снизу вверх", можно дать ясное понимание смысла рекурсивного определения понятия "тип". Как вы помните, тип определяется следующим образом:
| T1 | базисный класс, такой как INTEGER или STATION; |
| T2 | родовое порождение в форме C [T], где C является T – это тип. |
Правило T1 определяет нерекурсивный случай. Взгляд "снизу вверх" позволяет нам понимать данное определение как построение множества типов в виде последовательности слоев. Ограничившись для простоты одним родовым параметром, имеем:
INTEGER, STATION и т.д.;C [X], где C универсальный класс, а X принадлежит уровню L0: LIST [INTEGER], ARRAY [STATION] и т.д.;n > 0 имеет все типы в форме C [X], где X принадлежит уровню Li для i < n.Таким образом, мы получаем все типы – базисные и полученные в результате родового порождения.
Взглянем теперь "снизу вверх" на Ханойские башни. Программу можно рассматривать как рекурсивное определение последовательности ходов. Давайте обозначим такую последовательность как $$<A\to B,\; C\to A, …>$$, означающую, что первым ходом переносится диск с вершины стержня А на B, затем с C на A и так далее. Пустая последовательность будет $$<>$$, а конкатенация последовательностей задается знаком "+", так что
$$<A\to B,\; C\to A> + <B\to A>\text{ дает }<A\to B,\; C\to A,\; B\to A>.$$Тогда мы можем выразить рекурсивное решение как функцию
Функция определена, если $$n$$ положительно и значения $$s$$, $$t$$, $$o$$ (сокращения для source, target, other) различны – мы используем их, как и ранее, для обозначения стержней 'A', 'B', 'C'. Конструирование функции, решающей уравнение, просто: (5.5) позволяет инициализировать граф функции для $$n = 0$$ в следующей форме:
Обозначим через $$H_0$$ эту первую часть графа, содержащую 6 пар, которые включают все возможные перестановки стержней. После этого можно использовать (5.6) для получения множества пар $$H_1$$, содержащего значения для $$n = 1$$, где пары имеют вид:
$$[(1, s, t, o), <s\to t>]$$Здесь учитывается, что конкатенация $$< > + x$$ или $$x + < >$$ дает $$x$$. Следующая итерация (5.6) даст нам $$H_2$$, чьи пары имеют вид:
$$[(2, s, t, o), fl + <s\to t> + gl]$$Это верно для всех $$s, t, o$$ таких, что $$H_1$$ содержит как пару $$[(1, s, o, t), f1]$$, так и пару $$[(1, o, t, s), g1]$$.
Последующее итерирование позволит построить граф $$H_3$$. Полный граф – разумеется, бесконечный, поскольку включает пары для всех возможных $$n$$, – задает множество всех пар во всех элементах последовательности:
$$\bigcup\limits_{i\in N}H_i$$Теперь я смею надеяться, что вы получили достаточное представление о подходе "снизу вверх" к
Напишите программу (не используя рекурсии), создающую последовательно элементы множеств $$H_0, H_1, H_2 \ldots$$ для Hanoi.
Связанное с этой задачей упражнение попросит вас определить (без программирования) математические свойства графа.
Еще одно важное упражнение потребует применить подобный анализ к обходу бинарного дерева. Вы должны будете спроектировать модель для представления решения, подобную той, что использована в данной задаче, – вместо последовательности ходов должна появиться последовательность узлов.
Подход "снизу вверх", в частности, применим и для рекурсивных грамматик, как в нашем небольшом примере:
$$Instruction\triangleq ast\;\; |\;\; Conditional\\Conditional\triangleq ifc\;\; Instruction\;\; end$$Здесь введены сокращения: ifc представляет "if Condition then" и ast представляет "Assignment", оба рассматриваются как терминалы в данном обсуждении.
Достаточно просто видеть, как генерировать последовательные предложения языка, интерпретируя создаваемые продукции в стиле неподвижной точки:
$$ast\\ifc\;\;ast\;\;end\\ifc\;\;ifc\;\;ast\;\;end\;\;end\\ifc\;\;ifc\;\;ifc\;\;ast\;\;end\;\;end\;\;end$$С этих же позиций может быть проанализировано предыдущее обсуждение небольшого языка Game.
Данный подход обобщается на произвольные грамматики, рассматривая матричное представление описания
Мы уже научились поставлять наши классы и их методы с контрактами, устанавливающими их корректность: предусловия и постусловия методов, инварианты класса. Те же подходы, применяемые к алгоритмам, приводят к заданию вариантов и
Мы уже познакомились с понятием варианта для рекурсии. Если метод рекурсивен непосредственно или косвенно, то следует включать вариант для рекурсии в его описание. Как отмечалось, специальный синтаксис для этих целей отсутствует, так что приходится добавлять отдельное предложение в заголовочный комментарий метода:
— variant: expression
Вот пример процедуры Hanoi с более полными контрактами, новыми предложениями, записанными в виде комментариев:
hanoi (n: INTEGER; source, target, other: CHARACTER)
—Перенос n дисков из source на target,используя other
—в соответствии с правилами игры Ханойская Башня
— invariant: диски на каждом стержне образуют пирамиду,
— следуя в порядке уменьшения размеров.
— variant: n
require
non_negative: n >= 0
different1: source /= target
different2: target /= other
different3: source /= other
— source имеет n дисков; target и other пусты – без дисков
do
if n > 0 then
hanoi (n–1, source, other, target)
move (source, target)
hanoi (n–1, other, target, source)
end
ensure
— Диски, ранее находившиеся на source, теперь перенесены на target,
— сохраняя прежний порядок,
— other находится в исходном состоянии.
end
—invariant: текст комментария
Предлагаемая конструкция не является частью языка, но подчиняется следующим соглашениям.
Рекурсивное программирование хорошо работает в некоторых проблемных областях, что проиллюстрировано примерами этой лекции. Когда рекурсия облегчает вашу работу, нужно применять ее, не раздумывая, так как в современных языках программирования рекурсия считается само собой разумеющейся.
Обычно на уровне машинного кода отсутствует прямая поддержка рекурсии. Компиляторы для языков высокого уровня должны отображать рекурсивно выраженный алгоритм в нерекурсивный. Применяемая при этом техника, несомненно, важна для разработчиков компиляторов, но и для вас, даже если вы и не собираетесь написать компилятор, полезно познакомиться с базисными идеями, как для лучшего понимания рекурсии, так и для осознания потенциальных проблем производительности, связанных с реализацией рекурсии.
Мы рассмотрим некоторые рекурсивные схемы и спросим себя, как, если язык не допускает рекурсию, можно было бы спроектировать нерекурсивную версию, называемую также итеративной, доставляющую те же результаты.
Рассмотрим рекурсивную процедуру r, содержащую собственный вызов:
r (x: T)
do
code_before
r (y)
code_after
end
Здесь могло бы быть несколько рекурсивных вызовов, но мы пока рассматриваем только один. Что это означает, если вернуться к взгляду "сверху вниз"?
Наличие рекурсии влечет, что ни начало кода метода, ни его конец не являются тем, на что они претендуют (быть началом и концом).
code_before, то это вовсе не означает, что выполнение инициировано вызовом метода клиентом a.r(y) или неквалифицированным вызовом r.(y), – это может быть результатом работы экземпляра r, вызывающего себя рекурсивно.code_after завершается, это вовсе не означает завершение истории r: это может быть просто завершение одного рекурсивно вызванного экземпляра. В этом случае следует подвести итоги выполнения последнего вызванного экземпляра r и продолжить выполнение предыдущего экземпляра.Ключевой новинкой последнего наблюдения является понятие экземпляра (называемого также активацией) программы. Мы знаем, что классы имеют экземпляры – "объекты", создаваемые при выполнении ОО-программы. Теперь подобным образом начнем рассматривать и методы класса.
В любой момент выполнения программы состояние вычислений характеризуется цепочкой вызовов, как показано на рисунке. Корневая процедура p вызывает q, которая, в свою очередь, вызывает r… Когда выполнение программы в цепочке завершается, скажем, r, отложенное выполнение вызывающей программы, здесь q, подводит итоги и продолжается с той точки, где оно было прервано при вызове r.
(рис 9.2) Цепочка вызовов без рекурсии
В отсутствие рекурсии не было особой необходимости явного введения понятия экземпляра метода, так как во время выполнения существовал только один активный экземпляр. При рекурсии цепочка вызовов может включать два или более экземпляров одного и того же метода. При прямой рекурсии они будут следовать друг за другом:
(рис 9.3) Цепочка вызовов при прямой рекурсии
Например, вызов hanoi(2, s, t, o) непосредственно запустит вызов hanoi(1, s, o, t), который вызовет hanoi(0, s, t, o). В этом состоянии будем иметь три экземпляра процедуры в цепочке вызовов.
Подобная ситуация существует и при
(рис 9.4) Цепочка вызовов при косвенной рекурсии
Все экземпляры метода разделяют его код. Экземпляры различаются не кодом, а контекстом выполнения. Мы уже обращали внимание на то, что для правильно построенных
При изучении того, как стеки поддерживают выполнение программ в современных языках программирования, мы познакомились со структурой данных, представляющей контекст выполнения метода и называемой записью активации.
При рекурсии каждой активации нужен собственный контекст. Так что остаются только две возможности реализации.
| I1 | Мы можем обратиться к динамическому распределению. Всякий раз, когда стартует очередной экземпляр |
| I2 | В целях экономии памяти можно заметить, что не всегда требуется создавать собственную запись активации, – как обычно, вместо сохранения данных можно перейти к их повторному вычислению. Такое возможно, если преобразование контекста обратимо, и разумно, если потери времени менее значимы, чем дополнительная память на хранение контекста. hanoi(n, …) имеет вид hanoi(n-1, …). Вместо того, чтобы хранить n в активационной записи, сохранять значение n - 1 в новой записи, можно, как при статическом распределении, в самом начале отвести память для хранения n. При вызове нового экземпляра значение n уменьшается на 1, а при завершении увеличивается на 1. |
Два подхода не являются исключающими друг друга. Можно использовать подход I2 для элементов контекста, допускающих простую трансформацию, как с аргументом n в методе hanoi(n, …), и создавать запись активации для остальных элементов контекста. Как всегда, решение принимается на основе компромисса "память или время".
Из двух рассмотренных стратегий управления контекстом рассмотрим вначале первую, основанную на явных записях активации.
Подобно записям активации, динамически создаются и объекты в результате выполнения оператора create.
(рис 9.5) Цепочка вызовов и соответствующий стек записей активации
Такая стратегия работы соответствует уже хорошо известной стратегии LIFO "последний пришел – первый ушел", для реализации которой применяется структура данных – стек. Стек записей активации задает цепочку вызовов, что показано на следующем рисунке.
Мы уже ранее встречались со стеком записей активации – он назывался стеком вызовов, сохраняющим историю вызовов методов во время выполнения. Если вы программируете на языке, поддерживающем рекурсию, то создание стека вызовов выполняется компилятором. Сейчас же мы посмотрим, как это можно сделать самому.
Вам может понадобиться явный стек записей активации, если по каким-либо причинам вы захотите написать итеративный вариант
Заметьте, обе трансляционные схемы вызова и возврата требуют оператора goto для перехода в нужную точку кода. Это прекрасно при работе с машинным кодом, но при работе с языком высокого уровня такого перехода стараются избежать, и в языке goto просто нет. В этом случае приходится временно написать имитацию goto и промоделировать его подходящими структурными средствами.
Давайте посмотрим, как эта схема работает для тела процедуры hanoi с ее двумя рекурсивными вызовами. Будем использовать стек записей активации, называемый просто stack:
stack: STACK [RECORD]
Вспомогательный класс RECORD задает запись активации:
note
description: "Данные, связанные с экземпляром метода"
class RECORD create
make
feature — Инициализация полей
make (n: INTEGER; c: INTEGER; s, t, o: CHARACTER)
— Инициализация полей записи: count, call, source, target, other.
do
count := n ; call := c; source := s ; target := t ; other := o
end
feature — Access
count: INTEGER.
— Число дисков.
call: INTEGER
— Идентифицирует рекурсивный вызов: 1 – первый вызов, 2 – второй.
source, target, other: CHARACTER
— Стержни.
end
(вместо полноценного класса можно было бы использовать кортеж). Экземпляр класса представляет контекст вызова: число перемещаемых дисков (count), три стержня в порядке их использования в вызове, и call, задающее, первый или второй
hanoi (n: INTEGER; source, target, other: CHARACTER)
do
if n > 0 then
hanoi (n–1, source, other, target) — Первый вызов
move (source, target)
hanoi (n–1, other, target, source) — Второй вызов
end
end
Мы задействуем стек записей активации для реализации нерекурсивной версии процедуры, временно использующей goto:
iterative_hanoi (n: INTEGER; source, target, other: CHARACTER)
local — Нам необходимы локальные переменные, представляющие аргументы
— последовательных вызовов:
count: INTEGER
x, y, z, t: CHARACTER
call: INTEGER
top: RECORD
do — Инициализация локальных переменных:
count := n; x := source; y := target; z := other
start: if count > 0 then
— Трансляция hanoi (n–1, source, other, target):
stack.put (create {RECORD}. make (count, 1, x, y, z))
count := count – 1
t := y ; y := z ; z := t
goto start
after_1: move(x, y )
— Трансляция hanoi (n–1, other, target, source):
stack.put (create{RECORD}.make(count, 2, x, y, z))
count := count – 1
t := x ; x := z ; z := t
goto start
end
— Трансляция возврата:
after_2: if not stack.is_empty then
top := stack.item – Вершина стека
count := top.count
x := top.source ; y := top.target ; z := top.other
call := top.call ; stack.remove
if call = 2 then
goto after_2
else
goto after_1
end
end
— Отсутствует предложение else: программа завершается тогда и
— только тогда, когда стек пуст.
end
Тело процедуры iterative_hanoi получено из рекурсивной процедуры hanoi систематическим применением техники исключения рекурсии.
| D1 | Для каждого аргумента вводится локальная переменная. В примере используется простое соглашение о наименовании стержней: x для source и так далее. |
| D2 | Соответствующей локальной переменной присваивается значение аргумента. Дальнейшая работа выполняется над локальной переменной. Это необходимо, поскольку процедура не может изменять значения аргументов (n:= new_value; – некорректно). |
| D3 | Задать метку (здесь start) первому оператору исходного текста процедуры (после инициализации локальных переменных, добавленной в пункте D2). |
| D4 | Ввести еще одну локальную переменную, здесь call, со значениями, идентифицирующими различные рекурсивные вызовы в теле. Здесь есть два рекурсивных вызова, так что call имеет два возможных значения, произвольным образом заданные как 1 и 2. |
| D5 | Добавить метки, здесь after_1 и after_2, к операторам, непосредственно следующим за каждым рекурсивным вызовом. |
| D6 | Заменить каждый n на n -1 и выполняет обмен значений other и target; |
| D7 | В конце процедуры добавляются операторы, которые завершают выполнение процедуры, только когда стек пуст, а в противном случае:
call;call. |
Эта общая схема применима к исключению рекурсии в любой рекурсивной программе, выполняемой как самим программистом в собственных целях, так и разработчиками трансляторов.
Мы теперь рассмотрим возможность ее упрощения, включая удаление goto. Нам понадобится более глубокое понимание структуры программы. В то же время убедитесь, что вы хорошо понимаете этот "грубый" вариант исключения рекурсии.
(рис 9.6) Питер Наур и Джим Хорнинг (2006)
Летом 1961 года я пригласил прочитать лекцию в Лос-Анджелесе малоизвестного ученого из Дании. Его звали Питер Наур, и темой его лекции был новый язык программирования Алгол 60. Когда пришло время вопросов, мужчина, сидевший рядом со мной, встал и сказал: "Мне кажется, что в ваших слайдах есть ошибка".
Питер был озадачен: "Нет, я так не думаю. В каком слайде?"
"В том, на котором показано, что программа вызывает саму себя. Реализовать это невозможно".
Питер был озадачен еще больше: "Но мы же реализовали язык полностью и пропустили все примеры через наш компилятор".
Мужчина сел, но продолжал бормотать: "Невозможно! Невозможно!"
Я подозреваю, что не один он в зале думал так же.
В то время общепринятой практикой было
Говоря о независимом изобретении понятия стека вызовов, Хорнинг, видимо, имеет в виду Фридриха Бауэра из Мюнхена, который использовал термин Keller (
(рис 9.7) Фридрих Бауэр (2005)
Код, данный выше, в сравнении с исходным рекурсивным вариантом выглядит громоздким. Действительно, для серьезного рекурсивного алгоритма итеративная версия никогда не будет выглядеть столь же элегантной, как рекурсивная. Но мы попытаемся приблизиться к этому эталону, пересмотрев источники компиляции.
goto конструкциями структурного программирования.Последние два случая упрощений могут быть также важны для улучшения производительности, поскольку операции над стеком требуют и времени, и памяти.
В примере с Ханойской башней первым делом устраним торчащие как заноза операторы goto. Чтобы абстрагироваться от лишних деталей кода, запишем тело процедуры iterative_hanoi в виде:
INIT
start: if count > 0 then
SAVE_AND_ADAPT_1
goto start
after_1: MOVE
SAVE_AND_ADAPT_2
goto start
end
after_2: if not stack.is_empty then
RETRIEVE
if call = 2 then goto after_2 else goto after_1 end
end
Здесь SAVE_AND_ADAPT_1 представляет сохранение информации в стеке и изменение значений перед первым вызовом, SAVE_AND_ADAPT_2 – то же для второго вызова, call, MOVE – базисную операцию переноса, INIT – инициализацию локальных переменных значениями аргументов.
Ранее, при обсуждении вопроса избавления от goto подобный пример уже был рассмотрен. Еще раз проанализировав его, нетрудно понять, что наша программа может быть записана с циклами, но без goto:
from INIT until over loop
from until count <= 0 loop
SAVE_AND_ADAPT_1
end
from stop := stack.is_empty until stop loop
RETRIEVE
stop := (stack.is_empty or (call /= 2))
end
over := (stack.is_empty and (call = 2))
if not over then MOVE ; SAVE_AND_ADAPT_2 end
end
И этот вариант можно упростить, удалив, в частности, булевскую переменную stop:
from INIT until over loop
from until count = 0 loop SAVE_AND_ADAPT_1 end
from call := 2 until stack.is_empty or call = 1 loop RETRIEVE end
over := (stack.is_empty and (call = 0))
if not over then MOVE ; SAVE_AND_ADAPT_2 end
end
Упрощения являются результатом анализа возможных значений переменных.
count никогда не может стать отрицательной величиной из-за предусловия, требующего его положительности, и условия завершения вычислений, то вполне законно заменить тест count <= 0 на тест count = 0.stop заметим, что значение call может быть только 1 или 2, так что допустимо заменить тест call /= 2 на тест call = 1. После чего установим начальное значение call = 2, так что это условие будет учитываться для второй и последующих итераций, если таковые будут.Стандартная техника, позволяющая уменьшить затраты на операции над стеком по вталкиванию и выталкиванию элементов, основана на том, что нет необходимости хранить контекстную информацию, а позже получать ее, если алгоритму эта информация больше не нужна. В частности, это происходит при рекурсивном вызове, который является последней операцией, выполняемой экземпляром рекурсивной программы.
Это упрощение применимо к примеру hanoi. Второй SAVE_AND_ADAPT_2, или, более точно, единственная информация, которую требуется сохранить, – это значение call, так как при возврате необходимо анализировать это значение.
Хороший компилятор может обнаружить хвостовую рекурсию и применить эту оптимизацию для улучшения производительности рекурсивного алгоритма.
В случае с hanoi устранение хвостовой рекурсии может и не проводиться, так как существует другая, более мощная оптимизация, почти полностью устраняющая необходимость в стеке, с которой мы вскоре познакомимся. Но все же следует освоить на практике оптимизацию, связанную с хвостовой рекурсией, удалив операции, в которых нет необходимости.
Использование стека для хранения значений перед вызовом и получение их после завершения вызова – это техника по умолчанию, которая работает во всех случаях; но мы уже видели ранее, что существует альтернатива данному подходу – обращение преобразования аргументов. В случае с hanoi обращение возможно для всех аргументов.
count:= count - 1, имеет очевидное обращение: count:= count + 1.swap23 – для первого вызова и swap12 – для второго, где swapij означает операцию обмена между стержнями с номерами i и j. Понятно, что эта трансформация обратима, более того, swapij является собственным обращением, поскольку двойной обмен восстанавливает исходное состояние.Так что, фактически, нет необходимости хранить в стеке ни count, ни x, y, z. Достаточно при достижении
Стек остается необходимым, но только для записи и получения call. Упрощение становится еще существеннее, если вспомнить, что call имеет только два значения: 1 и 2. Но ничто не мешает нам изменить соглашение и рассматривать их как булевские значения 1 и 0. Тогда можно применить стек, содержащий булевское значение. Более того, если допустимо ограничить высоту стека, то вместо стека можно использовать единственную целочисленную переменную, скажем, s (в современных компьютерах целочисленные переменные могут иметь длину в 64 бита). Тогда операции над стеком моделируются операциями над целым s, рассматриваемым как строка битов:
s = 1 — Пуст ли стек?
s := 1 — Инициализация пустого стека
s := 2*s — Втолкнуть 0 (сдвиг влево на один разряд строки битов)
s := 2*s + 1 — Втолкнуть 1 (сдвиг влево на один разряд строки битов с
— приписыванием 1)
b := s \\ 2 — Получить (в b) значение с вершины стека
— (\\ остаток от деления нацело)
s:= s // 2 — Удалить значение с вершины стека
— (// - деление нацело – сдвиг вправо)
Вот результат выполнения некоторой последовательности таких операций.
| Оператор | Цель | Результат | Бинарное представление s (часть нулей слева опущена) |
|---|---|---|---|
s:= 1 |
— Начать с пустого стека | s = 1 | 1 |
s:= 2*s |
— Втолкнуть 0 | s = 2 | 10 |
s:= 2*s + 1 |
— Втолкнуть 1 | s = 5 | 101 |
s:= 2*s + 1 |
— Втолкнуть 1 | s = 11 | 1011 |
s:= 2*s |
— Втолкнуть 0 | s = 22 | 10110 |
s:= s // 2 |
— Вытолкнуть | s = 11 | 1011 |
b:= s \\ 2 |
— Прочитать элемент вершины | b = 1 |
В последнем столбце показано бинарное представление целого. Если нумеровать разряды в этом представлении справа налево, начиная с 0, то единица в разряде $$k$$ имеет значение $$2^k$$. Значение 0 в самом правом разряде означает, что число четное, 1 – нечетное. Когда такое представление задает стек булевских значений, вершиной стека является самый правый разряд. Пустой стек задается значением $$s$$, равным 1.
Техника использования единственного целого числа для задания стека булевских значений может безопасно использоваться, когда гарантируется, что размер стека не превосходит длины целого в битах. В примере с Hanoi проблемы не возникает, поскольку $$2^{63}$$ или даже $$2^{31}$$ – число, задающее количество ходов, столь велико, что компьютеру не справиться с вычислениями за разумное время.
В результате обсуждений приходим к более простой и эффективной форме алгоритма iterative_hanoi с аргументами n, source, target, other:
Хотя полученная программа является результатом систематических трансформаций, а не программой, которую вы бы написали с самого начала (рекурсия яснее и проще), интересно проследить за ее выполнением, сравнивая с оригинальной рекурсивной версией, а особенно – с бинарным деревом выполнения, представленным в начале этой лекции и показывающим выполнение как инфиксный обход дерева:
(рис 9.8) Обход бинарного дерева задачи Hanoi
В алгоритме можно выделить три компонента.
| H1 | Самый левый в глубину – идти насколько возможно вниз, влево, пока не достигнешь листа. У листьев значение n = 0 (count в этой версии), хотя на предыдущих рисунках дерево заканчивалось на 1, поскольку на нулевом уровне ничего не происходит. |
| H2 | Возврат вверх. Если вы возвращаетесь из правого поддерева, то продолжаете идти вверх, поскольку это означает завершение второго рекурсивного вызова, а следовательно – и завершение работы текущего экземпляра процедуры. |
| H3 | Поднявшись вверх по левой ветви, выполняем посещение корня – перенос диска из x на y, а потом идем вниз по правой ветви. |
Все это повторяется, пока, придя справа (H2), не обнаружим, что стек пуст.
При спуске вниз (H1, H3) уменьшается count и выполняется обмен y и z, если идем слева (H1), и обмен x и z, если идем справа (H3). При возврате назад (H2) восстанавливаются исходные значения, увеличивая count и выполняя подходящий обмен в зависимости от того, справа или слева вы пришли. Анализ вершины стека, хранящей значение call, позволяет понять, откуда мы пришли в узел – слева (первый вызов) или справа (второй вызов).
| Activation | Активация | Activation record | Запись активации |
| Alpha-beta | Альфа-бета | Backtracking | Перебор с возвратами |
| Binary tree | Бинарное дерево | Call chain | Цепочка вызовов |
| Depth-first | Первый в глубину | Direct recursion | Прямая рекурсия |
| Indirect recursion | Непрямая ( |
Inorder | Инфиксный |
| Instance (of a routine) | Экземпляр (программы) | Iterative | Итеративный |
| Minimax | Non-creative | Не творческий | |
| Postorder | Постфиксный | Preorder | Префиксный |
| Recursion | Рекурсия | Recursive | Рекурсивный |
| Recursive definition | Рекурсивное определение | Traversal | Обход |
Дайте точные определения терминам словаря.
Является ли определение "рекурсивного определения" рекурсивным?
Для каждого приведенного в этой лекции метода поиска в бинарных деревьях перепишите объявление (если требуется), допуская возможность множественного вхождения элемента item в дерево.
Напишите компилятор и интерпретатор элементарного языка программирования. Используйте приемы, обсуждаемые в предыдущих лекциях. Решение должно использовать рекурсию. Чтобы избежать проблем с конкретным синтаксисом, ваш инструментарий должен иметь дело непосредственно со структурами данных, а не с текстом программы.
Наш маленький язык, назовем его АСТ ("
integer.Типичная программа на АСТ приведена здесь с учетом конкретного синтаксиса, хотя он и не является частью определения языка:
assign
x := 3
y := 5
x := 2*(x + (y // 3))
then
print x
print z
end
В результате выполнения этой программы должно быть напечатано одно значение – 8.
Синтаксис конкретной программы является одним из возможных выборов. Вполне возможно, например, вместо слова then использовать ключевое слово print. Печать переменных можно задавать списком без повторения print.
Напишите множество классов, включающее PROGRAM, ASSIGNMENT, PRINT, EXPRESSION. Методы этих классов, включающие процедуры создания, должны позволять построить абстрактное синтаксическое дерево, задающее АСТ-программу.
PROGRAM процедуру write_out, которая выполняет текстуальное представление АСТ-программ в том виде, как оно дано в примере. Выполните программу из шага 2 и убедитесь в корректности полученного результата. Подсказка: вам необходима рекурсивная процедура обхода, подобная той, которая рассматривалась в данной лекции.interpret PROGRAM, который выполняет программу и вырабатывает ожидаемый результат. Запустите ее на данном примере и проверьте результат выполнения.compile в классе PROGRAM, которая АСТ-программу преобразует в программу на Терминологическое замечание. Результатом шага 5 является реанализатор – unparser, который создает текст программы по внутреннему представлению, такому как абстрактное синтаксическое дерево, выполняя операцию, обратную тому, что делает классический анализатор – parser.
Напишите версию put для бинарного дерева поиска, используя цикл, а не рекурсию.
Подсказка: источником вдохновения может служить реализация метода has.
Сохраняя предположения (список остановок известен своей первой ячейкой типа STOP, остальные остановки доступны через повторное применение next), перепишите функцию reversed, используя рекурсию вместо цикла (смотри также следующее упражнение).
Напишите рекурсивную функцию для обращения связного списка (аргумент и результат должны быть типа LINKED_LIST[G]). Сведите к минимуму манипуляции с указателями и приблизьтесь, насколько возможно, к стилю функции reversed, приведенному как пример программирования на Haskell. Проанализируйте временную и
Адаптируйте общий алгоритм перебора с возвратами так, чтобы он сохранял историю ранее исследованных позиций и удалял любой путь, ведущий к такой позиции. Можете предположить, что PATH имеет запрос position, определяющий терминальную позицию пути.
Адаптируйте общий алгоритм перебора с возвратами так, чтобы он не исследовал пути длиннее, чем path_cutoff – заданное целое число.
(Это упражнение не требует программирования, но предполагает проведение математического анализа)
Для последовательных аппроксимаций $$H_i$$ графа функции, связанной с Ханойской башней (параграф 5.7: "Башни снизу вверх"), определите:
Рассмотрим рекурсивный алгоритм обхода бинарного дерева: вы можете выбрать префиксный, инфиксный или постфиксный порядок обхода.
(Это упражнение требует доступа к компилятору, например, С или С++, с поддержкой оператора goto)
Реализуйте и протестируйте прямую итеративную трансляцию процедуры hanoi в ее начальном варианте, используя goto и стек без оптимизации.
goto, основанную на стеке версию Ханойской башни.goto.Мы видели, что реализация рекурсии требует обращения преобразования аргументов рекурсивного вызова. Стек является одним из возможных путей решения этого требования. Используя подходящие приемы обращения, реализуйте обход бинарного дерева, например, в инфиксном порядке, без рекурсии и без стека, за исключением, возможно, стека булевских значений (или, эквивалентно, бита в каждом узле).
Подсказка: временно переопределите связи дерева, сохраняя информацию о том, откуда пришли в узел.
Контр-подсказка: решение можно найти, набрав при поиске в Интернете слова Deutsch, Shorr или Waite (имена авторов известного алгоритма, основанного на этой идее). Не делайте этого! Спроектируйте алгоритм самостоятельно, затем посмотрите ссылки, если пожелаете.
(Это упражнение ссылается на последнюю лекцию)
Сформулируйте определение транзитивного замыкания как рекурсивное определение.
(Это упражнение требует знания основ линейной алгебры)
Рассмотрим
Вернемся назад, к общим проблемам рекурсии.
Мы уже видели, что некоторые рекурсивные алгоритмы –
Фактически, нетрудно заменить любой цикл рекурсией. Рассмотрим произвольный цикл, данный здесь без указания инвариантов и варианта (хотя позже мы познакомимся с рекурсивными двойниками):
from Init until Exit loop Body end
Мы можем заменить его на
Init
loop_equiv
Здесь введена процедура:
loop_equiv
— Используется условие выхода Exit и тело цикла Body.
do
if not Exit then
Body
Loop_equiv
end
end
В функциональных языках (таких как Lisp, Scheme, Haskell, ML) рекурсивный стиль является предпочитаемым, даже если доступны циклы. Мы могли бы также использовать рекурсию с первых шагов нашего курса, рассмотрев, например, анимацию линии метро, перемещающую красную точку, как рекурсивную процедуру:
Line8.start
animate_rest (Line8)
Вот как могла бы выглядеть сама процедура:
animate_rest (line: LINE)
— Анимация станций линии метро, начиная от текущей позиции курсора
do
if not line.after then
show_spot (line.item.location)
line.forth
animate_rest (line)
end
end
(более полная версия должна восстанавливать текущую позицию курсора).
Рекурсивная версия выглядит элегантно, но нет особых причин в рамках нашего курса предпочитать ее форме с применением циклов, мы и в дальнейшем будем использовать циклы.
Но даже чисто теоретически важно понимать, что циклы не являются обязательной принадлежностью языка программирования и могут быть заменены рекурсией. Хорошим примером является программа paradox, демонстрирующая неразрешимость проблемы остановки. Рекурсия позволяет задать более выразительную версию:
recursive_paradox
— Завершается, если и только если не завершается.
do
if terminates ("C:\your_project") then
recursive_paradox
end
end
Знание того, что всякий цикл может быть заменен рекурсией, немедленно порождает вопрос, а верно ли обратное – можно ли рекурсивную процедуру заменить процедурой, использующей циклы?
С примерами замены мы уже встречались – те же has и put для бинарных деревьев. Другие рекурсивные процедуры – hanoi, height, print_all – не имели свободного от рекурсии эквивалента. Для понимания того, что точно может быть сделано, необходимо более глубоко познакомиться со свойствами и смыслом рекурсивных программ.
Приобретенный опыт построения рекурсивных программ позволяет нам более глубоко исследовать смысл рекурсивных определений.
Прежде всего, вернемся назад и зададим весьма невежливый вопрос: а не является ли рекурсия "голым королем"? Другими словами, стоит ли что-либо за рекурсивным определением? Примеры, особенно примеры рекурсивных программ, свидетельствуют в их пользу, но некоторая доля сомнений все же остается. Мы все же находимся в опасной близости к определениям, не имеющим смысла, – к каким-то неправильным циклам. Рекурсия позволяет определять понятие в терминах самого понятия. Но, когда говорится:
Информатика занимается изучением информатики
то это общее место,
Информатика занимается изучением программирования, структур данных, алгоритмов, приложений, теоретическими вопросами и другими областями информатики
В определение добавлены полезные элементы, но оно все еще не является удовлетворительным определением. Подобным образом могут оказаться бесполезными и рекурсивные программы, такие как эта:
p (x: INTEGER)
— Что в этом хорошего?
do p (x) end
Эта программа выполняется для любых целочисленных аргументов, не производя никакого результата, работая бесконечно долго.
Как избежать такого очевидного ошибочного использования рекурсии? Если попытаться понять, почему рекурсивные определения, с которыми мы сталкивались, кажутся интуитивно имеющими смысл, то можно выделить три интересных свойства.
Полезное рекурсивное определение должно удовлетворять следующим требованиям:
| R1 | должна присутствовать хотя бы одна нерекурсивная ветвь; |
| R2 | каждый вызов рекурсивной ветви должен иметь контекст, отличающийся от контекста, в котором эта ветвь была вызвана; |
| R3 | для каждой рекурсивной ветви изменение контекста (R2) приближает к одному из нерекурсивных случаев (R1). |
Для рекурсивных программ изменение контекста (R2) может заключаться в том, что вызов использует различное значение аргумента, как в вызове r(n -1) в программе r(n:INTEGER). Этот вызов применим к различным целям – x.r(n), где x не является текущим объектом. Изменение контекста может также означать, что вызов встречается после того, как программа изменила по меньшей мере одно поле по меньшей мере одного объекта.
Все рекурсивные программы, рассмотренные нами ранее, удовлетворяют этим требованиям.
Hanoi(n, …) включает условный оператор if n > 0 then … end, где все рекурсивные вызовы сосредоточены в then-ветви оператора, но поскольку else-ветвь отсутствует, то эта "пустая" ветвь при n = 0 определяет нерекурсивный вариант (R1). Рекурсивные вызовы имеют форму Hanoi(n - 1, …), изменяя первый аргумент и порядок других аргументов (R2). Замена n на n – 1 приближает контекст к нерекурсивному случаю n = 0 (R3).x = item, для x < item, если нет x > item, если нет правого поддерева (R1). Рекурсивные вызовы имеют другую цель – left или right, отличающуюся от текущего объекта (R2). Каждый такой вызов приближается к height.animate_rest – рекурсивной версии обхода линии метро, – когда курсор находится в положении after, срабатывает нерекурсивная ветвь (R1), ничего не делающая. Рекурсивные вызовы не изменяют аргумент, но в процессе работы вызывается метод line.forth, изменяющий состояние линии (R2); при этом курсор передвигается ближе к состоянию after, где рекурсия заканчивается (R3).Для рекурсивных понятий, не связанных с программами, условия R1, R2, R3 также должны выполняться.
STOP, являются рекурсивными благодаря ссылкам, которые могут иметь значение void. В void служат в качестве Каждая рекурсивная программа должна быть объявлена с ассоциированным с рекурсией вариантом, целочисленной величиной, связанной с каждым вызовом, такой, что:
v для варианта, то значение варианта v1 для любого рекурсивного вызова удовлетворяет условию 0 <= v1 < v.Вариант может включать аргументы
Hanoi(n, …) вариантом является n.has, height, print_all и других node_height – наибольшая длина пути от текущего узла до одного из animate_rest вариантом является, как и для соответствующего цикла, Line8.count – Line8.index +1.Специального синтаксиса для вариантов Hanoi(n, …):
— variant n
Хорошо определенные правила кажутся настолько разумными, что мы можем думать, что они являются не только достаточными, но и необходимыми правилами, чтобы рекурсивное определение имело смысл. Это и в самом деле справедливо для первых двух правил.
| R1 | Если все ветви определения являются рекурсивными, то невозможно выработать какой-либо экземпляр, который не был бы уже известен. В случае рекурсивных программ такое определение приводит к бесконечным вычислениям, на практике аварийно заканчивающимся из-за переполнения памяти. |
| R2 | Если рекурсивная ветвь применяется к оригинальному контексту, то она не может выработать экземпляр, который не был бы уже известен. Для рекурсивной программы (например, p(x: T) с ветвью, которая вызывает p(x) для того же x, что и в начальном вызове, и где ничего не менялось), это приводит опять-таки к зацикливанию вычислений. Если речь не идет о программах и вычислениях, то такая ветвь бесполезна. |
Другая ситуация – с правилом R3, где правило требует существования варианта у рекурсии, такого как аргумент n у Hanoi. Некоторые рекурсивные программы, которые завершаются, нарушают это свойство. Приведу два примера. Они не имеют практических применений, но высвечивают общие свойства, которые следует знать.
Функция 91 Маккарти была спроектирована Джоном Маккарти, профессором университета в Стэнфорде, создателем языка
mc_carthy (n: INTEGER): INTEGER
— Функция 91 Маккарти.
do
if n > 100 then
Result := n – 10
else
Result := mc_carthy (mc_carthy (n + 11))
end
end
Для целых n, больших 100, она возвращает значение n – 10. Это понятно. Значительно менее понятно из-за двойного рекурсивного вызова, какое же значение вернет функция для n, меньших 100, в том числе и для отрицательных значений, и вообще – закончатся ли вычисления. Оказывается, что во всех случаях, когда n меньше 100, функция завершает работу и возвращает значение 91, из-за чего функция и получила такое имя. Но очевидного варианта здесь нет, и внутренний n.
Вот еще один пример знаменитой программы и знаменитой проблемы, не получившей решения до настоящего момента:
bizarre (n: INTEGER): INTEGER
— Функция, всегда возвращающая 1 для n нечетного и большего 1.
require
positive: n >= 1
do
if n = 1 then
Result := 1
elseif even (n) then
Result := bizarre (n // 2)
else — для нечетных n, больших 1
Result := bizarre ((3*n + 1) // 2)
end
end
Здесь используются операция // – деление нацело, и even(n), истинное для четных n. Два вхождения этой операции дают точное значение, поскольку применяются к четным числам. Понятно, что если функция возвращает результат, то он может быть только 1, производимой единственной нерекурсивной ветвью. Но завершается ли эта программа для любых n? Ответ кажется очевидным: "да" (можно написать программу и проверить ее на возможном диапазоне чисел. Доказана ее завершаемость на очень больших числах, но общего решения пока нет). Явного варианта рекурсии здесь нет, и видно, что в одной из ветвей рекурсивного вызова аргумент (3*n +1)//2 больше, чем n.
Эти интересные примеры являются экзотикой, но необходимо принимать в расчет их существование для общего понимания рекурсии. Они означают, что существуют некоторые рекурсивные определения, которые не удовлетворяют, казалось бы, разумным методологическим правилам, обсужденным выше, и все же вырабатывают хорошо определенные результаты.
Заметьте, что такие примеры, завершающиеся для каждого возможного аргумента, должны иметь вариант, так как для любого выполнения число рекурсивных вызовов определено и конечно, и следовательно, определяется состоянием программы во время вычисления, так что оно является функцией состояния, которая и может служить вариантом. Беда в том, что эта функция неизвестна, мы не можем ее выразить, а раз так, то ее теоретическое существование мало что дает практике.
На практике мы такие примеры оставляем без внимания и ограничиваем себя рекурсивными определениями, которые обладают всеми тремя свойствами – R1, R2, R3. В частности, когда вы пишете рекурсивную программу, следует всегда, как в оставшихся примерах этой лекции, явно задавать вариант в рекурсии.
Даже с хорошо определенными правилами и наличием варианта у рекурсии мы все же не можем спать спокойно, используя рекурсию. Проблема в том, что рекурсивное определение не является определением в обычном смысле, поскольку оно может быть креативным – творческим.
Аксиома в математике является креативной: она говорит нам нечто такое, что не может быть выведено из известных уже фактов. Примером является аксиома о целых в математике, которая говорит, что для числа n', следующего за n, справедливо n < n'. Фундаментальные законы в естественных науках также креативны, например, закон, утверждающий о невозможности двигаться со скоростью, превышающей скорость света.
Теоремы в математике, так же как и аналогичные результаты в физике, с рассматриваемой точки зрения "творческими" не являются, поскольку могут быть выведены из аксиом и известных уже законов. Они интересны сами по себе и позволяют нам более просто выводить новые утверждения, но они не добавляют новых предположений, являясь следствиями уже сделанных ранее.
Определение, так же как и теорема, не должно быть творческим. Определение дает новое имя объекту нашего мира, но все утверждения, которые можно выразить с использованием определения, могут быть сделаны и без помощи этого определения. Мы хотим более просто выражать утверждения, используя введенное определение, а иначе зачем бы понадобилось его вводить. Но мы знаем, что можно обойтись и без определения. Пусть сказано:
$$\text{Определим }x^2\text{ для любого x, как x * x}$$Ничего нового такое определение в математику не добавляет: просто разрешается использовать новую нотацию для умножения. Любое свойство, которое может быть доказано с использование новой нотации, может быть доказано и без нее, по сути, заменой $$x^2$$ в соответствии с определением.
Символ $$\triangleq$$, который мы использовали для обозначения "определено как" (начиная с
Здесь some_expression включает f. Теперь наш принцип больше не выполняется! Всякая попытка заменить f в определении some_expression на some_expression не устраняет f, так что реально мы ничего не определили. До тех пор, пока мы не найдем удобного, некреативного смысла для определений, подобных формуле (5.1), мы должны быть терминологически аккуратны. По этой причине символ $$\triangleq$$ будет использоваться только для нерекурсивных определений, а такое свойство, как (5.1), будет задаваться равенством
Это равенство можно рассматривать как уравнение, решением которого выступает f. Говоря о рекурсивных "определениях", для корректности будем заключать второе слово в кавычки.
Изолировав пока рекурсию и поместив ее в карантинную зону, полезно посмотреть на рекурсивные программы и рекурсивные "определения" в целом с позиции "снизу вверх". Я надеюсь, что это удалит легкое головокружение, которое остается, когда видишь определения программ, которые – частично – сами себя вызывают.
Рекурсивные "определения" пишутся "сверху вниз", определяя смысл понятия в терминах того же понятия для "меньшего" контекста – меньшего с точки зрения варианта рекурсии. Например, Fibonacci для n выражается через Fibonacci для n – 1 и n – 2.
Взгляд "снизу-вверх" предоставляет другую интерпретацию того же определения, трактуя это другим способом, как механизм, который создает новое значение на основе уже существующих. Начнем с рассмотрения функции. Для любой функции f можно построить граф этой функции как множество пар [x, f(x)] для каждого применимого x. Граф для функции Fibonacci задается множеством
Он содержит все пары [n, Fibonacci(n)] для всех неотрицательных n. Этот граф содержит всю информацию о функции. Визуально этот граф можно представить в следующей форме:
(рис 9.1) Граф функции (Фибоначчи)
В верхней строчке показаны возможные аргументы функции, в нижней – соответствующие значения функции.
Дать функции рекурсивное определение – это все равно, что сказать, что ее граф F – как множество пар – удовлетворяет некоторому свойству
Здесь h рассматривается как некоторая функция, применимая к такому множеству пар. Это подобно уравнению, которому F должна удовлетворять, и известному как уравнение неподвижной точки. Неподвижной точкой – решением такого уравнения – является некоторый математический объект, в данном случае функция, который остается инвариантом при некоторых трансформациях, в данном случае – задаваемых функцией h.
Определим рекурсивно функцию Fibonacci:
$$fib (0) = 0\\fib (1) = 1\\fib (i) = fib (i – 1) + fib (i – 2)\qquad \text{— Для }i >1$$Такое определение эквивалентно тому, что граф F, рассматриваемый как множество пар, удовлетворяет уравнению неподвижной точки (5.4), где h – это функция, которая, получив множество пар, вырабатывает новое множество, содержащее следующие пары:
| G1 | каждую пару, уже содержащуюся в F |
| G2 [0, 0] | — Пару для n = 0: [0, |
| G3 [1, 1] | — Пару для n = 1: [1, |
| G4 | каждую пару в форме [i, a + b)] для некоторого i, такого, что F содержит пары [i-1, a] и [i-2, b] |
Мы можем использовать эту точку зрения, чтобы дать рекурсивному "определению" точный смысл, свободный от всякой рекурсивной загадочности. Мы начинаем с графа $$F_0$$, который пуст (не содержит пар). Далее мы определяем
$$F_1\triangleq h(F_0)$$Оно имеет смысл и означает, что $$F_1$$ задается множеством {[0, 0], [1, 1]} – парами, определяемыми правилами G2 и G3. Правила G1 и G4 в данном случае неприменимы, так как $$F_0$$ пусто. Затем мы снова применяем $$h$$, чтобы получить
$$F_2\triangleq h(F_1)$$Здесь G2 и G3 нам не дают ничего нового, так как пары [0, 0] и [1, 1] уже присутствуют в $$F_1$$, но G4 создает новую пару из существующих – [2, 1]. Продолжая, мы определяем последовательность графов, начиная с $$F_0$$ и определяя $$F_i = h(F_{i – 1})$$. Теперь рассмотрим $$F$$ как бесконечное объединение:
$$\bigcup\limits_{i\in N}F_i$$Здесь $$N$$ – это множество натуральных чисел. Достаточно просто видеть, что $$F$$ удовлетворяет свойству (5.4).
Такова нерекурсивная интерпретация – семантика, – которую мы дали рекурсивному "определению" функции Fibonacci.
В общем случае уравнение неподвижной точки в форме (5.4) на графах функции, устанавливающее эквивалентность $$F$$ и $$h(F)$$, представляет решение в виде графа функции
$$F\triangleq\bigcup\limits_{i\in N}F_i$$Здесь $$F_i$$ – это последовательность графов функции:
$$F_0\triangleq \{ \}\qquad\qquad\text{ — Пустое множество пар}\\F_i\triangleq h(F_{i-1})\qquad\text{ — Для }i > 0$$Подход, основанный на неподвижной точке, является базисом интерпретации "снизу вверх" рекурсивных вычислений. Он частично удаляет загадочность из этих определений, поскольку рассматривает рекурсивное определение как уравнение неподвижной точки и допускает решение, полученное как результат объединения (подобно пределу последовательности в математическом анализе) последовательности графов функции.
Данный подход редуцирует рекурсивное "определение" к хорошо известному, традиционному понятию индуктивного определения последовательности.
Функция Фибоначчи является хорошим примером для понимания концепции, но, вероятно, она не поражает впечатления. Во всех учебниках по математике она определяется индуктивно как последовательность чисел. Это в компьютерном мире мы рассматриваем ее как рекурсивную функцию. Так что мы не узнали ничего нового о самой функции, а просто познакомились с разными точками зрения. Давайте посмотрим, можно ли научиться чему-нибудь на других примерах.
Понимая природу "снизу вверх", можно дать ясное понимание смысла рекурсивного определения понятия "тип". Как вы помните, тип определяется следующим образом:
| T1 | базисный класс, такой как INTEGER или STATION; |
| T2 | родовое порождение в форме C [T], где C является T – это тип. |
Правило T1 определяет нерекурсивный случай. Взгляд "снизу вверх" позволяет нам понимать данное определение как построение множества типов в виде последовательности слоев. Ограничившись для простоты одним родовым параметром, имеем:
INTEGER, STATION и т.д.;C [X], где C универсальный класс, а X принадлежит уровню L0: LIST [INTEGER], ARRAY [STATION] и т.д.;n > 0 имеет все типы в форме C [X], где X принадлежит уровню Li для i < n.Таким образом, мы получаем все типы – базисные и полученные в результате родового порождения.
Взглянем теперь "снизу вверх" на Ханойские башни. Программу можно рассматривать как рекурсивное определение последовательности ходов. Давайте обозначим такую последовательность как $$<A\to B,\; C\to A, …>$$, означающую, что первым ходом переносится диск с вершины стержня А на B, затем с C на A и так далее. Пустая последовательность будет $$<>$$, а конкатенация последовательностей задается знаком "+", так что
$$<A\to B,\; C\to A> + <B\to A>\text{ дает }<A\to B,\; C\to A,\; B\to A>.$$Тогда мы можем выразить рекурсивное решение как функцию
Функция определена, если $$n$$ положительно и значения $$s$$, $$t$$, $$o$$ (сокращения для source, target, other) различны – мы используем их, как и ранее, для обозначения стержней 'A', 'B', 'C'. Конструирование функции, решающей уравнение, просто: (5.5) позволяет инициализировать граф функции для $$n = 0$$ в следующей форме:
Обозначим через $$H_0$$ эту первую часть графа, содержащую 6 пар, которые включают все возможные перестановки стержней. После этого можно использовать (5.6) для получения множества пар $$H_1$$, содержащего значения для $$n = 1$$, где пары имеют вид:
$$[(1, s, t, o), <s\to t>]$$Здесь учитывается, что конкатенация $$< > + x$$ или $$x + < >$$ дает $$x$$. Следующая итерация (5.6) даст нам $$H_2$$, чьи пары имеют вид:
$$[(2, s, t, o), fl + <s\to t> + gl]$$Это верно для всех $$s, t, o$$ таких, что $$H_1$$ содержит как пару $$[(1, s, o, t), f1]$$, так и пару $$[(1, o, t, s), g1]$$.
Последующее итерирование позволит построить граф $$H_3$$. Полный граф – разумеется, бесконечный, поскольку включает пары для всех возможных $$n$$, – задает множество всех пар во всех элементах последовательности:
$$\bigcup\limits_{i\in N}H_i$$Теперь я смею надеяться, что вы получили достаточное представление о подходе "снизу вверх" к
Напишите программу (не используя рекурсии), создающую последовательно элементы множеств $$H_0, H_1, H_2 \ldots$$ для Hanoi.
Связанное с этой задачей упражнение попросит вас определить (без программирования) математические свойства графа.
Еще одно важное упражнение потребует применить подобный анализ к обходу бинарного дерева. Вы должны будете спроектировать модель для представления решения, подобную той, что использована в данной задаче, – вместо последовательности ходов должна появиться последовательность узлов.
Подход "снизу вверх", в частности, применим и для рекурсивных грамматик, как в нашем небольшом примере:
$$Instruction\triangleq ast\;\; |\;\; Conditional\\Conditional\triangleq ifc\;\; Instruction\;\; end$$Здесь введены сокращения: ifc представляет "if Condition then" и ast представляет "Assignment", оба рассматриваются как терминалы в данном обсуждении.
Достаточно просто видеть, как генерировать последовательные предложения языка, интерпретируя создаваемые продукции в стиле неподвижной точки:
$$ast\\ifc\;\;ast\;\;end\\ifc\;\;ifc\;\;ast\;\;end\;\;end\\ifc\;\;ifc\;\;ifc\;\;ast\;\;end\;\;end\;\;end$$С этих же позиций может быть проанализировано предыдущее обсуждение небольшого языка Game.
Данный подход обобщается на произвольные грамматики, рассматривая матричное представление описания
Мы уже научились поставлять наши классы и их методы с контрактами, устанавливающими их корректность: предусловия и постусловия методов, инварианты класса. Те же подходы, применяемые к алгоритмам, приводят к заданию вариантов и
Мы уже познакомились с понятием варианта для рекурсии. Если метод рекурсивен непосредственно или косвенно, то следует включать вариант для рекурсии в его описание. Как отмечалось, специальный синтаксис для этих целей отсутствует, так что приходится добавлять отдельное предложение в заголовочный комментарий метода:
— variant: expression
Вот пример процедуры Hanoi с более полными контрактами, новыми предложениями, записанными в виде комментариев:
hanoi (n: INTEGER; source, target, other: CHARACTER)
—Перенос n дисков из source на target,используя other
—в соответствии с правилами игры Ханойская Башня
— invariant: диски на каждом стержне образуют пирамиду,
— следуя в порядке уменьшения размеров.
— variant: n
require
non_negative: n >= 0
different1: source /= target
different2: target /= other
different3: source /= other
— source имеет n дисков; target и other пусты – без дисков
do
if n > 0 then
hanoi (n–1, source, other, target)
move (source, target)
hanoi (n–1, other, target, source)
end
ensure
— Диски, ранее находившиеся на source, теперь перенесены на target,
— сохраняя прежний порядок,
— other находится в исходном состоянии.
end
—invariant: текст комментария
Предлагаемая конструкция не является частью языка, но подчиняется следующим соглашениям.
Рекурсивное программирование хорошо работает в некоторых проблемных областях, что проиллюстрировано примерами этой лекции. Когда рекурсия облегчает вашу работу, нужно применять ее, не раздумывая, так как в современных языках программирования рекурсия считается само собой разумеющейся.
Обычно на уровне машинного кода отсутствует прямая поддержка рекурсии. Компиляторы для языков высокого уровня должны отображать рекурсивно выраженный алгоритм в нерекурсивный. Применяемая при этом техника, несомненно, важна для разработчиков компиляторов, но и для вас, даже если вы и не собираетесь написать компилятор, полезно познакомиться с базисными идеями, как для лучшего понимания рекурсии, так и для осознания потенциальных проблем производительности, связанных с реализацией рекурсии.
Мы рассмотрим некоторые рекурсивные схемы и спросим себя, как, если язык не допускает рекурсию, можно было бы спроектировать нерекурсивную версию, называемую также итеративной, доставляющую те же результаты.
Рассмотрим рекурсивную процедуру r, содержащую собственный вызов:
r (x: T)
do
code_before
r (y)
code_after
end
Здесь могло бы быть несколько рекурсивных вызовов, но мы пока рассматриваем только один. Что это означает, если вернуться к взгляду "сверху вниз"?
Наличие рекурсии влечет, что ни начало кода метода, ни его конец не являются тем, на что они претендуют (быть началом и концом).
code_before, то это вовсе не означает, что выполнение инициировано вызовом метода клиентом a.r(y) или неквалифицированным вызовом r.(y), – это может быть результатом работы экземпляра r, вызывающего себя рекурсивно.code_after завершается, это вовсе не означает завершение истории r: это может быть просто завершение одного рекурсивно вызванного экземпляра. В этом случае следует подвести итоги выполнения последнего вызванного экземпляра r и продолжить выполнение предыдущего экземпляра.Ключевой новинкой последнего наблюдения является понятие экземпляра (называемого также активацией) программы. Мы знаем, что классы имеют экземпляры – "объекты", создаваемые при выполнении ОО-программы. Теперь подобным образом начнем рассматривать и методы класса.
В любой момент выполнения программы состояние вычислений характеризуется цепочкой вызовов, как показано на рисунке. Корневая процедура p вызывает q, которая, в свою очередь, вызывает r… Когда выполнение программы в цепочке завершается, скажем, r, отложенное выполнение вызывающей программы, здесь q, подводит итоги и продолжается с той точки, где оно было прервано при вызове r.
(рис 9.2) Цепочка вызовов без рекурсии
В отсутствие рекурсии не было особой необходимости явного введения понятия экземпляра метода, так как во время выполнения существовал только один активный экземпляр. При рекурсии цепочка вызовов может включать два или более экземпляров одного и того же метода. При прямой рекурсии они будут следовать друг за другом:
(рис 9.3) Цепочка вызовов при прямой рекурсии
Например, вызов hanoi(2, s, t, o) непосредственно запустит вызов hanoi(1, s, o, t), который вызовет hanoi(0, s, t, o). В этом состоянии будем иметь три экземпляра процедуры в цепочке вызовов.
Подобная ситуация существует и при
(рис 9.4) Цепочка вызовов при косвенной рекурсии
Все экземпляры метода разделяют его код. Экземпляры различаются не кодом, а контекстом выполнения. Мы уже обращали внимание на то, что для правильно построенных
При изучении того, как стеки поддерживают выполнение программ в современных языках программирования, мы познакомились со структурой данных, представляющей контекст выполнения метода и называемой записью активации.
При рекурсии каждой активации нужен собственный контекст. Так что остаются только две возможности реализации.
| I1 | Мы можем обратиться к динамическому распределению. Всякий раз, когда стартует очередной экземпляр |
| I2 | В целях экономии памяти можно заметить, что не всегда требуется создавать собственную запись активации, – как обычно, вместо сохранения данных можно перейти к их повторному вычислению. Такое возможно, если преобразование контекста обратимо, и разумно, если потери времени менее значимы, чем дополнительная память на хранение контекста. hanoi(n, …) имеет вид hanoi(n-1, …). Вместо того, чтобы хранить n в активационной записи, сохранять значение n - 1 в новой записи, можно, как при статическом распределении, в самом начале отвести память для хранения n. При вызове нового экземпляра значение n уменьшается на 1, а при завершении увеличивается на 1. |
Два подхода не являются исключающими друг друга. Можно использовать подход I2 для элементов контекста, допускающих простую трансформацию, как с аргументом n в методе hanoi(n, …), и создавать запись активации для остальных элементов контекста. Как всегда, решение принимается на основе компромисса "память или время".
Из двух рассмотренных стратегий управления контекстом рассмотрим вначале первую, основанную на явных записях активации.
Подобно записям активации, динамически создаются и объекты в результате выполнения оператора create.
(рис 9.5) Цепочка вызовов и соответствующий стек записей активации
Такая стратегия работы соответствует уже хорошо известной стратегии LIFO "последний пришел – первый ушел", для реализации которой применяется структура данных – стек. Стек записей активации задает цепочку вызовов, что показано на следующем рисунке.
Мы уже ранее встречались со стеком записей активации – он назывался стеком вызовов, сохраняющим историю вызовов методов во время выполнения. Если вы программируете на языке, поддерживающем рекурсию, то создание стека вызовов выполняется компилятором. Сейчас же мы посмотрим, как это можно сделать самому.
Вам может понадобиться явный стек записей активации, если по каким-либо причинам вы захотите написать итеративный вариант
Заметьте, обе трансляционные схемы вызова и возврата требуют оператора goto для перехода в нужную точку кода. Это прекрасно при работе с машинным кодом, но при работе с языком высокого уровня такого перехода стараются избежать, и в языке goto просто нет. В этом случае приходится временно написать имитацию goto и промоделировать его подходящими структурными средствами.
Давайте посмотрим, как эта схема работает для тела процедуры hanoi с ее двумя рекурсивными вызовами. Будем использовать стек записей активации, называемый просто stack:
stack: STACK [RECORD]
Вспомогательный класс RECORD задает запись активации:
note
description: "Данные, связанные с экземпляром метода"
class RECORD create
make
feature — Инициализация полей
make (n: INTEGER; c: INTEGER; s, t, o: CHARACTER)
— Инициализация полей записи: count, call, source, target, other.
do
count := n ; call := c; source := s ; target := t ; other := o
end
feature — Access
count: INTEGER.
— Число дисков.
call: INTEGER
— Идентифицирует рекурсивный вызов: 1 – первый вызов, 2 – второй.
source, target, other: CHARACTER
— Стержни.
end
(вместо полноценного класса можно было бы использовать кортеж). Экземпляр класса представляет контекст вызова: число перемещаемых дисков (count), три стержня в порядке их использования в вызове, и call, задающее, первый или второй
hanoi (n: INTEGER; source, target, other: CHARACTER)
do
if n > 0 then
hanoi (n–1, source, other, target) — Первый вызов
move (source, target)
hanoi (n–1, other, target, source) — Второй вызов
end
end
Мы задействуем стек записей активации для реализации нерекурсивной версии процедуры, временно использующей goto:
iterative_hanoi (n: INTEGER; source, target, other: CHARACTER)
local — Нам необходимы локальные переменные, представляющие аргументы
— последовательных вызовов:
count: INTEGER
x, y, z, t: CHARACTER
call: INTEGER
top: RECORD
do — Инициализация локальных переменных:
count := n; x := source; y := target; z := other
start: if count > 0 then
— Трансляция hanoi (n–1, source, other, target):
stack.put (create {RECORD}. make (count, 1, x, y, z))
count := count – 1
t := y ; y := z ; z := t
goto start
after_1: move(x, y )
— Трансляция hanoi (n–1, other, target, source):
stack.put (create{RECORD}.make(count, 2, x, y, z))
count := count – 1
t := x ; x := z ; z := t
goto start
end
— Трансляция возврата:
after_2: if not stack.is_empty then
top := stack.item – Вершина стека
count := top.count
x := top.source ; y := top.target ; z := top.other
call := top.call ; stack.remove
if call = 2 then
goto after_2
else
goto after_1
end
end
— Отсутствует предложение else: программа завершается тогда и
— только тогда, когда стек пуст.
end
Тело процедуры iterative_hanoi получено из рекурсивной процедуры hanoi систематическим применением техники исключения рекурсии.
| D1 | Для каждого аргумента вводится локальная переменная. В примере используется простое соглашение о наименовании стержней: x для source и так далее. |
| D2 | Соответствующей локальной переменной присваивается значение аргумента. Дальнейшая работа выполняется над локальной переменной. Это необходимо, поскольку процедура не может изменять значения аргументов (n:= new_value; – некорректно). |
| D3 | Задать метку (здесь start) первому оператору исходного текста процедуры (после инициализации локальных переменных, добавленной в пункте D2). |
| D4 | Ввести еще одну локальную переменную, здесь call, со значениями, идентифицирующими различные рекурсивные вызовы в теле. Здесь есть два рекурсивных вызова, так что call имеет два возможных значения, произвольным образом заданные как 1 и 2. |
| D5 | Добавить метки, здесь after_1 и after_2, к операторам, непосредственно следующим за каждым рекурсивным вызовом. |
| D6 | Заменить каждый n на n -1 и выполняет обмен значений other и target; |
| D7 | В конце процедуры добавляются операторы, которые завершают выполнение процедуры, только когда стек пуст, а в противном случае:
call;call. |
Эта общая схема применима к исключению рекурсии в любой рекурсивной программе, выполняемой как самим программистом в собственных целях, так и разработчиками трансляторов.
Мы теперь рассмотрим возможность ее упрощения, включая удаление goto. Нам понадобится более глубокое понимание структуры программы. В то же время убедитесь, что вы хорошо понимаете этот "грубый" вариант исключения рекурсии.
(рис 9.6) Питер Наур и Джим Хорнинг (2006)
Летом 1961 года я пригласил прочитать лекцию в Лос-Анджелесе малоизвестного ученого из Дании. Его звали Питер Наур, и темой его лекции был новый язык программирования Алгол 60. Когда пришло время вопросов, мужчина, сидевший рядом со мной, встал и сказал: "Мне кажется, что в ваших слайдах есть ошибка".
Питер был озадачен: "Нет, я так не думаю. В каком слайде?"
"В том, на котором показано, что программа вызывает саму себя. Реализовать это невозможно".
Питер был озадачен еще больше: "Но мы же реализовали язык полностью и пропустили все примеры через наш компилятор".
Мужчина сел, но продолжал бормотать: "Невозможно! Невозможно!"
Я подозреваю, что не один он в зале думал так же.
В то время общепринятой практикой было
Говоря о независимом изобретении понятия стека вызовов, Хорнинг, видимо, имеет в виду Фридриха Бауэра из Мюнхена, который использовал термин Keller (
(рис 9.7) Фридрих Бауэр (2005)
Код, данный выше, в сравнении с исходным рекурсивным вариантом выглядит громоздким. Действительно, для серьезного рекурсивного алгоритма итеративная версия никогда не будет выглядеть столь же элегантной, как рекурсивная. Но мы попытаемся приблизиться к этому эталону, пересмотрев источники компиляции.
goto конструкциями структурного программирования.Последние два случая упрощений могут быть также важны для улучшения производительности, поскольку операции над стеком требуют и времени, и памяти.
В примере с Ханойской башней первым делом устраним торчащие как заноза операторы goto. Чтобы абстрагироваться от лишних деталей кода, запишем тело процедуры iterative_hanoi в виде:
INIT
start: if count > 0 then
SAVE_AND_ADAPT_1
goto start
after_1: MOVE
SAVE_AND_ADAPT_2
goto start
end
after_2: if not stack.is_empty then
RETRIEVE
if call = 2 then goto after_2 else goto after_1 end
end
Здесь SAVE_AND_ADAPT_1 представляет сохранение информации в стеке и изменение значений перед первым вызовом, SAVE_AND_ADAPT_2 – то же для второго вызова, call, MOVE – базисную операцию переноса, INIT – инициализацию локальных переменных значениями аргументов.
Ранее, при обсуждении вопроса избавления от goto подобный пример уже был рассмотрен. Еще раз проанализировав его, нетрудно понять, что наша программа может быть записана с циклами, но без goto:
from INIT until over loop
from until count <= 0 loop
SAVE_AND_ADAPT_1
end
from stop := stack.is_empty until stop loop
RETRIEVE
stop := (stack.is_empty or (call /= 2))
end
over := (stack.is_empty and (call = 2))
if not over then MOVE ; SAVE_AND_ADAPT_2 end
end
И этот вариант можно упростить, удалив, в частности, булевскую переменную stop:
from INIT until over loop
from until count = 0 loop SAVE_AND_ADAPT_1 end
from call := 2 until stack.is_empty or call = 1 loop RETRIEVE end
over := (stack.is_empty and (call = 0))
if not over then MOVE ; SAVE_AND_ADAPT_2 end
end
Упрощения являются результатом анализа возможных значений переменных.
count никогда не может стать отрицательной величиной из-за предусловия, требующего его положительности, и условия завершения вычислений, то вполне законно заменить тест count <= 0 на тест count = 0.stop заметим, что значение call может быть только 1 или 2, так что допустимо заменить тест call /= 2 на тест call = 1. После чего установим начальное значение call = 2, так что это условие будет учитываться для второй и последующих итераций, если таковые будут.Стандартная техника, позволяющая уменьшить затраты на операции над стеком по вталкиванию и выталкиванию элементов, основана на том, что нет необходимости хранить контекстную информацию, а позже получать ее, если алгоритму эта информация больше не нужна. В частности, это происходит при рекурсивном вызове, который является последней операцией, выполняемой экземпляром рекурсивной программы.
Это упрощение применимо к примеру hanoi. Второй SAVE_AND_ADAPT_2, или, более точно, единственная информация, которую требуется сохранить, – это значение call, так как при возврате необходимо анализировать это значение.
Хороший компилятор может обнаружить хвостовую рекурсию и применить эту оптимизацию для улучшения производительности рекурсивного алгоритма.
В случае с hanoi устранение хвостовой рекурсии может и не проводиться, так как существует другая, более мощная оптимизация, почти полностью устраняющая необходимость в стеке, с которой мы вскоре познакомимся. Но все же следует освоить на практике оптимизацию, связанную с хвостовой рекурсией, удалив операции, в которых нет необходимости.
Использование стека для хранения значений перед вызовом и получение их после завершения вызова – это техника по умолчанию, которая работает во всех случаях; но мы уже видели ранее, что существует альтернатива данному подходу – обращение преобразования аргументов. В случае с hanoi обращение возможно для всех аргументов.
count:= count - 1, имеет очевидное обращение: count:= count + 1.swap23 – для первого вызова и swap12 – для второго, где swapij означает операцию обмена между стержнями с номерами i и j. Понятно, что эта трансформация обратима, более того, swapij является собственным обращением, поскольку двойной обмен восстанавливает исходное состояние.Так что, фактически, нет необходимости хранить в стеке ни count, ни x, y, z. Достаточно при достижении
Стек остается необходимым, но только для записи и получения call. Упрощение становится еще существеннее, если вспомнить, что call имеет только два значения: 1 и 2. Но ничто не мешает нам изменить соглашение и рассматривать их как булевские значения 1 и 0. Тогда можно применить стек, содержащий булевское значение. Более того, если допустимо ограничить высоту стека, то вместо стека можно использовать единственную целочисленную переменную, скажем, s (в современных компьютерах целочисленные переменные могут иметь длину в 64 бита). Тогда операции над стеком моделируются операциями над целым s, рассматриваемым как строка битов:
s = 1 — Пуст ли стек?
s := 1 — Инициализация пустого стека
s := 2*s — Втолкнуть 0 (сдвиг влево на один разряд строки битов)
s := 2*s + 1 — Втолкнуть 1 (сдвиг влево на один разряд строки битов с
— приписыванием 1)
b := s \\ 2 — Получить (в b) значение с вершины стека
— (\\ остаток от деления нацело)
s:= s // 2 — Удалить значение с вершины стека
— (// - деление нацело – сдвиг вправо)
Вот результат выполнения некоторой последовательности таких операций.
| Оператор | Цель | Результат | Бинарное представление s (часть нулей слева опущена) |
|---|---|---|---|
s:= 1 |
— Начать с пустого стека | s = 1 | 1 |
s:= 2*s |
— Втолкнуть 0 | s = 2 | 10 |
s:= 2*s + 1 |
— Втолкнуть 1 | s = 5 | 101 |
s:= 2*s + 1 |
— Втолкнуть 1 | s = 11 | 1011 |
s:= 2*s |
— Втолкнуть 0 | s = 22 | 10110 |
s:= s // 2 |
— Вытолкнуть | s = 11 | 1011 |
b:= s \\ 2 |
— Прочитать элемент вершины | b = 1 |
В последнем столбце показано бинарное представление целого. Если нумеровать разряды в этом представлении справа налево, начиная с 0, то единица в разряде $$k$$ имеет значение $$2^k$$. Значение 0 в самом правом разряде означает, что число четное, 1 – нечетное. Когда такое представление задает стек булевских значений, вершиной стека является самый правый разряд. Пустой стек задается значением $$s$$, равным 1.
Техника использования единственного целого числа для задания стека булевских значений может безопасно использоваться, когда гарантируется, что размер стека не превосходит длины целого в битах. В примере с Hanoi проблемы не возникает, поскольку $$2^{63}$$ или даже $$2^{31}$$ – число, задающее количество ходов, столь велико, что компьютеру не справиться с вычислениями за разумное время.
В результате обсуждений приходим к более простой и эффективной форме алгоритма iterative_hanoi с аргументами n, source, target, other:
Хотя полученная программа является результатом систематических трансформаций, а не программой, которую вы бы написали с самого начала (рекурсия яснее и проще), интересно проследить за ее выполнением, сравнивая с оригинальной рекурсивной версией, а особенно – с бинарным деревом выполнения, представленным в начале этой лекции и показывающим выполнение как инфиксный обход дерева:
(рис 9.8) Обход бинарного дерева задачи Hanoi
В алгоритме можно выделить три компонента.
| H1 | Самый левый в глубину – идти насколько возможно вниз, влево, пока не достигнешь листа. У листьев значение n = 0 (count в этой версии), хотя на предыдущих рисунках дерево заканчивалось на 1, поскольку на нулевом уровне ничего не происходит. |
| H2 | Возврат вверх. Если вы возвращаетесь из правого поддерева, то продолжаете идти вверх, поскольку это означает завершение второго рекурсивного вызова, а следовательно – и завершение работы текущего экземпляра процедуры. |
| H3 | Поднявшись вверх по левой ветви, выполняем посещение корня – перенос диска из x на y, а потом идем вниз по правой ветви. |
Все это повторяется, пока, придя справа (H2), не обнаружим, что стек пуст.
При спуске вниз (H1, H3) уменьшается count и выполняется обмен y и z, если идем слева (H1), и обмен x и z, если идем справа (H3). При возврате назад (H2) восстанавливаются исходные значения, увеличивая count и выполняя подходящий обмен в зависимости от того, справа или слева вы пришли. Анализ вершины стека, хранящей значение call, позволяет понять, откуда мы пришли в узел – слева (первый вызов) или справа (второй вызов).
| Activation | Активация | Activation record | Запись активации |
| Alpha-beta | Альфа-бета | Backtracking | Перебор с возвратами |
| Binary tree | Бинарное дерево | Call chain | Цепочка вызовов |
| Depth-first | Первый в глубину | Direct recursion | Прямая рекурсия |
| Indirect recursion | Непрямая ( |
Inorder | Инфиксный |
| Instance (of a routine) | Экземпляр (программы) | Iterative | Итеративный |
| Minimax | Non-creative | Не творческий | |
| Postorder | Постфиксный | Preorder | Префиксный |
| Recursion | Рекурсия | Recursive | Рекурсивный |
| Recursive definition | Рекурсивное определение | Traversal | Обход |
Дайте точные определения терминам словаря.
Является ли определение "рекурсивного определения" рекурсивным?
Для каждого приведенного в этой лекции метода поиска в бинарных деревьях перепишите объявление (если требуется), допуская возможность множественного вхождения элемента item в дерево.
Напишите компилятор и интерпретатор элементарного языка программирования. Используйте приемы, обсуждаемые в предыдущих лекциях. Решение должно использовать рекурсию. Чтобы избежать проблем с конкретным синтаксисом, ваш инструментарий должен иметь дело непосредственно со структурами данных, а не с текстом программы.
Наш маленький язык, назовем его АСТ ("
integer.Типичная программа на АСТ приведена здесь с учетом конкретного синтаксиса, хотя он и не является частью определения языка:
assign
x := 3
y := 5
x := 2*(x + (y // 3))
then
print x
print z
end
В результате выполнения этой программы должно быть напечатано одно значение – 8.
Синтаксис конкретной программы является одним из возможных выборов. Вполне возможно, например, вместо слова then использовать ключевое слово print. Печать переменных можно задавать списком без повторения print.
Напишите множество классов, включающее PROGRAM, ASSIGNMENT, PRINT, EXPRESSION. Методы этих классов, включающие процедуры создания, должны позволять построить абстрактное синтаксическое дерево, задающее АСТ-программу.
PROGRAM процедуру write_out, которая выполняет текстуальное представление АСТ-программ в том виде, как оно дано в примере. Выполните программу из шага 2 и убедитесь в корректности полученного результата. Подсказка: вам необходима рекурсивная процедура обхода, подобная той, которая рассматривалась в данной лекции.interpret PROGRAM, который выполняет программу и вырабатывает ожидаемый результат. Запустите ее на данном примере и проверьте результат выполнения.compile в классе PROGRAM, которая АСТ-программу преобразует в программу на Терминологическое замечание. Результатом шага 5 является реанализатор – unparser, который создает текст программы по внутреннему представлению, такому как абстрактное синтаксическое дерево, выполняя операцию, обратную тому, что делает классический анализатор – parser.
Напишите версию put для бинарного дерева поиска, используя цикл, а не рекурсию.
Подсказка: источником вдохновения может служить реализация метода has.
Сохраняя предположения (список остановок известен своей первой ячейкой типа STOP, остальные остановки доступны через повторное применение next), перепишите функцию reversed, используя рекурсию вместо цикла (смотри также следующее упражнение).
Напишите рекурсивную функцию для обращения связного списка (аргумент и результат должны быть типа LINKED_LIST[G]). Сведите к минимуму манипуляции с указателями и приблизьтесь, насколько возможно, к стилю функции reversed, приведенному как пример программирования на Haskell. Проанализируйте временную и
Адаптируйте общий алгоритм перебора с возвратами так, чтобы он сохранял историю ранее исследованных позиций и удалял любой путь, ведущий к такой позиции. Можете предположить, что PATH имеет запрос position, определяющий терминальную позицию пути.
Адаптируйте общий алгоритм перебора с возвратами так, чтобы он не исследовал пути длиннее, чем path_cutoff – заданное целое число.
(Это упражнение не требует программирования, но предполагает проведение математического анализа)
Для последовательных аппроксимаций $$H_i$$ графа функции, связанной с Ханойской башней (параграф 5.7: "Башни снизу вверх"), определите:
Рассмотрим рекурсивный алгоритм обхода бинарного дерева: вы можете выбрать префиксный, инфиксный или постфиксный порядок обхода.
(Это упражнение требует доступа к компилятору, например, С или С++, с поддержкой оператора goto)
Реализуйте и протестируйте прямую итеративную трансляцию процедуры hanoi в ее начальном варианте, используя goto и стек без оптимизации.
goto, основанную на стеке версию Ханойской башни.goto.Мы видели, что реализация рекурсии требует обращения преобразования аргументов рекурсивного вызова. Стек является одним из возможных путей решения этого требования. Используя подходящие приемы обращения, реализуйте обход бинарного дерева, например, в инфиксном порядке, без рекурсии и без стека, за исключением, возможно, стека булевских значений (или, эквивалентно, бита в каждом узле).
Подсказка: временно переопределите связи дерева, сохраняя информацию о том, откуда пришли в узел.
Контр-подсказка: решение можно найти, набрав при поиске в Интернете слова Deutsch, Shorr или Waite (имена авторов известного алгоритма, основанного на этой идее). Не делайте этого! Спроектируйте алгоритм самостоятельно, затем посмотрите ссылки, если пожелаете.
(Это упражнение ссылается на последнюю лекцию)
Сформулируйте определение транзитивного замыкания как рекурсивное определение.
(Это упражнение требует знания основ линейной алгебры)
Рассмотрим
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.