Введение в программирование на Лиспе



             

Рекурсивные функции: определение и исполнение - часть 3


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

(Запись на алгоритмической нотации)

алг АБС( цел 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, позволяющее вычислять значения выражений, представленных в виде списков, - правило интерпретации выражений.




Содержание  Назад  Вперед