Язык Лого

38

Язык Лого
Урок 3: Рекурсии, функции

А. А. ДУВАНОВ,
Ю. А. ПЕРВИН

Все возвращается на круги своей
Выполняя процессу ОКРУЖНОСТЬ
(см. Урок 2 в прошлом номере «Кванта»), Черепаха обжит один полный оборот и оставится. Приятно наблюдайте ее бег на экране дисплея! Поэтому хочется заставить ее покружиться еще и еще. Вот как это можно сделать:

ЭТО КАРУСЕЛЬ :R
ОКРУЖНОСТЬ :R
КАРУСЕЛЬ :R
КОНЕЦ

Эта процедура имеет непrivibuousное описание: в него включен вызов той же самой процедуры. Процедура, вызывающая сама себя, называется рекурсивной, а ее вызов — рекурсей. С рекурсей часто и неожиданно можно встретиться и вдали от уроков информаτικи. Художники любят рисунки-шутки: на рисунке изображен тритель, наблюдающий экран телевизора, на котором виден тритель, взираю-щий на экран … и т. д. Пример «lintературной» рекурсии — знаментийный стишок про попа, у которого была собака.

Вызвав рекурсивную процедуру КАРУСЕЛЬ, можно убедиться в том, что не так уж она и хорошо: она заставляет бедную Черепаху безостановочно бегать по кругу, … пока включена машина.

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

СДЕЛАЙ «СЧЕТЧИК :СЧЕТЧИК+1,
которую следует включить в описание процедуры КАРУСЕЛЬ сразу вслед за вызовом ОКРУЖНОСТЬ :R (выогдавыаетесь, по-видимому, что для правильной работы задуманной программы надо будет в самом начале выполнить команду

СДЕЛАЙ «СЧЕТЧИК 0;
почему?).

А вот для того, чтобы сравнить две величины, потребуется новая

39

команда. Условная команда имеет вид ECЛИ условия [список-1 команд] [список-2 команд]

Стоящее в квадратных скобках списки команд представляют собой одно из двух возможных продолжений программы: в том случае, когда условия, записанное после слова ECЛИ, истинно, выполняются команды первого списка (и пропускается весь второй списк!), и наоборот, если условия ложно, пропускается первый списк и выполняются команды второго списка. Условием (точнее, простым условиям) называют два выражения, соединенные знаками отношений «<», «>», «>=» (большие или равно), «<=» (меньше или равно), «=», «/=» (не равно). Определение таким образом условия может быть либо истинным, либо ложным. Например, условия команда ECЛИ: $R/2 > 3.14*2$ [ВПЕРЕД 50] [НАЗАД 50] сначала вычисляется истинность условия при текущем значении $R$, и получив положительный ответ, посылает Черепаху вперед, а в противном случае — назад.

Допустима сокращенная форма условий команды (с одним списком): ECЛИ условия [список команд]

Тогда в случае истинности условия выполняется команда списка, а если условия ложно, то машина … ничего не делает, а просто переходит к выполнению следующей команды программы, если она есть. Этот форминой команды мы и воспользуемся для решения поставленной задачи, заставляя Черепаху углать по кругу, например, 17 раз. Для этого надо составить описание процедуры

это ПРОГУЛКА :$R$
СДЕЛАЙ «СЧЕТЧИК 0»
КАРУСЕЛЬ :$R$
КОНЕЦ

описание процедуры КАРУСЕЛЬ будет иметь вид

это КАРУСЕЛЬ :$R$
ОКРУЖНОСТЬ :$R$
СДЕЛАЙ «СЧЕТЧИК :СЧЕТЧИК+1»
ECЛИ СЧЕТЧИК<17 [КАРУСЕЛЬ :$R$]
КОНЕЦ

На сея раз процедура КАРУСЕЛЬ, хотя и остается рекурсивной, все же вызывается не всякий раз, а только если значение переменной СЧЕТЧИК не превыходит 17. Заметьте, что в процессе ПРОГУЛКА пришлось предустотть установку нулевого началаного значения счетчика. Такая программа после завершения своей работы оставит переменную СЧЕТЧИК равной 17. Переменные, не являющиеся параметрами процедуры и используемые как внутри процедуры, так и в вызывающей ее программе под одним и тем же именем и с теми же значениями, называются глобальными (ср. с определением локальной переменной на предыдущем уровне). Переменная СЧЕТЧИК в последнем примере глобальная. Поэтому программист должен помнить, что вызов процедуры ПРОГУЛКА может изменить значение глобальной переменной СЧЕТЧИК, существовавшее до вызова. Уйти от этого ограничения можно, сделав СЧЕТЧИК параметром процедуры: параметры всегда локальны. Такая процедура имеет описание

это КАРУСЕЛЬ :$R$ :СЧЕТЧИК
ОКРУЖНОСТЬ :$R$
СДЕЛАЙ «СЧЕТЧИК :СЧЕТЧИК+1»
ECЛИ :СЧЕТЧИК<17 [КАРУСЕЛЬ :$R$]
КОНЕЦ

Тепер процедура ПРОГУЛКА возвращает не нужна. Вызов КАРУСЕЛЬ 50 0

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

Задание 1. Перепишите процедура КАРУСЕЛЬ так, чтобы Черепаха могла обегаться любое заданное число кругов.

На прошлом уроке мы видели, что всегда, когда известно число повторяемых одинаковых действия, можно воспользоваться командой ПОВТОРИ. Значит, можно это сделать и в нашем рис. 1.

40

несложном задании — прогулке Черепахи по окружности.

Задачка 2. Еще раз перешите проедуру КАРУСЕЛЬ, исключив рекурсию и воспользовшись командой цикла.

«Рекурсивный» рисунок на с. 38 программровать мы не будем. Но часть его — прямугольники внутри прямугольников (рис. 1) — запросимировать легко:

ЭТО РЕКУРСИЯ :СТОРОНА
ПОВТОРИ 2 [В :СТОРОНА П 90 В
1.5 * :СТОРОНА П 90]
НР В :СТОРОНА / 2 П 90 В
1.5 * :СТОРОНА / 2 Л 90 Р
СДЕЛАЙ «СТОРОНА :СТОРОНА * 0.4
РЕКУРСИЯ :СТОРОНА
КОНЕЦ

Эта процедура будет безстановочно рисовать вложенные прямугольники. Самым последним (но бесконечно повторяемым!) изображается прямугольник с минимальным значением СТОРОНА, при котором еще выполняется условие СТОРОНА > 1. А как добиться остановки процедуры?

Рисунки 2, а—z выполены рекурсивной процедурой СПИРАЛЬ с двумя параметрами.

Задачка 3. Следайте описание процедуры СПИРАЛЬ, воспроизводящей рисунки 2, а—z.

Процедуры и функции

Введем понятие предписания как неокоторого приказа, отделного машине в понятной для нее форме. Такие предписания, как ВПЕРЕД, заставляющие машину произвести определенные действия без вычисления результатов, мы будем называть командами, а также, как «+», вычисляющие значения — операции.

Набор встречных команд в Лого относительно неевелик. Описывая процедуры, мы объявляем машине новые команды. Например, можно ввести команду
КВАДРАТ α
рисушую квадрат со стороны α (α —арифметическое выражение). Для этого достаточно знать в памяти компьютера описание

ЭТО КВАДРАТ :A
ПОВТОРИ 4 [ВПЕРЕД :A ВПРАВО 90]
КОНЕЦ

Выполняя команду (или процедуру), ЭВМ осуществляет некоторые действия — передвигает Черепаху, выводит сообщения на экран, организует повторения. Выполняя операцию ико, машина не только делает предписанные действия, но и (это главное!) вырабатывает в качестве результата неокоторое единственное значение (сумму, разность, …).

Мы уже пользовались арифметическими операциями: сложением, вычитанием, умножением, делением. Для более сложных математических выкладок требуют операции, вычисляющие значения функций. В Лого также операции записьюются в виде имя α, (1)
где «имя» — идентификатор функции, α — выражение, на которое воздействует функция, т. е. операнд операции. Операции и функции могут иметь не один, а несколько операндов.

Вот несколько имен, резервированных в Лого для обозначения элементов функций: SIN — синус, COS — косинус, TAN — tangенс, ARCTAN — арктигенс, SQRT — квадратный корень, RND — функция, генерирующая случайное число.

Например, выражение
$$\frac{\mathrm{tg} 2 + \sqrt{\sin a + 2}}{2}$$

перешется на Лого в виде
$$\frac{TAN 2 + SQRT(SIN :A + 2)}{2}.$$

Выражение RND можно использовать в качестве случая случайных чисел из интервала (0; N—1).

Для знакомых операций «+», «—», «», «/» в Лого также предисмотреть имена: СЛОЖИ для «+», ВЫЧТИ для «—», УМНОЖЬ для «», РАЗДЕЛИ для «/». Эти операции можно также записьать в форме (1) с двумя параметрами-операндами:
имя αβ (α и β —арифметические выражения).

41

Так, выражение $x+1$ можно перепись в виде
СЛОЖИ :x1
Для записи выражения (2) имеется эквивалент:
РАЗДЕЛИ СЛОЖИ TAN 2 SQRT
СЛОЖИ SIN :A 2 2

(расстояние внешательно соответствие форм записи (3) и (5)!). Запись выражений в форме (4), когда имя операции ставится перед операдими, называется префиксной, в отличие от более привчной, инфиксной записи, когда имя (знак) операции ставится между операдими. Например, $2+3$ — инфиксная форма записи,
СЛОЖИ 2 3 — префиксная форма записи той же операции.

Задание 4. Перепишите выражение
$$\frac{\sqrt{\sin^2 a + \cos^2 a}}{a+1}$$

на Лого, используя префиксную форму записи.

Форма записи операций (1) и (4) делает их разчително положими на команды и вызовы процедур. Однако программа СЛОЖИ :A :B (равно как и :A+:B) вызовет недоумение ЭВМ — что делать с полученным результатом? Чтобы избежать ошибок, надо помнить, что операции можно использовать только в выражениях; например:

Diagram

Процедура ПРЕДЕЛ используетстроенную в Лого функцию квадратного корня SQRT. Однако в Лого можно создавать и свои собственные функции, точно так же, как это делается при описании процедур. Единственное отличие описаний функций от описаний процедур — это обязательное присутствие в описании функций команды ВЕРНИ $\alpha$.

Эта команда возвращает в вызывающий программу в качестве результата значения выражения $\alpha$.

Итак, описание пользовательской (создаваемой программистом) функций имеет вид

Рис. 3. Рис. 4.

Рис. 5.