Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Рекурсивные объявления функций - часть 2
Опираясь на это наблюдение, существует два основных подхода для толкования рекурсивных соглашений о функциях, т.е. для того, чтобы рекурсивно объявленным идентификаторам функций однозначным образом предписать отображение:
·
индуктивное толкование;
· толкование через равенство фиксированной (неподвижной) точки.
В обоих толкованиях однозначно устанавливается, какое отображение предписывается идентификатору с помощью рекурсивного объявления.
До того как последует точное описание смысла рекурсивного объявления, сначала необходимо дать краткое разъяснение способа того, как можно обращаться операционально с рекурсивным объявлением
Подстановку правой части объявления функции вместо функции называют расширением
или развертыванием (англ. unfold) вызова рекурсивной функции. Через повторное применение правила расширения можно при известных обстоятельствах редуцировать рекурсивный вызов к значению. Идея вычисления через расширение является ведущей линией для операционального смысла рекурсивных объявлений функций.
При толковании с помощью функционала мы соединяем с рекурсивным объявлением функцию, которую связываем с объявляемым идентификатором.
