Навигация
Главная
Поиск
Форум
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
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
ТЕХНОЛОГИИ ДОСТ... 64668
Имитационное мо... 58927
Реклама
Сейчас на сайте
Гостей: 4
На сайте нет зарегистрированных пользователей

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

База данных склада на Delphi + Схема БД
Моделирование процесса обработки заданий пакетным режимом работы с квант...
База данных студентов на Delphi (файл записей) + Блок схемы

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Устранение рекурсии в общем случае
Функции , и могут быть упрощены . Упростить функцию, просчитывающую ,
можно с помощью таблицы значений или решения задачи восходящим способом.
Некоторые рекурсивные алгоритмы настолько сложны, что применение этих
методов затруднено или невозможно. Проблематично создать нерекурсивные ал-
горитмы для рисования кривых Гильберта и Серпинского. Другие рекурсивные
алгоритмы еще более сложны.
Любой алгоритм, который выводит
или , занимает 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 21 2009 00:33:58 · 0 Комментариев · 6211 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Info
Работа с базами д...
StartMark
Counter [Исходник...
Керниган Б.В., Ри...
Алгоритмы шифрова...
начисление процен...
KOL & MCK v1.69
Шейдеры в Delphi
C# Учебный курс
IIIDTrans
Андрей Боровский....
AlnComponents
Delphi 6 программ...
Развивающийся фла...
ZipForge
PHP 5. Полное рук...
Еext Editor
Delphi. Готовые а...
Простой пример ка...

Топ загрузок
Приложение Клие... 100501
Delphi 7 Enterp... 89065
Converter AMR<-... 20086
GPSS World Stud... 14195
Borland C++Buil... 12390
Borland Delphi ... 8802
Turbo Pascal fo... 7067
Калькулятор [Ис... 5025
Visual Studio 2... 5011
FreeSMS v1.3.1 3550
Случайные статьи
Объяснение решения
Сохранение проекта
VARIABLE (ОПРЕДЕЛИ...
Пакет: бесплатный ...
Что позволяет подд...
Интересная тема дл...
Построение активно...
Работа с динамиче...
Каким будет просто...
Средства обработки...
Создание компонент...
Реализация обобщен...
Блоки
Разрыв страницы
Удаление компонент...
Вызов хранимых про...
Что есть у большин...
0, добавьте следую...
Где купить постель...
Завершение установ...
Жесткие диски
11.5. Задачи
Взаимодействие с п...
Misplaced conditio...
Определение шаблон...
Статистика



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


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