Var a,b,r:integer;
procedure nod(a,b:integer; var r:integer);
begin if a=b then r:=a {базис}
else if a>b then nod(a-b,b,r)
else nod(a,b-a,r)
end;
begin readln(a,b);
nod(a,b,r);
writeln(r);
end.
Рис.3.
При выполнении программы Паскаль будет использовать стек, в который будут записываться фреймы активации каждого вызова. Например, для а=20 и b=12 стек будет выглядеть следующим образом (запись в стек идет словами, то есть по 2 байта, как и изображено на рисунке):
Рис.4.
Если вместо процедуры использовать рекурсивную функцию, то фрейм активации уменьшится, так как сократится список параметров. Соответствующая программа будет выглядеть следующим образом:
program ex;
Var a,b,r:integer;
function nod(a,b:integer):integer;
begin if a=b then nod:=a {базис}
else if a>b then nod:=nod(a-b,b) {рекурсивные утверждения}
else nod:=nod(a,b-a)
end;
begin readln(a,b);
r:=nod(a,b);
writeln(r);
end.
Пример 5. Определение корней уравнения y=x2-2 на заданном отрезке методом половинного деления.
Для простоты будем считать, что отрезок задается таким образом, что корень на нем есть (иначе основная программа должна содержать проверку наличия корня).
Метод половинного деления для непрерывных функций заключается в следующем:
Базисное утверждение: Если абсолютная величина функции в середине отрезка не превышает заданного значения точности, то координата середины отрезка и есть корень.
Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.
Var a,b,eps,X:real;
procedure root(a,b,eps:real,var r):real;
Var f,X:real;
begin x:=(a+b)/2; f:=x*x-1;
if abs(f)>eps then
begin
if (a*a-1)*f>0 then root(x,b,eps,r)
else root(a,x,eps,r)
end;
end;
begin readln(a,b,eps);
root(a,b,eps,x);
writeln(x);
end.
Рис.5.
Одной из наиболее часто встречающихся ошибок при создании рекурсивных процедур является "зациклившаяся" или бесконечная рекурсия, при которой базисное утверждение не достигается, и, соответственно, вновь и вновь вызывается рекурсивная подпрограмма. От бесконечного цикла бесконечная рекурсия отличается тем, что каждая активация требует дополнительной памяти для размещения фрейма активации, и, следовательно, программа, содержащая бесконечную рекурсию, обычно завершается аварийно при исчерпании доступной памяти. Так для рассмотренного примера, если, например, задать отрезок, не содержащий корня, то произойдет "зацикливание", что вызовет аварийное завершение программы. Таким образом, причиной "зацикливания" может являться, как ошибка в программе, так и ошибка в данных.
Пример 6. Проверка чередования букв и цифр в заданной строке (первый символ - обязательно буква).
Базисные утверждения: Строка допустима, если она пустая.
Строка не допустима, если обнаружен не допустимый символ.
Рекурсивное утверждение: Если текущий символ строки допустим, то допустимость строки определяется оставшейся частью строки.
Для написания данной программы используем взаиморекурсивные подпрограммы. Первая будет проверять, является ли текущий символ буквой, и, если "да", будет удалять этот символ и вызывать вторую. Вторая - будет проверять, является ли текущий символ цифрой, и, если "да", будет удалять эту цифру и вызывать первую. Выход из рекурсии - по достижению конца строки. Параметр - строка передается по значению.
program ex2;