11. Циклы и рекурсия

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

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

11.1 while		Заставляем код повторяться.
11.2 Рекурсия
11.3 Упражнения с циклами

11.1 while

while --- это особая форма, которая проверяет правда ли что значение, которое вернуло вычисление ее первого аргумента, является ли истинным или ложным. Это похоже на то, что делает интерпретатор Лиспа с if; однако то, что интерпретатор делает затем, несколько отличается.

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

Шаблон для выражения while выглядит следующим образом:

(while проверка-истинна-ложь тело...)

До тех пор, пока проверка-истина-ложь в выражении while будет возвращать истину, тело всего выражения будет повторно вычисляться. Этот процесс называется циклом, поскольку интерпретатор Лиспа снова и снова повторяет один и тот же код, как будто аэроплан делает петлю. Когда в результате вычисления проверки-истинна-ложь возвратится ложь, то интерпретатор Лиспа не вычисляет оставшуюся часть выражения while и как говорят --- `выходит из цикла'.

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

Значение, возвращаемое после вычисления while --- это значение проверки-истина-ложь. Интересное следствие, что сам цикл while после завершения без ошибок вернет nil или ложь --- не важно сколько раз он сам исполнялся, 1 раз или 100 или совсем ни разу. Выражение while, которое вычислилось успешно, никогда не вернет значение истину! Это значит, что while всегда используется ради побочных эффектов, то есть именно за последовательное повторное вычисление выражений тела цикла while. Именно это имеет смысл. Не то, что сам акт цикла, а последовательности которые происходят когда выражения цикла последовательно вычисляются.

11.1.1 Цикл while и список
11.1.2 Пример: print-elements-of-list		Uses while, car, cdr.
11.1.3 Цикл с увеличивающимся счетчиком
11.1.4 Цикл с уменьшающимся счетчиком

11.1.1 Цикл while и список

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

Простой способ проверить имеет ли список какие-нибудь элементы --- это вычислить список; если там нет элементов, то есть --- это пустой список, то вернется пустой список (), который является тем же самым, что и nil или ложь. С другой стороны если список имеет какие-нибудь элементы, то после вычисления вернутся эти элементы. Поскольку Лисп считает все, что не nil, истиной, то список с какими-нибудь элементами считается истиной и выражения в теле цикла while будут вычисляться.

Например, вы может связать переменную пустой-список с nil вычислив следующее выражение setq:

(setq пустой-список ())

После вычисления этого выражения, вы можете вычислить переменную пустой-список обычным образом, поместив курсор после символа и нажав C-x C-e; в эхо-области появится nil:

пустой-список

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

(setq животные '(жираф газель лев тигр)) животные

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

(while животные ...

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

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

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

(setq животные (cdr животные))

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

Шаблон для цикла while, в котором используется функция cdr для того, чтобы постепенно проверка-истина-ложь наконец-то вернула ложь и цикл закончился, выглядит следующим образом:

(while проверить-пуст-ли-список тело... установить-список-в-cdr-списка)

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

11.1.2 Пример: print-elements-of-list

Функция печать-элементов-списка иллюстрирует использование цикла while со списком.

Этой функции требуется несколько строк для вывода. Поскольку эхо-область вмещает только одну строку, то мы не сможем показать как она работает, тем же способом, как мы показывали функции в прошлом, вычисляя их не выходя из буфреа Info. Вместо этого, вам надо будет скопировать необходимые выражения в ваш буфер `*scratch*' и вычислить их там. Вы можете скопировать выражения поставив метку в начале региона с помощью сочетания клавиш C-SPC (set-mark-command), затем переместив курсор в конец региона и скопировав регион с помощью M-w (copy-region-as-kill). В буфере `*scratch*' вы можете вставить выражения назад, с помощью C-y (yank).

После того, как вы скопировали выражения в буфер `*scratch*', последовательно вычислите их. Обязательно вычислите последнее выражение --- (печать-элементов-списка), нажав C-u C-x C-e, то есть задав префикс аргумент к eval-last-sexp. Это заставит вывести результат вычисления в буфер `*scratch*' а не в эхо-области. (В противном случае вы увидите в эхо-области что-то подобное: ^Jжираф^J^Jгазель^J^Jлев^J^Jтигр^Jnil, где каждый символ `^J' означает символ новой строки, которая в буфере `*scratch*' будет разделять слова на отдельные строки. Вы можете вычислить выражения прямо в буфер Info, для того, чтобы посмотреть что получится).

(setq животные '(жираф газель лев тигр)) (defun печать-элементов-списка (list) "Печатать каждый элемент СПИСКА на отдельной строке." (while list (print (car list)) (setq list (cdr list)))) (печать-элементов-списка животные)

Когда вы последовательно вычислите эти три выражения в буфере `*scratch*', то в нем там будет напечатано:

жираф газель лев тигр nil

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

11.1.3 Цикл с увеличивающимся счетчиком

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

Проверка может быть выражением таким, как (< счетчик нужное-число), которое вернет t, если значение счетчик меньше чем нужное-число повторов, и nil, если счетчик равен или больше чем нужное-число. Выражение которое увеличивает счетчик может быть простым выражением setq, таким как (setq счетчик (1+ счетчик)), где 1+ --- встроенная в Emacs Лисп функция которая добавляет 1 к своему аргументу. (Выражение (1+ счетчик) имеет тоже самое значение, что и (+ счетчик 1), но для человека первое выражение более понятно.)

Шаблон для цикла while управляемого увеличивающимся счетчиком выглядит следующим образом:

установить-счетчик-к-начальному-значению (while (< счетчик нужное-число) ; проверка-истинна-ложь тело... (setq счетчик (1+ счетчик))) ; инкремент, увеличение

Необходимо отметить, что вам надо будет присвоить счетчик начальное значение; обычно оно равно 1.

Пример с увеличивающимся счетчиком
Части определения функции
Составляем определение функции

Пример с увеличивающимся счетчиком

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

* * * * * * * * * *

(Около 2500 лет назад, Пифагор и другие начали изучение теории чисел, рассматривая именно такие вопросы.)

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

Ясно, что вам надо будет добавить числа от 1 до 7. Есть два способа сделать это --- начать с самого маленького числа, единицы и добавлять последовательно 1, 2, 3, 4 и так далее; или начать с самого большого числа и добавлять вниз по уменьшению: 7, 6, 5, 4 и так далее. Из-за того, что оба механизма демонстрируют обычные способы используемые в циклах, мы создадим два примера, один считающий вверх и другой считающий вниз. В первом примере мы начнем с 1 и будем добавлять 2, 3, 4 и так далее.

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

Например, вместо того чтобы складывать все камни сразу, вы можете сложить число камней в первой строке, 1, с числом камней во второй строке, 2, и затем добавить к итоговой сумме число камней в третьей строке, 3. После этого, вы можете добавить число камней в четвертой строке, 4, к сумме первых трех строк, и так далее.

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

Части определения функции

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

Во вторых, мы знаем что функции нужен будет аргумент --- этот аргумент будет обозначать число строк в треугольнике. Его можно назвать число-строк.

Наконец нам понадобиться переменная, которую мы будем использовать как счетчик. Мы могли бы назвать ее счетчик, но лучше ее назвать номер-строки. Поскольку этот счетчик считает строки и программы, то надо давать максимально понятные имена.

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

Обе переменные --- итог и число-строк используются только внутри функции, поэтому они могут быть объявлены как локальные переменные, с помощью let, где им будут присвоены начальные значения. Ясно что начальным значением итог должен быть 0. А начальное значение число-строк должно быть равно 1, поскольку мы начнем считать с первой строки. Это значит, что выражение let будет выглядеть следующим образом:

(let ((итог 0) (номер-строки 1)) тело...)

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

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

(<= номер-строки число-строк)

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

(setq итог (+ итог номер-строки))

В этом выражении новому значению итог присваивается сумма предыдущего значение итог и число камней в текущей строке.

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

Существующая в Emacs Lisp функция 1+ добавляет 1 к своему аргументу, поэтому переменная текущая-строка, может быть увеличена с помощью следующего выражения:

(setq текущая-строка (1+ текущая-строка))

Составляем определение функции

Мы уже рассмотрели части определение функции; сейчас нам надо только сложить их вместе.

Вначале возьмем выражение while:

(while (<= текущая-строка число-строк) ; проверка-истина-ложь (setq итог (+ итог текущая-строка)) (setq текущая-строка (1+ текущая-строка))) ; увеличение

Вместе со списком переменных выражения let, этот код почти завершает тело определения функции. Однако для завершения всей картины все же требуется нанести последний штрих.

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

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

Схематично, функция выглядит следующим образом:

(defun имя-функции (список-аргументов) "документация..." (let (список-переменных) (while (проверка-истина-ложь) тело-while... ) ... ) ; Здесь необходимо последнее выражение.

Результат вычисления let --- это то что вернет defun, поскольку let не вложена в какой-нибудь внешний список кроме самой defun. Однако, если while --- это последний элемент выражения let, то функция всегда будет возвращать nil. А это совсем не то что мы хотим! В самом деле, то что мы хотим получить --- это значение переменной итог. Его можно получить просто поместив этот символ, как последний элемент списка let. Он будет вычислен после того, как будут вычислены все предыдущие элементы let, в том числе и цикл while, а это значит, что там будет храниться правильный итоговый результат.

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

(let (список-пер) (while (проверка-истина-ложь) тело-while... ) итог)

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

(defun треугольник (число-строк) ; Версия с ; увеличивающимся счетчиком. "Считает число камней в треугольнике. Первая строка один камень, вторая два камня, третья строка три камня, и так далее. Аргумент---ЧИСЛО-СТРОК." (let ((итог 0) (текущая-строка 1)) (while (<= текущая-строка число-строк) (setq итог (+ итог текущая-строка)) (setq текущая-строка (1+ текущая-строка))) итог))

После того как вы установили треугольник, вычислив определение функции, вы можете опробовать ее. Ниже приведены два примера:

(треугольник 4) (треугольник 7)

Сумма первых четырех чисел --- 10, а сумма первых семи чисел --- 28.

11.1.4 Цикл с уменьшающимся счетчиком

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

В этом случае проверяемым условием цикла может быть выражение такое как, например (> счетчик 0), которое возвращает t, если значение счетчик больше нуля и nil, если значение счетчик меньше или равно нулю. Выражение, которое уменьшает счетчик с каждым выполнением цикла может быть простым выражением setq, например, (setq счетчик (1- счетчик)), где 1- встроенная в Emacs Lisp функция, которая вычитает 1 из своего аргумента.

Шаблон для уменьшающего цикла while выглядит следующим образом:

(while (> счетчик 0) ; проверка-истина-ложь body... (setq счетчик (1- счетчик))) ; уменьшение

Пример с уменьшением счетчика
Части определения функции
Составляем определение функции

Пример с уменьшением счетчика

Чтобы продемонстрировать цикл с уменьшающимся счетчиком, мы перепишем функцию треугольник, таким образом, чтобы счетчик уменьшался.

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

Аналогично, чтобы найти число камней в треугольнике из 7 строк, сложим число камней в седьмой строке, с числом камней в предыдущей строке --- 6 и затем добавим к итоговой сумме число камней в пятой строке --- 5, ну и так далее. Как и в предыдущем примере, в каждом сложении участвуют только два числа --- общее число камней в уже добавленных строках и число камней в текущей строке. Этот процесс сложения двух чисел будет повторятся снова и снова, до тех пор пока больше не останется строк для добавления.

Мы знаем с какого числа камней начать: число камней в последней строке равно числу строк. Если треугольник состоит из семи строк, то число камней в последней строке равно 7. Еще мы знаем сколько камней в предыдущей строке: их на один меньше, чем число камней в текущей строке.

Части определения функции

Мы начнем работу с объявления трех переменных: числа строк в треугольнике; числа камней в текущей строке; и итогового числа камней, которое нам и надо вычислить. Эти переменные можно назвать число-строк, текущая-строка и итог, соответственно.

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

Это значит, что начало выражения let будет выглядеть следующим образом:

(let ((итог 0) (текущая-строка число-строк)) body...)

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

(setq итог (+ итог текущая-строка))

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

Поскольку число камней в предыдущей строке на единицу меньше чем число камней в текущей строке, то для вычисления числа камней в предыдущей строке можно использовать встроенную в Emacs Lisp функцию 1-. Это делается в следующем выражении:

(setq текущая-строка (1- текущая-строка))

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

(while (> текущая-строка 0)

Составляем определение функции

Соединив все рассмотренные выражения вместе, у нас получиться следующее определение функции:

;;; Первая версия с уменьшающимся счетчиком. (defun треугольник (число-строк) "Найти числи камней в треугольнике." (let ((итог 0) (текущая-строка число-строк)) (while (> текущая-строка 0) (setq итог (+ итог текущая-строка)) (setq текущая-строка (1- текущая-строка))) итог))

Эта функция работает, как и надо.

Однако выясняется, что одна из локальных переменных, текущая-строка не нужна!

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

Ниже приведена вторая версия функции, котороя выглядит более понятно:

(defun треугольник (число) ; Вторая версия. "Возвращает сумму чисел от 1 до ЧИСЛО включительно." (let ((итог 0)) (while (> число 0) (setq итог (+ итог число)) (setq число (1- число))) итог))

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

1. Проверки, которая должна возвращать ложное значение после того, как цикл повторился нужное число раз.

2. Главного вычисляемого выражения, которое мы вернем, после того, как цикл повторится нужное число раз.

3. Выражения, где изменяется значение передаваемое в проверку-истина-ложь, так чтобы проверка возвращала ложное значение только после того, как цикл повторился нужное число раз

11.2 Рекурсия

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

Рекурсивная функция обычно содержит условное выражение, которое имеет три части:

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

2. Имя функции.

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

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

Шаблон для рекурсивной функции выглядит следующим образом:

(defun имя-рекурсивной-функции (список-аргументов) "документация..." тело... (if рекурсивная-проверка (имя-рекурсивной-функции выражение-следующего-вызова)))

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

Рекурсивную-проверку иногда называют условием завершения, поскольку она останавливает повторы, когда возвращает ложное значение.

11.2.1 Рекурсия на списке
11.2.2 Рекурсия на месте счетчика		Меняем цикл while на рекурсию.
11.2.3 Пример рекурсии с использованием cond		Пример рекурсии с другим условием.

11.2.1 Рекурсия на списке

Пример цикла while, который печатал элементы списка, можно переписать рекурсивно. Ниже приведен код который делает это, включая выражение присваивающий список переменной животные.

Этот пример надо скопировать в буфер `*scratch*' и там последовательно вычислить каждое выражение. Используйте C-u C-x C-e для того, чтобы вычислить последнее выражение, так, чтобы результат отпечатался в буфере; в противном случае интерпретатор Лиспа сожмет результат в одну строку для отображения в эхо-области.

Расположите курсор сразу за последней закрывающей скобкой функции рекурсивная-печать-элементов, перед комментарием. В притивном случае интерпретатор Лиспа попробует вычислить комментарий.

(setq животные '(жираф газель лев тигр)) (defun рекурсивная-печать-элементов (список) "Печать каждого элемента СПИСОК на отдельной строке. Использует рекурсию." (print (car список)) ; тело (if список ; рекурсивная-проверка (рекурсивная-печать-элементов ; рекурсивный вызов (cdr список)))) ; выражение-следующего-вызова (рекурсивная-печать-элементов животные)

Функция рекурсивная-печать-элементов вначале печатает первый элемент списка --- значение поля CAR списка. Затем, если список не пуст, то функция вызывает сама себя, но при вызове передает в качестве аргумента не весь список, а второй и последующие элементы списка, то есть --- поле CDR списка.

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

Каждый раз, когда функция вызывает сама себя, она при вызове передает аргумент, который короче первоначального списка. В конце концов она вызовет себя задав в качестве аргумента пустой список. Функция nil напечатает пустой список как nil. Затем, в условном выражении проверится значание список. Поскольку сейчас его значение равно nil, то проверка завершится неудачей, и поэтому then-часть вычислятся не будет. И вся функция вернет nil. Поэтому вы увидите nil дважды, когда вы вычислите эту функцию.

Если вы вычислите (рекурсивная-печать-элементов животные) в буфере `*scratch*', то вы увидите следующий результат:

жираф газель лев тигр nil nil

(Первое nil --- это напечатанное значение пустого списка; а второе nil --- это значение которое вернуло вся функция).

11.2.2 Рекурсия на месте счетчика

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

(defun рекурсивный-треугольник (число) "Возвращает сумму чисел от 1 до ЧИСЛО включительно. Использует рекурсию." (if (= число 1) ; рекурсивная-проверка 1 ; then-часть (+ число ; else-часть (рекурсивный-треугольник ; рекурсивный вызов (1- число))))) ; выражение-следующего-вызова (рекурсивный-треугольник 7)

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

Чтобы понять как работает эта функция, давайте рассмотрим что произойдет в при ее вызове с разными аргументами, когда мы передадим в функцию значения 1, 2, 3, или 4.

Первое, что случится если значение аргумента равно 1?

Первое выражение в теле функции --- это выражение if. Оно проверяет равно ли значение переменной число единице; если да, то Emacs вычисляет then-часть выражения if, которое возвращает число 1 в качестве значения функции. (Треугольник состоящий только из одной строки можно сложить из одного камня).

Предположим, что теперь значение аргумента равно 2. В этом случае, Emacs вычислит else-часть выражения if.

Else-часть состоит из сложения, рекурсивного вызова функции рекурсивный-треугольник и уменьшения числа; все это выглядит следующим образом:

(+ число (рекурсивный-треугольник (1- число)))

Когда Emacs вычисляет это выражение, то сначала вычисляется самое внутреннее выражение; затем последовательно вычисляются другие части выражения. Рассмотрим эти шаги более подробно:

Этап 1 Вычисление самого внутреннего выражения.

Самое внутреннее выражение --- это (1- число), поэтому Emacs вначале уменьшает число с 2 до 1.

Этап 2 Вычисление функции рекурсивный-треугольник.

Не имеет значения, что вызов этой функции происходит из нее же самой. Emacs передаст результат Этапа 1 в качестве аргумента при вызове функции рекурсивный-треугольник.

То есть, теперь, Emacs вычислит рекурсивный-треугольник с аргументом равным 1. Это значит, что вычисление рекурсивный-треугольник вернет 1 (как мы уже знаем).

Этап 3 Вычисление значения число.

Переменная число --- это первый элемент списка, который начинается с символа +; его значение равно 2.

Этап 4 Вычисление выражения +.

Выражение + получает два аргумента --- первый от вычисления число (Этап 3) и второй от вычисления рекурсивный-треугольник (Этап 2).

Результат этого сложения --- это сумма 2 плюс 1, то есть будет возвращено число 3 (ведь треугольник из двух строк можно сложить из трех камней).

Аргумент 3

Аргумент 3

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

Этап 1 Вычисление рекурсивной-проверки.

Вначале вычисляется выражение if. Это рекурсивная-проверка, и поскольку она возвратит ложное значение, то будет вычислена else-часть выражения if. (Обратите внимание, что в этом примере, рекурсивная-проверка составлена таким образом, чтобы функция вызывала саму себя только тогда, когда проверка вернет ложное значение, а не тогда, когда она вернет истинное значение).

Этап 2 Вычисление самого внутреннего выражения else-части.

Вычисляется самое внутреннее выражение else-части, которое уменьшает 3 до 2. Это выражение-следующего-вызова.

Этап 3 Вычисление функции рекурсивный-треугольник.

В функцию рекурсивный-треугольник передается число 2.

Мы уже знаем, что произойдет, когда Emacs вычислит функцию рекурсивный-треугольник с аргументом равным 2. Пройдя через рассмотренную нами последовательность вычислений, интерпретатор вернет значение 3.

Этап 4 Вычисление сложения.

Функция + будет вычислена с аргументами 3 и 3; где первый результат получен в результате вычисления функции (рекурсивный-треугольник 2), а второе число было задано, в качестве аргумента при вызове функции.

Это значит, что функция в результате вычисления вернет значение равное 6.

Теперь, когда мы знаем, что произойдет когда функция рекурсивный-треугольник будет вызвана с аргументом равным 3, то становиться ясно, что получится, когда мы вызовем ее с аргументом равным 4:

В рекурсивном вызове, вычисление

(рекурсивный-треугольник (1- 4))

вернет значение вычисления

(рекурсивный-треугольник 3)

а это равно 6, и теперь это значение будет передано в функцию + вместе с аргументом функции равным 4.

Значит вся функция вернет 10.

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

11.2.3 Пример рекурсии с использованием cond

Версия рекурсивный-треугольник представленная ранее была написана с использованием особой формы if. Но ее можно было также написать и с использованием другой особой формы, которая называется cond. Название этой особой формы произошло от сокращения слова `conditional' (6).

Хотя особоя форма cond используется в программах на Emacs Lisp не так часто, как if, но тем не менее она применяется достаточно часто, и поэтому заслуживает отдельного рассмотрения.

Шаблон для выражения cond выглядит следующим образом:

(cond тело...)

где тело состоит из серии списков.

Более подробно, шаблон выглядит следующим образом:

(cond ((первая-проверка-истина-ложь первое-следствие) (вторая-проверка-истина-ложь второе-следствие) (третья-проверка-истина-ложь третье-следствие) ...)

Когда интерпретатор Лиспа вычисляет выражение cond, он вначале вычисляет первый элемент (CAR или проверку-истина-ложь) первого выражения в серии списков внутри тела cond.

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

Если ни одна из проверок истина-ложь не вернет истину, то значением всего выражения cond будет nil.

Переписанная с использованием cond функция треугольник выглядит следующим образом:

(defun треугольник-с-cond (число) (cond ((<= число 0) 0) ((= число 1) 1) ((> число 1) (+ число (треугольник-с-cond (1- число))))))

В этом примере, cond вернет 0, если число меньше или равно 0; вернет 1, если число равно 1, или вычислит выражени треугольник-с-cond (1- число), если число больше 1.

11.3 Упражнения с циклами

• Напишите функцию аналогичную функции треугольник для которой значение камней в каждой строкe которой равно квадрату номера строки. Используете цикл while.

• Создайте функцию аналогичную функции треугольник, в которой вместо операции сложения используется операция умножения.

• Перепишите эти две функции с использованием рекурсии. Перепишите их с использованием особой формы cond.

• Создайте функцию для режима Texinfo, котороя создает индекс в начале каждого параграфа в котором встречается какое-нибудь определение (помеченное как `@dfn'). (В файле Texinfo, `@dfn' означает определение. Для получения дополнительной информации смотрите @xref{Indicating, , Indicating Definitions, texinfo}.)