рекурсия

1.

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

2.

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

3.

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

4.

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

5.

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

6.

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

7.

В языке Паскаль определено пять целых
типов
Тип
Диапазон допустимых значений
Отводимая
память, в байтах
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, запоминает, что
эти переменные могут принимать только целые значения и формирует
соответственно этому команды программы.

8.

Процедура на 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;

9.

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

10.

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

11.

Демонстрация хода рекурсии
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.

12.

Задачи.
1.
Написать рекурсивную подпрограмму возведения
числа X в степень N.
2.
Написать рекурсивную подпрограмму нахождения
НОД двух чисел.
3.
Написать рекурсивную подпрограмму нахождения
суммы цифр числа.
4.
Написать рекурсивную подпрограмму вычисления
чисел Фибоначчи.
Xn=Xn-1+Xn-2
X0=1 X1=1