Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.

Рассмотрим пример - вычисление факториала. Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции FAC.

При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В примере решение при N = 0 тривиально и используется для остановки рекурсии.

Пример 0‑29

(Pascal)

Program Factorial;

var

n: Integer;

Function Fac(n: Integer): Real;

{Рекурсивная функция, вычисляющая n! }

begin {Fac}

if n< = 0 then

Fac:= 1

else Fac:= n * Fac(n-1)

end {Fac};

{---------------}

begin {main}

ReadLn (n);

WriteLn ('n!= ',Fac(n))

end {main}.

Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FAC на EXTENDED, программа перестанет работать уже при N = 8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной.

Пример 0‑30

(Pascal)

Program Factorial;

var

n: Integer;

Function Fac(n: Integer): extended;

var

F: extended; {Буферная переменная для разгрузки стека сопроцессора}

{Рекурсивная функция, вычисляющая п! }

if n <= 0 then

Fac:= 1 else begin

F:= Fac(n-l); Fac:= F * n end end {Fac};

{--------------}

begin {main}

ReadLn (n);

WriteLn ('n! = ',Fac(n))

end {main}.

 

Пример 0‑31

Составьте программу, сообщающую сумму чисел от 1 до n, где n вводится пользователем.

(Pascal)

Program Summa;

var

n: Integer;

Function Sum(n: Integer): Real;

begin

if n = 0 then

Sum:= 0

else Sum:= n + Sum(n-1)

end;

{---------------}

begin {main}

ReadLn (n);

WriteLn ('сумма’= ',Sum(n))

end {main}

Пример 0‑32

Составьте программу, сообщающую "Условие верно", если переменной cond с клавиатуры присвоено значение, не равное 0. Если с клавиатуры введено значение 0, сообщить, сколько раз выполнилось тело цикла и "Работа завершена".

(Pascal)

var n: Integer;

procedure Cond;

var k:integer;

begin

readln (k);

if k= 0 then

exit

else

begin

n:=n+1;

writeln (‘Условие верно’);

Cond

end

end;

{---------------}

begin {main}

n:=0;

Cond

Writeln('Работа завершена', 'n=',n)

End. {main}

Задачи на рекурсию на практике брать не будем, студентам скажи, что разобранные примеры с рекурсивным вызовом процедуры уметь показывать на экзамене и уметь исполнять. Исполни задачу с факториалом и оформи протокол исполнения.