Функции , и могут быть упрощены . Упростить функцию, просчитывающую ,
можно с помощью таблицы значений или решения задачи восходящим способом.
Некоторые рекурсивные алгоритмы настолько сложны, что применение этих
методов затруднено или невозможно. Проблематично создать нерекурсивные ал-
горитмы для рисования кривых Гильберта и Серпинского. Другие рекурсивные
алгоритмы еще более сложны.
Любой алгоритм, который выводит
или , занимает 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. Поскольку число шагов остается тем же самым, пол-
ное время выполнения алгоритма не изменяется.
Как и в случае удаления хвостовой рекурсии, этот метод позволяет избежать
глубокой рекурсии, которая может . |
Главная
Каталог файлов
