Лекция: Рекурсивные процедуры и функции.

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

Рекурсия может быть прямой или косвенной. При прямой рекурсии оператор вызова подпрограммы содержится непосредственно в ее исполняемой части. Любую рекурсивную процедуру (функцию) можно сделать не рекурсивной. Рекурсивное описание обычно короче и нагляднее, но требует больших затрат машинного времени (за счет повторных обращений) и памяти машины (за счет дублирования переменных).

Рекурсивная подпрограмма однократно вызывается извне. Условие полного окончания работы рекурсивной процедуры или функции должно находиться в ней самой.

Рассмотрим пример. Вычислить значение F=M! Рекурсивное определение значение факториала можно записать следующим образом:

при М=1 F=1

при М> 1 F= M!= M*(M-1)!, т.е. М! определяется через (М-1)!

a) Рекурсивная функция

Program Main;

Var M: integer;

F:real;

Function FACT (N:integer): real;

Begin

If N=1 then

FACT:=1

Else

FACT:= N* FACT(N-1);

End;

Begin

Readln(M);

F:= FACT ( M );

Writeln (' M!=', F);

End.

b) Рекурсивная процедура

Program Main;

Var M: integer;

F:real;

Procedure FACT(N:integer; Var F: real);

Var Q: real;

Begin

If N=1 then Q:=1