Рекурсивные функции: определение и исполнение
- Определения могут быть рекурсивны.
Как правило рекурсивное применение функций должно быть определено в комплекте с нерекурсивными ветвями процесса. Основное предназначение условных выражений - рекурсивные определения функций.
Для примера рассмотрим функцию, выбирающую в списке самый левый атом:
Алг Левейший ( список x) арг x нач если Atom (x) то знач := x иначе знач := Левейший (Car (x)) кон
Пример 4.10. запись на алгоритмической нотации (html, txt)
Новая функция "Левейший" выбирает первый атом из любого данного.
(DEFUN Левейший (x) (COND ((ATOM x) x) (T (Левейший (CAR x))) ))
Пример 4.11. эквивалентная Лисп-программа (html, txt)
Если x является атомом, то он и является результатом, иначе функцию "Левейший" следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь специальной функции COND, выбираемая по тождественно истинному значению встроенной константы T.
Определение функции "Левейший" рекурсивно. Эта функция действительно работает в терминах самой себя. Важно, что для любого S-выражения существует некоторое число применений функции CAR, после которого из этого S-выражения обязательно выделится какой-нибудь атом, следовательно процесс вычисления функции всегда определен, детерминирован, завершится за конечное число шагов. Можно сказать, что для определенности рекурсивной функции следует формулировать условие ее завершения.
Введенные обозначения достаточны, чтобы пронаблюдать формирование значений и преобразование форм в процессе исполнения функциональных программ.
Рассмотрим вычисление формы:
(APPLY (DEFUN Левейший (x) (COND ((ATOM x) x) (T (Левейший (CAR x))) ))) (QUOTE ((A . B) . C) ) )
Функция "APPLY" применяет функцию "Левейший", полученную как результат "DEFUN", к ее аргументам – константе "((A . B) . C)".
DEFUN дает имена обычным функциям, поэтому фактический параметр функции "Левейший" будет вычислен до того как начнет работать ее определение и переменная "x" получит значение "((A .
Такие функции называют частичными. Их определения должны включать в себя ветвления для проверки аргументов на принадлежность фактической области определения функции - динамический контроль. Условные выражения не менее удобны и для численных расчетов.
(Запись на алгоритмической нотации)
алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон
(эквивалентная Лисп-программа)
(DEFUN Абс(LAMBDA (x) (COND ((< x 0 )(- x)) (T x))))
Пример 4.12. Абсолютное значение числа. (html, txt)
(Запись на алгоритмической нотации)
алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := 1 иначе знач := N * ФАКТОРИАЛ (N - 1) кон
(эквивалентная Лисп-программа)
(DEFUN Факториал (LAMBDA (N) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ) ) )
Пример 4.3. Факториал неотрицательного числа. (html, txt)
Это определение не завершается на отрицательных аргументах.
Функция, которая определена лишь для некоторых значений аргументов естественной области определения, называется частичной функцией.
(Запись на алгоритмической нотации)
алг НОД ( цел x, y) арг x, y нач если (x < y) то знач := НОД ( y, x) инес Остаток (y, x) = 0 то знач := x иначе знач := НОД (Остаток (y, x), x) кон
остаток [x, y] - функция, вычисляющая остаток отделения x на y.
(эквивалентная Лисп-программа)
(DEFUN НОД (LAMBDA (x y) (COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) )
Пример 4.14. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция "Остаток". (html, txt)
Как и любое S-выражение, символьные представления функций могут быть значениями аргументов - функциональные аргументы.
Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, DEFUN.
Далее мы построим определение универсальной функции EVAL, позволяющее вычислять значения выражений, представленных в виде списков, - правило интерпретации выражений.
Формально для перехода к практике нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями:
- аргументы функций как правило вычисляются в порядке их перечисления,
- композиции функций выполняются в порядке от самой внутренней функции наружу до самой внешней,
- представление функции анализируется до того как начинают вычисляться аргументы, т.к. в случае специальных функций аргументы можно не вычислять,
- при вычислении лямбда-выражений связи между именами переменных и их значениями, а также между именами функций и их определениями, накапливаются в так называемом ассоциативном списке, пополняемом при вызове функции и освобождаемом при выходе из функции.
| (Declare Спецификации ) | Специфицирует переменные – dynamic-extent, ftype, ignorable, ignore, inline, optimize, special, type |
| (Defmacro Название Параметры Определение ) | Глобальное опреление макроса |
| (Defun Название Параметры Форма ) | Определение функции |
| (Function Название ) | #’ – выдает названную функцию |
| ( Lambda Параметры Определение ) | Конструирует бузымянную функцию |
B) . C))".
x = ((A . B) . C))
Имя "Левейший" теперь работает как известное название функции, которое может быть вызвано в форме:
( Левейший ' ((A . B) . C) )
| (Левейший (QUOTE ((A . B) . C))) | Выбор определения функции и | (COND ((ATOM x) x)(T (Левейший (CAR x))) ) |
| Выделение параметров функции | (QUOTE ((A . B) . C)) | |
| (QUOTE ((A . B) . C)) | Вычисление аргумента функции | X = ((A . B) . C) |
| (COND ((ATOM x) x)(T (Левейший (CAR x))) ) | Перебор предикатов: выбор первого | (ATOM x) |
| (ATOM x) | Вычисление первого предиката | Nil = "ложь",т.к. X – не атом. Переход ко второму предикату |
| T | Вычисление второго предиката | T = "истина" – константа. Переход к выделенной ветви |
| (Левейший (CAR x)) | выделение параметров функции | (CAR x) |
| (CAR x) | Вычисление аргумента функции | X = (A . B) Рекурсивный переход к редуцированному аргументу |
| (COND ((ATOM x) x)(T (Левейший (CAR x))) ) | Перебор предикатов: выбор первого | (ATOM x) |
| (ATOM x) | Вычисление первого предиката | Nil = "ложь", т.к. X – не атом. Переход ко второму предикату |
| T | Вычисление второго предиката | T = "истина" – константа. Переход ко второй ветви |
| (Левейший (CAR x)) | выделение параметров функции | (CAR x) |
| (CAR x) | Вычисление аргумента функции | X = A Рекурсивный переход к редуцированному аргументу |
| (COND ((ATOM x) x) (T (Левейший (CAR x))) ) | Перебор предикатов: выбор первого | (ATOM x) |
| (ATOM x) | Вычисление первого предиката | T – т.к. X теперь атом Преход к первой ветви |
| X | Вычисление значений переменной | A Значение функции получено и вычисление завершено |
Такие функции называют частичными. Их определения должны включать в себя ветвления для проверки аргументов на принадлежность фактической области определения функции - динамический контроль. Условные выражения не менее удобны и для численных расчетов.
(Запись на алгоритмической нотации)
алг АБС( цел x) арг x нач если (x < 0) то знач := - x иначе знач := x кон
(эквивалентная Лисп-программа)
(DEFUN Абс(LAMBDA (x) (COND ((< x 0 )(- x)) (T x))))
Пример 4.12. Абсолютное значение числа.
(Запись на алгоритмической нотации)
алг ФАКТОРИАЛ ( цел N) арг N нач если (N = 0) то знач := 1 иначе знач := N * ФАКТОРИАЛ (N - 1) кон
(эквивалентная Лисп-программа)
(DEFUN Факториал (LAMBDA (N) (COND ((= N 0 ) 1 ) (T ( * N (Факториал (- N 1 ))) ) ) ) )
Пример 4.3. Факториал неотрицательного числа.
Это определение не завершается на отрицательных аргументах.
Функция, которая определена лишь для некоторых значений аргументов естественной области определения, называется частичной функцией.
(Запись на алгоритмической нотации)
алг НОД ( цел x, y) арг x, y нач если (x < y) то знач := НОД ( y, x) инес Остаток (y, x) = 0 то знач := x иначе знач := НОД (Остаток (y, x), x) кон
остаток [x, y] - функция, вычисляющая остаток отделения x на y.
(эквивалентная Лисп-программа)
(DEFUN НОД (LAMBDA (x y) (COND ((< x y) (НОД y x)) ((= (остаток y x ) 0 ) x ) (T (НОД (остаток y x) x )) )) )
Пример 4.14. Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел при условии, что определена функция "Остаток".
Как и любое S-выражение, символьные представления функций могут быть значениями аргументов - функциональные аргументы.
Базис элементарного Лиспа образуют пять функций над S-выражениями CAR, CDR, CONS, ATOM, EQ и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, DEFUN.
Далее мы построим определение универсальной функции EVAL, позволяющее вычислять значения выражений, представленных в виде списков, - правило интерпретации выражений.
Формально для перехода к практике нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями:
- аргументы функций как правило вычисляются в порядке их перечисления,
- композиции функций выполняются в порядке от самой внутренней функции наружу до самой внешней,
- представление функции анализируется до того как начинают вычисляться аргументы, т.к. в случае специальных функций аргументы можно не вычислять,
- при вычислении лямбда-выражений связи между именами переменных и их значениями, а также между именами функций и их определениями, накапливаются в так называемом ассоциативном списке, пополняемом при вызове функции и освобождаемом при выходе из функции.
| (Declare Спецификации ) | Специфицирует переменные – dynamic-extent, ftype, ignorable, ignore, inline, optimize, special, type |
| (Defmacro Название Параметры Определение ) | Глобальное опреление макроса |
| (Defun Название Параметры Форма ) | Определение функции |
| (Function Название ) | #’ – выдает названную функцию |
| ( Lambda Параметры Определение ) | Конструирует бузымянную функцию |
