Иван кивает на Петра, а Петр кивает на Ивана.

Русская рекурсивная пословица

Для сравнения итерационных и рекурсивных процедур напишем две род­ственные программы из школьной жизни - для вычисления НОД (наибольшего общего делителя двух чисел) и НОК (наименьшего общего кратного). Они должны быть вам хорошо известны (если это не так, схо­дите, наконец, в школу!).

Наибольший общий делитель

Так как компьютер производит вычисления очень быстро, для более точ­ного сравнения скоростей будем повторять вычисления 1 миллион раз (но вы можете задать и другое число, побольше, если никуда не торопитесь). Для определения времени нам потребуются две подпрограммы:

 var Forml: TForml; time,time0: single; procedure TimeOn; begin time0:=GetTickCount(); //засечь начало end; function TimeOut: string; var s: string; begin time:=(GetTickCount()-time0)/1000; str(time:6:3,s); Result:= s; end; 

Для запуска соответствующих подпрограммм установим две кнопки: btnIterс надписью ИТЕРАЦИИ и sbtRecursс надписью РЕКУРСИЯ. Первая, как следует из названия, запускает итерационный цикл, вторая - рекур­сивный:

 procedure TForm1.btnIterClick(Sender: TObject); var n1,n2: integer;  i: integer;  begin  n1:= strtoint(txtNum1.Text);  n2:= strtoint(txtNum2.Text);  TimeOn;  for i:= 1 to strtoint(txtNumLoop.Text) do NOD(n1,n2); lblTime.Caption:= TimeOut;  lblRes.Caption:= inttostr(NOD(n1,n2));  end;    procedure TForm1.sbtRecursClick(Sender: TObject); var n1,n2: integer;  i: integer;  begin  n1:= strtoint(txtNum1.Text);  n2:= strtoint(txtNum2.Text);  TimeOn;  for i:= 1 to strtoint(txtNumLoop.Text) do NODR(n1,n2); lblTime.Caption:= TimeOut;  lblRes.Caption:= inttostr(NODR(n1,n2))  end;    Сами функции для вычисления НОД достаточно просты: //Вычисление наибольшего общего делителя //двух чисел типа integer //Итерационное вычисление НОД function NOD(n1,n2: integer): integer; //n1 >= n2 >= 0; var temp: integer; begin if n1 < n2 then swap(n1,n2); if n2=0 then result:= n1 else begin while n2>0 do begin temp:= n1 mod n2; n1:=n2; n2:= temp; end; result:=n1; end; end; //Рекурсивное вычисление НОД function NODR(n1,n2: integer): integer; begin if n1 < n2 then result:=NODR(n2,n1) else if n2<=0 then result:= n1  end; 

Найдите в функции NODR условие выхода из рекурсии!

Алгоритм, реализованный в функции NODR, кажется очень простым, но это обманчивая простота, поэтому рассмотрим его подробнее. Для опреде­лённости будем считать, что нужно найти НОД чисел n1=15 и n2=21.

 Для вычислений важно, чтобы первое число было не меньше второго. Если это не так, то в строке

if n1 < n2 then result:=NODR(n2,n1)

числа переставляются, и функция NODR вызывается с правильным поряд­ком аргументов. Для наших чисел n1 < n2, поэтому будет вызвана функция NODR(n2,n1), то есть NODR(21,15). Важно понять, что как числа ни пере­ставляй, первое из них - это n1, а второе - n2, поэтому в самой функции n1=21, а n2=15!

Теперь условие n1 >= n2 точно выполняется.

 В случае, если второе число меньше нуля или равно нулю, НОД равен первому числу и вычисления заканчиваются:

if n2<=0 then result:= n1

Возможно, это условие будет верным и сразу, а если нет, то будет выпол­няться строка

result:= NODR(n2,n1 mod n2);

Мы видим, что большим числом становится n2 (которое было меньшим в предыдущем обращении к функции), а меньшим - остаток от деления большего числа на меньшее (очевидно, что n2 не может быть меньше остатка).

Для наших чисел условие n2<=0 (15 <=0) неверное, так что будет испол­няться строка

result:= NODR(15, 21 mod 15); или result:= NODR(15, 6);

и вычисления продолжатся с начала п.2.

 Так как n2 (15) больше нуля, то ещё раз будет выполнена строка

result:= NODR(n2,n1 mod n2); 

или 

result:= NODR(6, 15 mod 6); или result:= NODR(6, 3);

Опять переходим к п.2, а затем к п.3:

result:= NODR(n2,n1 mod n2); или result:= NODR(3, 6 mod 3); или result:= NODR(3, 0);

Снова переходим к п.2. Теперь условие

if n2<=0 then result:= n1

выполнено и функция возвращает НОД - число 3.

Как видите, параметр n2 рано или поздно станет равен нулю, и рекурсия неизбежно закончится в строке

if n2<=0 then result:= n1,

которая и является условием завершения рекурсии.

Для более точного сравнения итерационного и рекурсивного методов, по­нажимайте на кнопки по нескольку раз, потому что в системе Windowsод­новременно выполняется множество процессов, так что время может не­сколько отличаться в разных «попытках». Более того, результаты зависят и от чисел, для которых вычисляется НОД.

Наименьшее общее кратное.

На самом деле НОК просто вычисляется через НОД по такой формуле:

НОК = n1 * n2 div НОД (n1,n2),

так что нам достаточно дополнить предыдущую программу двумя функ­циями, которые реализуют эту формулу:

//Итерационно
e вычисление HOK
function NOK(n1,n2: integer): integer;
var temp: integer; 
begin 
temp:= n1 *
n2; 
if temp = 0 
then result:= 0 
else result:= temp
div NOD(n1,n2);
end;
//Рекурсивное
вычисление HOK
function NOKR
(n1,n2:
integer): integer;
var temp: integer; 
begin 
temp:= n1 *n2 ; 
if temp = 0then result:= 0
else result:= temp
div NODR(n1,n2);
end; 

Казалось бы, и здесь скорость вычислений должна быть одинакова, но ре­курсивный способ всё-таки уверенно выигрывает: