рекурсия для дист

1.

Рекурсивные
подпрограммы
в Паскале

2.

Цель:
Изучить способ организации вспомогательного
алгоритма-рекурсия, понятие - глубина рекурсии,
прямой и обратный ход рекурсии.

3.

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

4.

Обращение к рекурсивной подпрограмме ничем не
отличается от вызова любой другой подпрограммы.
При этом при каждом новом рекурсивном
обращении в памяти создаётся новая копия
подпрограммы со всеми локальными переменными.
Такие копии будут порождаться до выхода на
граничное условие.
Очевидно, в случае отсутствия граничного условия,
неограниченный рост числа таких копий приведёт к
аварийному завершению программы за счёт
переполнения стека.

5.

Для того чтобы такое обращение не было
бесконечным, в тексте подпрограммы должно
быть условие, по достижению которого
дальнейшее обращение к подпрограмме не
происходит.
procedure Rec(n: integer; var y: integer);
begin
if <условие> then y:= <значение>
else
Begin
Rec(n-1, y); <операторы>;
end;
end;

6.

Пример 1. Определение
факториала.
Факториал определяется так:
n!=1*2*3*...*n.
Рекурсивное определение:
1, если n = 0;
n! = ቊ
n ⋅ (n − 1)!, если n > 0.
Граничным условием в данном случае
является n=0.

7.

Функция на Pascal
Function Fact
(N:integer):longint;
Begin
If N=0
Then Fact:=1
Else Fact:=Fact (N-1)*N;
End;
LongInt - целое 32 битное число

8.

В языке Паскаль определено пять целых
типов
Тип
Диапазон допустимых значений
Отводимая
память, в байтах
shortint
-128…127
1
integer
-32 768…32 767
2
longint
-2 147 483 648…2 147 483 647
4
byte
0…255
1
word
0…65 535
2
Переменные целого типа могут принимать только целые значения. Такие
переменные в программе описываются следующим образом:
a, b, c: integer;
Здесь a, b, c… - имена переменных, integer – тип переменных.
Транслятор, встретив такое описание переменных a, b, c, запоминает, что
эти переменные могут принимать только целые значения и формирует
соответственно этому команды программы.

9.

Процедура на Pascal
Procedure Factorial(N:integer; Var F:longint);
Begin
If N=0 Then F:=1
Else
Begin
Factorial(N-1, F); F:=F*N;
End;
End;

10.

Fact(4)
Fact(3)
Fact(2)
Fact(1)
Fact(0)
24=4*6
6=3*2
2=2*1
1=1*1
1
Число копий переменных, одновременно находящихся в памяти,
называется глубиной рекурсии.
Сначала она растет, а затем сокращается.

11.

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

12.

Демонстрация хода рекурсии
var glubina: Integer := 0;
function factorial(N: integer) : longint;
begin
{при входе в функцию увеличиваем глобальную переменную,
которая считает глубину рекурсии}
glubina := glubina + 1;
Writeln('Прямой ход рекурсии. Глубина = ', glubina);
Result := 1;
if N > 0 then Result := factorial(N-1) * N;
Writeln('Обратный ход рекурсии. Глубина = ', glubina);
{при входе из функции - уменьшаем эту глобальную переменную}
glubina := glubina - 1;
end;
begin
factorial(4);
end.

13.

Контрольные вопросы:
1.Что такое рекурсия. Дайте определение.
2.Глубина рекурсии-дайте определение.
3.Расскажите о прямом и обратным ходе рекурсии.