Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 26
На сайте нет зарегистрированных пользователей

Пользователей: 13,361
новичок: uehuat
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Файл записей с выводом обратного заголовка на Turbo Pascal
База данных - рабочее место кассира на Delphi + бд Access
Игра Sokoban на Delphi + Блок схемы

Устранение рекурсии в общем случае
Функции , и могут быть упрощены . Упростить функцию, просчитывающую ,
можно с помощью таблицы значений или решения задачи восходящим способом.
Некоторые рекурсивные алгоритмы настолько сложны, что применение этих
методов затруднено или невозможно. Проблематично создать нерекурсивные ал-
горитмы для рисования кривых Гильберта и Серпинского. Другие рекурсивные
алгоритмы еще более сложны.
Любой алгоритм, который выводит
или , занимает O(N^4) шагов, поэтому первоначаль-
ные рекурсивные алгоритмы вполне годятся для работы. Они достигают максималь-
ной производительности при приемлемой глубине рекурсии. Однако встречаются
сложные алгоритмы, которые имеют большую глубину рекурсии, но устранение
в них невозможно. В этом случае можно преобразовать рекурсив-
ный алгоритм в нерекурсивный. Базовый метод состоит в том, чтобы исследовать
пути, по которым компьютер выполняет рекурсию и попытаться повторить шаги,
выполняемые компьютером. Новый алгоритм будет выполнять мнимую рекурсию
вместо того, чтобы всю работу делал компьютер.
Поскольку новый алгоритм выполняет практически те же самые шаги, что
и компьютер, стоит поинтересоваться, увеличится ли скорость. Скорее всего, нет.
Компьютер может выполнять определенные задачи с помощью рекурсии быстрее,
чем вы можете имитировать их. Самостоятельная обработка всех деталей алгорит-
мов позволяет вам лучше контролировать распределение локальных переменных
и позволяет избежать большой глубины рекурсии.
Обычно вызов процедуры осуществляется в три этапа. Во-первых, система со-
храняет всю информацию, которая ей нужна для продолжения выполнения проце-
дуры после ее завершения. Во-вторых, она подготавливает вызов процедуры и пере-
дает управление ей. И наконец, когда вызванная процедура завершается, система
восстанавливает сохраненную информацию и передает управление назад в соот-
ветствующую точку программы. Если вы преобразовываете рекурсивную проце-
дуру в нерекурсивную, вы должны самостоятельно выполнить эти три шага.
Рекурсивную процедуру можно обобщить следующим образом:
procedure Recurse(num : Integer);
begin
<Кодовый блок 1>
Recurse(<параметры>)
<Кодовый блок 2>
end;



Поскольку после рекурсивного шага есть еще операторы, в данном алгоритме
нельзя устранить хвостовую рекурсию.
Начните с маркировки первых строк в 1-ом и 2-ом блоках кода. Затем эти мет-
ки будут использоваться для определения места, с которого требуется продолжить
выполнение при возврате из мнимой рекурсии. Метки нужны только для того, что-
бы вам было проще понять, что делает алгоритм; они не являются частью кода
Delphi. В данном примере метки будут выглядеть таким образом:
procedure Recurse(num : Integer);
begin
1 <Кодовый блок 1>
Recur8е(<параметры>);
2 <Кодовый блок 2>
end;



Используйте специальную метку 0 для обозначения конца мнимой рекурсии.
Затем можно переписать процедуру без рекурсии:
procedure Recurse(num : Integer);
var
рс : Integer; // Говорит о том, где необходимо возобновить
// выполнение.
begin
рс := 1; // Начинаем сначала.
repeat // Бесконечный цикл.
case pc of
1: // Выполняется 1 кодовый блок.
begin
<Кодовый блок 1>
if (достигнуто основное условие) then begin
// Выход из рекурсии и возврат к основному коду.
// Блок 2.
рс := 2
end else begin
// Сохранение необходимых после рекурсии переменных.
// Сохранить рс = 2 - где необходимо возобновить
// выполнение после окончания рекурсии.
// установка переменных для рекурсивного обращения.
// Например, num = num - 1.
//Переход к блоку 1 для запуска рекурсии
рс := 1;
end;
end;
2: // Выполнение 2 кодового блока.
begin
<Кодовый блок 2>
РС := 0;
end;
0: // Рекурсия закончена.
begin
if (Это последняя рекурсия) then break;
// В противном случае восстанавливаются рс и другие
// переменные, сохраненные перед рекурсией.
end;
end; // End case.
until (False); // Конец бесконечного цикла.
end;



Переменная рс - это программный счетчик, который сообщает процедуре, ка-
кой шаг она должна выполнить следующим. Например, когда рс = 1, процедура
должна выполнить кодовый блок 1.
Когда процедура достигает основного условия, она не выполняет рекурсию.
Вместо этого она изменяет значение рс на 2, и программа продолжает выполне-
ние кодового блока 2.
Если процедура еще не достигла основного условия, осуществляется мнимая
рекурсия. Для этого процедура сохраняет значения любых локальных переменных,
которые потребуются после завершения мнимой рекурсии. Она также сохраняет
значение рс для участка кода, который она должна выполнить после окончания
мнимой рекурсии. В данном примере следующим выполняется кодовый блок 2,
поэтому программа сохраняет 2 как следующее значение рс. Самый простой спо-
соб хранить значения локальных переменных и рс состоит в использовании сте-
ков, таких как описанные в главе 3.
Это проще понять на конкретном примере. Рассмотрим немного измененную
версию функции факториала. Здесь она написана как процедура, которая возвра-
щает свое значение через переменную, а не через саму функцию, что немного упро-
щает процедуру.
procedure Factorial(var num, value : Integer);
var
partial : Integer;
begin
1 if (num<=1) then
value := 1 else
begin
Factorial(num-1,partial);
2 value := num*partial;
end;
end;



После возврата процедуры из рекурсии требуется узнать первоначальное зна-
чение переменной num, чтобы выполнить умножение
value: = num * partial


.
Поскольку процедуре необходим доступ к значению num после окончания рекур-
сии, она должна сохранить значения рс и num перед началом рекурсии.
Следующая процедура сохраняет эти значения в двух стеках на основе масси-
ва. При подготовке рекурсии процедура помещает значения num и рс в стеки. Когда
мнимая рекурсия заканчивается, процедура выталкивает из стеков недавно добав-
ленные значения. Следующий код демонстрирует нерекурсивную версию процеду-
ры вычисления факториала:
procedure Factorial(var num, value : Integer);
var
num_stack : array [1..200] of Integer;
pc_stack : array [1..200] of Integer;
stack_top : Integer; // Начало стека.
рс : Integer;
begin
stack_top := 0;
pc := 1;
repeat // Бесконечный цикл.
case pc of
1 :
begin
if (num<=1) then // Основное условие.
begin
value := 1;
pc := 0; // Окончание рекурсии.
end else // Рекурсия.
begin
// Сохранение значений пит и следующего рс.
stack_top := stack_top+1;
num_stack[stack_top] := num;
pc_stack[stack_top] := 2; //Начинать с 2.
// Начало рекурсии.
num := num-1;
// Передает управление обратно в начало процедуры.
рс := 1;
end;
end;
2 :
begin
// Значения переменных содержат результат недавно
// оконченной рекурсии. Оно умножается на num.
value := value*num;
// Выход из рекурсии.
рс := 0;
end;
0:
begin
// Конец рекурсии.
// Если стеки пусты, то процедура заканчивает выполнение.
if (stack_top<=0) then break;
// В противном случае восстанавливаются значения локальных
// переменных и рс.
num := num_stack[stack_top],-
рс := pc_stack[stack_top];
stack_top := stack_top-1;
end;
end; // End case.
Until (False); // Конец бесконечного цикла.
end;



Как и алгоритм устранения хвостовой рекурсии, этот метод имитирует пове-
дение рекурсивного алгоритма. Процедура заменяет каждое рекурсивное обраще-
ние итерацией цикла repeat. Поскольку число шагов остается тем же самым, пол-
ное время выполнения алгоритма не изменяется.
Как и в случае удаления хвостовой рекурсии, этот метод позволяет избежать
глубокой рекурсии, которая может .
Опубликовал Kest October 20 2009 20:33:58 · 0 Комментариев · 7610 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Indy in Depth Глу...
De Knop
Редактор текста (...
БД студентов
Degisy Data Acces...
32 урока по Delphi
Crypt32
SysInfo [Исходник...
Prolog Interprete...
Панель "Случайное...
Язык программиров...
Обучение Borland ...
Библия для програ...
База каталогов ( ...
Delphi7 Для профе...
В.Понамарев - COM...
PHP: Полезные приемы
iComm v.6.1 - выв...
BIOS
Искусство програм...

Топ загрузок
Приложение Клие... 100772
Delphi 7 Enterp... 97809
Converter AMR<-... 20261
GPSS World Stud... 17014
Borland C++Buil... 14189
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5972
Visual Studio 2... 5206
Microsoft SQL S... 3661
Случайные статьи
Игровой клуб Космолот
Квартира в Новой У...
Чересчур большие и...
есть ли фильтр гру...
анне Тип Choices о...
Создание имитацион...
Литература
Москва ремонт погр...
Обмен ссылками, за...
Другие возможности...
Управление хранени...
Казино Jet
Построение дерева ...
МТС Банк: горячая ...
Ускоренное деление
Где мы находимся?
Анализ скорости вы...
Онлайн клуб Вулкан...
Продолжение описан...
Выбор атмосферы съ...
Type mismatch
Способ проведения ...
Методы values() и ...
Очереди
Передача данных в ...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?