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



             

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


B) . C))".

x = ((A . B) . C))

Имя "Левейший" теперь работает как известное название функции, которое может быть вызвано в форме:

( Левейший ' ((A . B) . C) )

Таблица 4.1. Схема вывода результата формы с рекурсивной функцией.

Вычисляемая формаОчередной шагРезультат и комментарииВход в рекурсиюПервый шаг рекурсииВторой шаг рекурсииТретий шаг рекурсииВыход из рекурсии
(Левейший (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 Значение функции получено и вычисление завершено

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


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