Рекурсия

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

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

Пример рекурсивной функции вычисления факториала:

Function factorial(N: integer) : longint;

Begin

If N= 0 then

Factorial := 1

Else Factorial := factorial(N-1) * N

End;

Пример рекурсивной процедуры, возводящей число в степень:

Procedure Power (X: real; N: integer; var Y: real);

Begin

If N=0 then

Y:= 1

Else Begin Power(X, N-1,Y);

Y:= Y*X;

End;

End;

Задача: Построить последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Применение рекурсии позволяет решить задачу без использования циклов, как в основной программе, так и в процедуре:

Program Arsac;

Var first: word;

Procedure posledov (i: word);

Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov(3*i+1) else posledov(i div 2);

End;

Begin

Write (‘ введите первое значение ’); readln (first);

Posledov (first);

Readln ;

End.