Лекция: Рекурсивные процедуры и функции
Рекурсия– это способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе (прямо или косвенно, через другие процедуры).
Рекурсивная процедура осуществляет многократный переход от некоторого текущего уровня организации алгоритма к более низкому последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи.
Рассмотрим программу с рекурсивным вызовом на примере факториала
(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 n). Вычислить Z = Xk + Ym.
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