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

Рекурсия может быть использована для реверсирования строк в подобным образом, как показано в примере

Исходная строка:

†character†

Разбиваем на первую половину и вторую:

†chara† †cter†

Реверсируем полустроки

†arahc† †retc†

Обмениваем реверсированные полустроки

†retc† †arahc†

Объединяем реверсированные полустроки в реверсированную строку

†retcarahc†

И снова неуклюжее разбиение может быть исключено. Предположим, файл был разбит на

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

Исходная строка:

†character†

Разбиваем на полустроки из четных-нечетных

†caatr† †hrce†

Реверсируем полустроки

†rtaac† †ecrh†

Перемешиваем реверсированные полустроки в реверсированную строку

†retcarahc†

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

Эти идеи позволяют нам подготовить следующий проект быстрого рекурсивного реверсирования.

Раздел проекта 2 [DP 2]

PROCEDURE RecursiveReverse(VAR F1: TEXT);

VAR

F2, F3: TEXT;

Ch, Last: CHAR;

BEGIN {RecursiveReverse}

RESET(F1);

IF NOT (EOLN(F1))

THEN

BEGIN

READ(F1, Ch);

IF NOT (EOLN(F1))

THEN {Файл имеет как минимум 2 символа}

BEGIN

{Разбить F1 на F2 и F3 и запоминаем в Last

в какой файл попал последний символ}

RecursiveReverse(F2);

RecursiveReverse(F3);

{Перемешиваем F2 и F3 в F1 начиная с файла

согласно тому, что запомнено в Last}

END

END

END {RecursiveReverse}

Оставшиеся разделы проекта аналогичны тем, что мы подготовили для RecursiveSort.

11.3. Решение задач с помощью рекурсии.

11.3.1. Ханойские башни.

11.3.2. Математическая индукция.

11.3.3. Рекурсивные процедуры для задачи Ханойские башни.

11.4. Исчисление рекурсивных процедур.

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

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

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

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

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