Проблемы с семантикой рекурсии

В случае не рекурсивных вызовов семантика обращений строилась с помощью замены обращения модифицированным телом процедуры. Фактически мы описывали её (семантику) как построение некоторого выражения – программы на базовом Паскале. Этот способ работал и для кратных обращений.

Использование процедуры процедурой:

P2

P1

P

Чётко выделялись два этапа:

1) Построение выражения;

2) Его вычисление.

В этом случае такое дерево не может быть построено.

Вспомним алгоритм вычисления выражения. Как показал наш анализ, для того, чтобы вычислить значение выражения, необязательно строить его полностью. Более того, мы не обязаны для этого обходить всё дерево.

Пример: Если значение левого терма – ноль, а операция у нас – умножение, то значение правого терма вычислять не нужно.

Любая рекурсия связана с последовательным построением и вычислением выражения. Действительно, в любом случае можно считать, что рекурсивный вызов выполняется в случае истинности некоторого условия. При каждом рекурсивном вызове вычисляется выражение, и дерево достраивается лишь в случае его истинности.

Таким образом, любой рекурсивный алгоритм эквивалентен построению и обходу некоторого дерева.

P1

P2

P2

P1

P1

P2

1 2 B₁⁺ B₂⁺ if B₁ then P₁ if B₂ then P₂

1 2 2

B₁⁺ B₂⁺ B₂⁺

В случае двух вызовов получаем бинарное дерево.

КЛП-обход или стековый обход.

Описали семантику рекурсии с помощью циклов. Теоретически возможно описание семантики циклов через рекурсию.

s, B(s)=false

while B do S(s)

S, while B do S, B(s)=true

Теоретически можно программировать без циклов в терминах лишь рекурсии.

Функциональным программированием называется программирование в терминах рекурсивного определения функций. Логическим программированием: языки основаны на рекурсивном определении булевых функций (предикатов).

Дата добавления: 2014-01-05