«

»

Pascal. Рекурсия

Алгоритм, в котором предусмотрен вызов подпрограммой себя самой, называется рекурсивным. Использовать эту особенность в Pascal могут как процедуры, так и функции.

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

В ЯП Pascal глубина рекурсии не ограничена, но необходимо предусмотреть условие, на каком-либо шаге приводящее к завершению вызова процедурой или функцией самой себя. Иначе произойдет зацикливание.

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
program recursio;
uses crt;
var
n: shortint;
function Fibonacci(p_n: shortint): longint;
begin
if (p_n=1) then Fibonacci:=0
else if (p_n=2) then Fibonacci:=1
else Fibonacci:=Fibonacci(p_n-1)+Fibonacci(p_n-2)
end;
begin
clrscr;
write(' Номер числа: '); readln(n);
write(' Значение чиса: ', Fibonacci(n));
end.

 

Во время выполнения рекурсивной подпрограммы в оперативной памяти выделяется  место для данных вызванной процедуры или функции. И те подпрограммы, которые рекурсивно передают управление, остаются в оперативной памяти. Поэтому завершение подпрограмм происходит пошагово, в обратном порядке.

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
program recursio;
uses crt;
var
n: integer;
function Sum(p_n: integer): integer;
var r: integer;
begin
r:=p_n mod 10;
if (p_n div 10)<>0 then r:=r+Sum(p_n div 10);
Sum:=r;
end;
begin
clrscr;
write(' Число: '); readln(n);
if Sum(n)>=0 then write(' Сумма цифр : ', Sum(n))
else write(' Сумма цифр: ', Sum(n)*(-1));
end.

 

Рекурсия в подпрограммах визуально оптимизирует код, но как уже было сказано ранее, такие алгоритмы несут сильную нагрузку на оперативную память. Поэтому приходиться выбирать между компактностью и производительностью.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *