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

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

РЕКУРСИВНЫЕ
ПОДПРОГРАММЫ
в Паскале

2.

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

3.

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

4.

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

5. Пример 1. Определение факториала.

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

6. Функция на Pascal

ФУНКЦИЯ НА PASCAL
Function Fact (N:integer):longint;
Begin
If N=0
Then Fact:=1
Else Fact:=Fact (N-1)*N;
End;

7. Процедура на Pascal

ПРОЦЕДУРА НА 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;

8.

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

9. Прямой и обратный ход рекурсии

ПРЯМОЙ И ОБРАТНЫЙ ХОД РЕКУРСИИ
Действия, выполняемые функцией до входа на
следующий уровень рекурсии, называются
выполняющимися на прямом ходу рекурсии,
а действия, выполняемые по возврату с более
глубокого уровня к текущему, –
выполняющимися на обратном ходу
рекурсии.

10. Демонстрация хода рекурсии

ДЕМОНСТРАЦИЯ ХОДА РЕКУРСИИ
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

11. Задачи.

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

12. Спасибо за внимание!

СПАСИБО ЗА ВНИМАНИЕ!