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

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

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

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

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

Функция на Pascal
Function Fact (N:integer):longint;
Begin
If N=0
Then Fact:=1
Else Fact:=Fact (N-1)*N;
End;

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

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

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

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

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