Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Схема для рекурсивного объявления функции
Рекурсивному объявлению fct f = (m1x1, …, mkxk) n: E соответствует схема (формуляр) вычислений, что можно разъяснить на примере.
Пример (формуляр для рекурсивно объявленной функции факториала).
fct fас = (nat x) nat:
else if x=0 then 1
x * fac(x - 1) fi
В вычислениях с помощью формуляров для каждого рекурсивного вызова (каждого развертывания рекурсии) прикладывается новый аналогичный формуляр. Управление с помощью формуляра может происходить по принципу штабеля: как только должен вычисляться рекурсивный вызов функции, на вершину штабеля кладется новый элемент формуляра, по которомy и продолжаются вычисления. Начальные, но еще не полностью выполненные, формуляры при этом оказываются в штабеле ниже. Как только формуляр, который соответствует рекурсивному вызову, будет полностью выполнен (т.е. искомое значение функции будет зарегистрировано) вычисление вызова переносится в предыдущий формуляр, а данный формуляр убирается со штабеля. Тогда можно продолжить вычисление по формуляру, который находится на верху штабеля. Так вычисления продолжаются до тех пор, пока не будут выполнены все формуляры.
Управление выполнением формуляров по принципу штабеля является типичным для обработки на машине рекурсивно объявленных функций. Этот способ обработки в связи с машинной реализацией рекурсий связывается с термином "стек" (аналог штабеля).
