Рекурсивные процедуры и функции

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

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

Рассмотрим программу с рекурсивным вызовом на примере факториала

(n! = 1* 2 * 3 * … * n).

Proqram rec_1;

var f: longint;

Function fact (f: inteqer): longint;

{описание функции, f – формальный параметр, значение типа inteqer, результат функции – типа longint}

Begin

if f = 0

then fact: = 1

else fact: = f * fact (f - 1)

End;

Begin

write (Введите число f > 0 ');

Readln (f);

if f > 0

then writeln('Для числа ',N,' значение фак-

ториала = ', fact(f))

else writeln(' число неверное! ');

End.

Использование рекурсивной формы организации алгоритма дает более компактный текст программы, но выполняется медленнее и может вызвать переполнение стека. Стек – специальным образом организованная область памяти, в которой размещаются при каждом входе в подпрограмму ее локальные переменные.

Вызов процедурой самой себя (рекурсивный вызов) ничем не отличается от вызова другой процедуры.

Что происходит, если одна процедура (или программа) вызывает другую? В общих чертах происходит следующее:

1) в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные);

2) в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;

3) запоминается адрес возврата в вызывающую процедуру (или программу);

4) управление передается вызванной процедуре.

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

П р и м е р. Пусть рекурсивная функция step(a: real; n: inteder): real; возводит число a в степень n (a ⁿ). Вычислить Z = X^k + Y^m_.

Program rec_2;

var a, y, z: real;

k, m: integer;

function step (a: real; n: integer): real;

Begin

if n = 0

then step: = 1

else step: = a * step (a, N -1)

End;

Begin