Сборник задач по курсу «Теория вычислительных процессов» (стр. 9 )

Пример 7.1. Рассмотрим рекурсивную программу, определенную для любого положительного целого числа X:

F(Х) ≡ IF  Х = 1 THEN 1

       ELSE  OTHERWISE X•F(Х–1)

Чтобы понять, как работает такая программа, выполним ее для некоторого конкретного значения аргумента X. Например,

F(4) = 4 • F(3)        [Так как условие 4 = 1 ложно, то F(4)=4•F(3).

       Теперь нужно вычислить F(3), т. е. рекурсивно

       обратиться к F.]

       = 4 • 3 • F(2)        [Так как при вычислении F(3) условие 3 = 1 ложно,

               то F(3) = 3•F(2).]

       = 4 • 3 • 2 • F(1)  [Так как условие 2 = 1 ложно, то F(2) = 2•F(1).]

       = 4 • 3 • 2 • 1        [Так как условие 1 = 1 истинно, то F(1) = 1.]

       = 24 = 4 !

Далее мы докажем, что F(Х) = Х! для любого положительного целого числа X.

Нужно заметить, что при выполнении вычислений для рекурсивной программы мы можем сталкиваться с неоднозначностями, которые требуют уточнений. Например, в приведенных вычислениях при обращении F(X1, F(X2, X3)) мы отдать предпочтение вычислениям, связанным с внутренним либо с внешним обращением. Соответственно предполагаем, что F(X2, X3) должно быть вычислено прежде, чем мы продолжим вычисления, относящиеся к внешнему обращению к F, или наоборот. Значение функции F(X1, F(X2, X3)) останется тем же, хотя последовательность вычислений отлична от предыдущей. Однако вполне возможно, что одна последовательность не будет заканчиваться, хотя другая последовательность закончится. Можно доказать, что если к одним и тем же аргументам некоторой рекурсивной функции применять две различные последовательности ее вычисления, то результат будет одним и тем же при условии конечности этих последовательностей.

Чтобы сделать наш язык программирования точным, нам нужно задать правила вычислений для программ, определяющие последовательность вычислений. Будем считать, что правило вычислений отдает предпочтение самому левому и самому внутреннему обращению. Другими словами, в любой из моментов вычислений первым начинает вычисляться левое и внутреннее обращение (для простоты далее везде будем опускать слово «самое») к функции F, все аргументы которой уже не содержат F. Это правило – не обязательно наилучшее, иногда оно может приводить к неоканчивающейся последовательности вычислений, хотя другое правило дало бы конечную последовательность (пример 4.3). Однако во многих существующих языках программирования используется правило вычислений, подобное описанному выше. Кроме того, большинство рассматриваемых нами программ заканчивается при любых значениях аргументов независимо от того, какие правила вычислений мы используем, а следовательно, и результат в любых случаях будет одинаковым. Поэтому для определенности будем считать, что предпочтение отдается левому внутреннему обращению.

Упражнения

1. Рассмотрите следующую рекурсивную функцию (функцию Аккермана), применимую для любой пары неотрицательных целых чисел X1, Х2:

А(Х1, Х2)  ≡  IF  X1 = 0  THEN Х2 + 1

ELSE  IF  Х2=0  THEN  А(Х1–1, 1)

ELSE  OTHERWISE  А(Х1–1, А(Х1, Х2–1))

Проследите, как выполняется такая программа при следующих аргументов:

а) А(1, 2);        б) А(1, 1);        в) А(2, 1).

Применяйте при этом правило левого внутреннего обращения.

2. Проследите, как проходят процессы вычисления функции Аккермана из упражнения 1, если вместо правила «левое внутреннее» использовать правило «левое внешнее» и покажите, что результаты будут те же.

3. Возьмите рекурсивную программу, применимую к любой паре неотрицательных целых X1, Х2:

F(Х1, Х2) ≡ IF  X1 =0  ТНЕN 0
ELSE  OTHERWISE  F(0, F(Х1, Х2))

Проследите за вычислением F(1, 1), используя два различных правила вычислений. По первому правилу нужно стараться сначала заканчивать вычисления, относящиеся к внешнему обращению, а по второму правилу – отдавать предпочтение самому внутреннему обращению. Проанализируйте результаты.

4. Рассмотрите следующую рекурсивную программу, применимую к любой паре целых X1, Х2:

F(Х1, Х2) ≡ IF  X2 =0  ТНЕN 0
ELSE  OTHERWISE  F( F(Х1, Х2 – X1), X2 – 1).

Вычислите F(1, 1) и F(0, 1), используя правило вычисления «левое внутреннее» и «левое внешнее». Отметим, что если вычисления заканчиваются при правиле вычисления «левое внутреннее», то они заканчиваются и дают тот же результат и при правиле «левое внешнее». Однако при использовании правила «левое внешнее» процесс может и не закончиться, хотя при другом правиле он заканчивается. Далее мы всегда будем использовать правило«левое внутреннее».

5. Дана функция F (X, Y) ≡ IF  X = 0  Λ  Y = 0  ТНЕN 0
ELSE  IF  X = 0  Λ  Y ≠ 0  ТНЕN Y – 1
ELSE  IF  X ≠ 0  Λ  Y = 0  ТНЕN X – 1
ELSE  OTHERWISE  F( F(Х – 1, Y), F(Х, Y – 1)).

Выпишите последовательность вычислений для случаев:  а) F(1, 1);  б) F(2, 1).

Рекурсивные функции работы со списками

Как было сказано выше, рекурсивные программы особенно удобны в тех случаях, когда речь идет о данных, структура которых определяется рекурсивно, каковыми являются, например, списки. Рассмотрим примеры работы со списками. В таких программах мы используем некоторое подобие «лисповской» нотации. По этой нотации список – набор объектов, отделенных друг от друга пробелами и заключенных в квадратные скобки [ ]. Объектами, входящими в такие списки, являются атомы или другие списки. Атом – строка буквенно-цифровых символов, не содержащая пробелов. Мы будем считать, что атомы должны начинаться с одной из букв А, В, С, D или F, а переменные – с букв, отличных от этих букв. Например, [А В С] – список из трех элементов, каждый из которых есть атом; [А [В А [С]] В С] – список, в котором (на верхнем уровне) четыре элемента. Второй элемент – сам список [В А [С]]. Третий элемент этого списка – опять список [С]. Для пустого списка, т. е. списка, не содержащего ни одного элемента, мы выделяем специальное имя NIL. Кроме того, мы будем использовать следующие проверки и функции:

1. Проверка = может применяться как к спискам, так и к числам. Например, проверка [А В] = [А В] истинна, а проверки [А В] = [В А] ложна.

2. Проверка АТОМ (X) применима к любым объектам, будь то атомы или списки и дает значение TRUE, если X – атом или пустой список, иначе – FALSE.

3. Функция CAR (L) применима к любому непустому списку. В качестве результата выступает первый элемент этого списка: CAR ( [А В С] )  дает А.

4. Функция CDR(L) применима к любому непустому списку. Результатом является список, полученный из L путем отбрасывания первого его элемента. Примеры: CDR ( [А В С] ) дает [В С], CDR ( [В] )дает NIL (или [ ] ).

5. Функцию CONS(Х, L) можно применять к любому списку L и любому X, будь то атом или список. В результате получается новый список: первый его элемент есть X, а потом идут элементе списка L. Так CONS ( А, [В С] ) дает [А В С].

Пример 7.2. Рекурсивная программа МЕМВЕR (Х, L) определяет, является ли X элементом списка L (на верхнем уровне):

МЕМВЕR (Х, L)  ≡  IF  L = NIL ТНЕN  FALSE

ЕLSЕ  IF  Х = САR (L)  ТНЕN TRUE

ЕLSЕ  ОТНЕRWISЕ  МЕМВЕR (X, CDR (L))

Проследим, как идет процесс вычислений по такой программе для фактических аргументов С и [А В С D]:

МЕМВЕR (С, [А В С D]) = МЕМВЕR (С, [В С D]) = МЕМВЕR (С, [С В]) = TRUЕ

Вычисление значения функции при фактических аргументах С и [А В [С D]]:

МЕМВЕR (С, [А В [С D]]) = МЕМВЕR (С, [В [С D]] ) = МЕМВЕR (С, [[С В]] ) =
= МЕМВЕR (С, NIL) = FALSE

Упражнения

6. Рекурсивная программа APPEND (L1, L2), добавляет список L1 к списку L2, другими словами, в этом списке, состоящем из двух, элементы первого стоят перед элементами второго:

APPEND (L1, L2)  ≡  IF L1 = NIL  ТНЕN L2
ЕLSЕ  OTHERWISE  CONS (CAR (L1),
АРРЕND (CDR(L1), L2))

Проследите, как идет процесс вычислений при различных парах аргументов:

а) АРРЕND ([А В], [С D]);         б) АРРЕND ([[А]], [В С]); 

с) АРРЕND ([А В], NIL);         г) АРРЕND (NIL, [А В С]);

д) АРРЕND ([А В [С]], [D]);        е) АРРЕND ([А В], [[С] D]).

7. Для рекурсивной программы, применимой к любым двум спискам L1, L2:

INT (L1, L2)  ≡  IF  L1 = NIL  ТНЕN  NIL

ЕLSЕ  IF МЕМВЕR (САR (L1), L2)  ТНЕN

CONS (САR (L1), INT (CDR (L1), L2))

ЕLSЕ  ОТНЕRWISЕ  INT (CDR (L1), L2)

Выпишите последовательность  вычислений для случаев

а) INT (NIL, [А В С]);         б) INT ([B D C], [А В С]); 

в) INT ([[B D] C], [А В D]).        г) INT ([С В А], [А В С]);

Тема 8. ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ
РЕКУРСИВНЫХ ПРОГРАММ

Структурная индукция

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

1) доказать, что программа работает правильно для простейших данных (аргументов функции);

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

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