Рекурсивное уравнение

11 Лекция

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

Когда внутри <блока> процедуры присутствуют одноименные процедурные операторы, функция частного значения процедур может быть применена внутри ее самой для того, чтобы получить значение внутреннего процедурного оператора как части внешнего процедурного оператора. Каждая процедура, чей текст достается из состояния выполнения, может содержать процедурные операторы, для которых также требуется получить их текст из состояния выполнения и т.д. В общем случае, существуют только две возможности для этого повторяющегося процесса.

Первая. К конце концов может случится, что тексты для всех процедурных операторов получены, последние не содержат процедурные операторов и значение может быть вычислено без усложнений.

Второе. Процедурные операторы образуют цикл, в котором внутри текста процедуры встречается тот же самый текст. Это может происходить явно, если процедура рекурсивно вызывает сама себя, или неявно, если процедура X вызывает Y, а Y вызывает X.

Таким образом, программа должна содержать конечное число процедурных идентификаторов, и у нас есть две возможности – устранение процедурных операторов через их вычисление (получение текста) и приведение рекурсии к итерации.

Вычисление значения рекурсивных процедурных вызовов.

Определение в разделе 9.2.5. подходит для случаев без рекурсии. Вычисление выполняется от процедурного оператора к вызываемому тексту процедуры, в конце концов все вызовы заменяются текстом процедур, значение которого может быть вычислено непосредственно.

Случай с рекурсией более интересен. Значение не может быть вычислено напрямую. Потому что любая попытка вычисления значения текста процедуры с рекурсивным вызовом будет снова требовать получения этого текста и вычисления его значения и этот процесс не имеет конца.

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

Рассмотрим программу P

PROGRAM LengthOfInput(INPUT, OUTPUT);

{Подсчитывает остаток от деления на 10 количества символов

в первой строке INPUT, используя символы 0-9}

VAR

Nc, Number: CHAR;

{Включить PROCEDURE NextDigit(VAR D1:CHAR);

D1 заменяется на его следующий

в последовательности 01234567890123…}

PROCEDURE Count;

BEGIN {Count}

IF EOLN

THEN

Number := ‘0’

ELSE

BEGIN

READ(Nc);

Count;

NextDigit(Number);

END

END; {Count}

BEGIN {LengthOfInput}

Count;

WRITELN(Number)

END. {LengthOfInput}

Предположим, что INPUT будет <†TW†>

Состояние s, в котром Count будет вызвана первый раз

s = {INPUT <††, †TW†R>, OUTPUT <††, ††W>, Nc?, Number?}

Процедурный идентификатор и присоединенный к нему текст исключим в интересах экономии места.

В тексте Count(s) выполняется часть ELSE, и когда случается внутренний вызов Count, состояние выполнения будет:

s = {INPUT <†T†, †W†R>, OUTPUT <††, ††W>, NcT, Number?}

Третий вызов процедурного оператора произойдет в состоянии выполнения

s = {INPUT <† TW†, ††R>, OUTPUT <††, ††W>, NcW, Number?}

Сейчас в операторе IF выполнится часть THEN и следующий вызов процедурного оператора не произойдет и после третьего вызова состояние выполнения будет

s = {INPUT <† TW†, ††R>, OUTPUT <††, ††W>, NcW, Number0}

После выполнения второго вызова будет

s = {INPUT <† TW†, ††R>, OUTPUT <††, ††W>, NcW, Number1}

Исходный процедурный оператор завершается с результатом

s = {INPUT <† TW†, ††R>, OUTPUT <††, ††W>, NcW, Number2}

И следовательно

P(<†TW†>) = <†2†>

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

Правило верификации рекурсивных процедур

Также как не всегда возможно раскрывать операторы WHILE пока они не завершатся, или увидеть общий случай так, чтобы можно было подсчитать количество итераций, так и не всегда возможно развернуть рекурсию. Может так случиться, что выражения, управляющие рекурсией слишком сложны для анализа и требуются другие методы. Для операторов WHILE было достаточно развернуть цикл однажды и получить рекурсивное уравнение. Для рекурсивных процедур такое уравнение может быть получено напрямую. В программе существуют как минимум два процедурных оператора: исходный оператор вызова процедур и рекурсивный вызов.

Вычисляем значение процедурного оператора в операторе BEGIN процедуры LengthOfInput:

Count = BEGIN IF NOT EOLN THEN …

= {<s, t>: EOLN(s) = TRUE, t = Number := ‘0’ (s)}

{<s, t>: EOLN(s) = FALSE, t = (READ(Nc)CountNextDigit(Number))(s)}

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

Если верить тому, что мы написали в комментарии LengthOfInput, значение Count – функция f, определяемая условным присваиванием

(EOLN -> Number := ‘0’) | (NOT(EOLN) -> Number, Nc := m mod 10, c)

где m – длина строки будущего INPUT до следующего конца строки, а c – последний символ перед маркером конца строки.

Заменяя Count на f в рекурсивном уравнении, рассмотрим два варианта, с пустой и непустой строкой будущего L, до первого символа конца строки.

Вариант 1. L пуста. Тогда для состояния s, левая часть рекурсивного уравнения в f, будет

f(s) = t, где t такое же как s, за исключением того, что значение Number - символ, представляющий 0 mod 10, т.е. 0

Правая часть первым множеством, где EOLN(s) = TRUE и в этом множестве s образует пару с таким же t. То есть в случае 1 f удовлетворяет рекурсивному уравнению.

Вариант 2. L не пуста. Пусть длина L будет k > 0, а последний символ с. Тогда для состояния s левая часть рекурсивного уравнения в f будет

f(s) = t, где t такое же как s за исключением того, что значение Number - символ, представляющий k mod 10 а значение Nc – с.

Правая часть покрывается вторым множеством, где EOLN(s) = TRUE и в значение, образующее пару с s, будет

t = (READ(Nc)CountNextDigit(Number))(s)

t может быть вычислено с помощью таблиц трассировки

Вариант 2.1.

	Условие	IN2	Nc	Number
READ(Nc) f NextDigit…	L †† Θ(Λ(L)) = /	L Λ(L)	Θ(L) c	0 1

Условие: (L ††) AND (Θ(Λ(L)) = /)

Присваивание: Number, Nc := ‘1’, c

Условие выполняется только когда L – 1-строка, а поскольку L – 1-строка, Θ(L) = c, потому что он единственный символ в L (до маркера конца строки).

Таким образом, не учитывая происходящее с INPUT, условное присваивание будет

(длина(L) = 1 -> Number, Nc := ‘1’, c)

Вариант 2.2.

	Условие	IN2	Nc	Number
READ(Nc) f NextDigit…	L †† Θ(Λ(L))  /	L Λ(L)	Θ(L) c	длина(Λ(L)) mod 10 (длина(Λ(L)) mod 10 + 1) mod 10

NextDigit увеличивает Number за исключением значения 9, которое становится 0. Это поведение описывается добавлением функции mod 10 – остаток от деления на 10.

Условие: (L ††) AND (Θ(Λ(L))  /)

Присваивание: Number, Nc := (длина(Λ(L)) mod 10 + 1) mod 10, c

Условие может быть упрощено наблюдением, что L должна быть как минимум 2-строкой, потому что Λ(L) не должен начинаться с маркера конца строки.

Таким образом, не учитывая происходящее с INPUT, условное присваивание будет

(длина(L) > 1 -> Number, Nc := (длина(Λ(L)) mod 10 + 1) mod 10, c)

Отметим, что

длина(Λ(L)) mod 10 + 1 = длина(L) mod 10

для всех длина (L ) >= 1 и применение второй функции mod не дает эффекта.

Случай 2.1 и 2.2 могут быть объединены :

(длина(L) >= 1 -> Number, Nc := длина(Λ(L)) mod 10, c)

Это точно то, что было получено для левой части, таким образом, f удовлетворяет рекурсивному уравнению в случае 2. Было показано, что функция f построенная из комментария в LengthOfInput, удовлетворяет рекурсивному уравнению для Count в данной программе.

Однако, как и в случае с оператором WHILE, требуется осторожность, поскольку рекурсивное уравнение не единственное необходимое условие. Может случится, что функция удовлетворяет рекурсивному уравнению, но не является значением процедуры, из которой было выведено это уравнение.

Например, процедура

PROCEDURE Forever;

BEGIN

Forever

END;

чье рекурсивное уравнение будет

Forever = Forever

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

По аналогии со случаем для оператора WHILE, это предлагает правило верификации: функция частного значения для процедурного оператора, включающего рекурсивный вызов это решение рекурсивного уравнения, область определения которого согласуется с областью определения процедуры.

Пусть P будет процедурный оператор для процедуры без параметров с одним рекурсивным вызовом, имеющим рекурсивное уравнение P = M(P). M(P) представляет результат вычисления функции частного значения <блока> процедуры, в котором P встречается только один раз. Вычисление должно производиться до тех пор, пока явно не встретится P как в примере выше. Функция f = P если и только если:

1. domain(f) = domain(P), и

2. f является решением рекурсивного уравнения.

Доказательство правила верификации рекурсивных процедур

Правило верификации применяется к процедурному оператору P процедуры без параметров и с одним рекурсивным вызовом, имея рекурсивное уравнение P = M (P). Функция f = P если и только если

1. domain(f) = domain(P), и

2. f является решением рекурсивного уравнения.

Направление доказательства “только если” тривиально, потому что P удовлетворяет обоим условиям, следовательно, удовлетворяет и f = P.

Для другого направления примем условия 1) и 2). Рассмотрим любое s  domain(P). Когда правая сторона рекурсивного уравнения применяется к s, к тому времени как будет применена собственно P, состояние выполнения может быть изменено (другими операторами в M(P)) в s’. При вычислении P(s’) снова используется правая часть рекурсивного уравнения и продолжается процесс вычисления частей M(P) и замены в правой части рекурсивного уравнения всякий раз, когда P применяется к измененному состоянию выполнения. Процесс не может продолжаться бесконечно, потому что P определено на s, рекурсия должна завершиться. То есть после (скажем, k) замен в правой части рекурсивного уравнения, часть M(P), включающая P не встретится, и вычисление результирующего состояния сможет быть вычислено. То есть, объединяя эти замены в k-местное применение модификации M,

P(s) = (M^k(P))(s) = t,

где при получении состояния t не применялось P.

Теперь рассмотрим написание рекурсивного уравнения в терминах f вместо P. Поскольку f является решением рекурсивного уравнения по условию 2), выполнение k подстановок дает

f(s) = (M^k(f))(s) = t,

то же состояние, что и полученное при использовании уравнения для P, потому что не зависит от применения к исходному состоянию f или P, а только других операторов из M(P).

Таким образом, P(s) = f(s), и поскольку s – определенная точка в их общей области определения, P=f, что и требовалось доказать.

Другой способ охарактеризовать функцию, которая фиксирует значение вызова рекурсивной процедуры, это то, что решение рекурсивного уравнения процедуры, определенно минимально. То есть, F – это функция удовлетворяющая уравнению, которое неопределено так часто как это возможно. (Не существует другой удовлетворяющей уравнению, которая была бы подмножеством F.) Чтобы увидеть, почему это выражение эквивалентно, отметим, что если F имело бы ту же область определения, что и P, F удовлетворял бы правилу верификации, следовательно F = P. Предположим далее, что domain(F) точно меньше, чем domain(P), что существует точка x, для которой P определено, а F нет. Произведем замены в рекурсивном уравнении для P до тех пор пока оно не исчезнет для аргумента x, как было показано выше,

P(x) = y,

где при получении состояния y не применялось P. Но поскольку F удовлетворяет тому же уравнению,

F(x) = y

И потому F определено на x. Тот же аргумент применим к любой точке в domain(P), поэтому последнее решение F имеет эту область определения.

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

Значение процедурного оператора для рекурсивной процедуры должно, следовательно, получаться через нахождение пробной функции, потом верификации. Что это значение с помощью вышеописанного правила. Ситуация похожа на ситуацию с оператором WHILE, рассмотренную в разделе 8.4.2. Однако, правило верификации для оператора WHILE применялось в общем случае, а результат выше ограничен одной рекурсией без параметров. Технические подробности общего случая для рекурсии довольно объемны, поскольку в общем случае могут встречаться несколько рекурсивных выражений одновременно для множественных рекурсий и различные параметры для одной процедуры, если она встречается несколько раз в этих уравнениях.