Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Решение задач с рекурсией.

Программирование с рекурсией.

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

Рекурсивные процедуры в CF Pascal.

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

Новые идеи: рекурсия и ее реализация в CF Pascal.

Решение задач с рекурсией.

Метод семейства задач, рассмотренный в главе 4 подводит нас к рекурсивным решениям. Как показано в семействах программ IFSort и MinSort, в этом подходе для сортировки более длинных строк использовались ранее разработанные подходы для сортировки более коротких строк. Например, в семействе MinSort, MinSort4, которая сортирует 4-строки может быть описана в терминах MinSort3, MinSort5 – в теминах MinSort4 и т.д. Решение для сортировки m-строк – использовать сортировку (m-1)-строк.

Именно эта концепция используется в SelectSort, для m-строки, которую требуется отсортировать, находится минимальный символ и удаляется из строки. Остается (m-1)-строка, которую также обрабатывает SelectSort, получая для дальнейшей сортировки (m-2)-строку, …, 2-строку, 1-строку. Финальная задача, сортировка 1-строки, имеет тривиальное решение.

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

PROCEDURE RSort (VAR F1: TEXT);

VAR

Min: CHAR;

F2: TEXT;

BEGIN {RSort}

RESET(F1);

IF NOT(EOLN(F1))

THEN

BEGIN

REWRITE(F2);

{Положить минимальный из F1 в Min

и копировать другие символы в F2}

WRITE(Min);

{Копировать F2 обратно в F1}

{***}

END

END; {RSort}

В строке отмеченной {***} F1 содержит строку на один символ меньше, чем при вызове процедуры, первый символ отсортированной последовательности уже записан. Задача была сведена к сортировке более короткой строки в точно таком же формате, для которого была разработана RSort. Таким образом, {***} может быть замещен на процедурное выражение

RSort(F1)

В случае пустого файла, нам нечего писать в OUTPUT, RSort именно это и делает, проверяя на EOLN.

Предположим, что RSort вызывается в процедурном идентификаторе.

PROGRAM DoRSort (INPUT, OUTPUT);

VAR

Raw: TEXT;

{Включить PROCEDURE RSort (VAR F1: TEXT);}

BEGIN {DoRSort}

REWRITE(Raw);

{Копировать строку из INPUT в Raw}

WRITELN(‘Сортированая строка:’);

RSort(Raw);

WRITELN;

END. {DoRSort}

Может показаться, что здесь есть что-то магическое. RSort обрабатывает только один символ, не выполняя сортировки. Но она будет перезапускаться снова и снова, каждый раз обрабатывая один символ, снова до тех пор пока файл передаваемый как параметр не станет пустым. Каждый символ будет выведен в OUTPUT в сортированном порядке.