Навигация
Главная
Поиск
Форум
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
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 63909
Модуль Forms 63636
ТЕХНОЛОГИИ ДОСТ... 60480
Пример работы с... 59868
Имитационное мо... 55957
Реклама
Сейчас на сайте
Гостей: 14
На сайте нет зарегистрированных пользователей

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

Сравнение двух бинарных деревьев на Turbo Pascal + отчет
Моделирование регулировочного участка цеха на GPSS + Пояснительная записка
Обратное размещение элементов ЭВС на 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 Комментариев · 6053 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
CoolDev TipsSyste...
Библия хакера 2. ...
Printgrid
Borland Delphi 8 ...
CaptionButton
Delphi 7 Enterpri...
Программа для рис...
Карта сайта
Разработка распре...
Игра "Астероиды" ...
Использование Lis...
Программирование ...
Borland C++Builde...
EMSQuickImport
Allsubmitter 4.7 ...
AUTOWEB
ProLIB18
INSTANT BOOSTER v...
Изучаем Ассемблер
TelBook

Топ загрузок
Приложение Клие... 100449
Delphi 7 Enterp... 85816
Converter AMR<-... 20067
GPSS World Stud... 12518
Borland C++Buil... 11576
Borland Delphi ... 8504
Turbo Pascal fo... 7023
Visual Studio 2... 4989
Калькулятор [Ис... 4739
FreeSMS v1.3.1 3536
Случайные статьи
Представление хэш-...
Как фильтруется и ...
Семафоры и синхрон...
"Введите число, из...
1. Какое правило н...
К головоломке "зеб...
Двоичная композиция
Сборка. Продолжение
Найти среднее ариф...
Особенности практи...
Вкладка Configure ...
status
Процедура SetFillP...
Оператор «плюс» (+)
Просмотр списка по...
Использование SD-карт
Разнотипные переме...
Тестирование прово...
убедиться, что сет...
6. Локальная групп...
Протокол Telnet
Apache + Perl + PH...
Словарь раскрутки ...
Как решить проблем...
Анонимный доступ г...
Статистика



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


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