Слайд 2
Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором
эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе.
В рекурсивном определении должно присутствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
Слайд 3
Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой
подпрограммы.
При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными.
Такие копии будут порождаться до выхода на граничное условие.
Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.
Слайд 4
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы
должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.
procedure Rec(n: integer; var y: integer);
begin
if <условие> then y:= <значение>
else
Begin
Rec(n-1, y); <операторы>;
end;
end;
Слайд 5
Пример 1. Определение факториала.
Слайд 6
Функция на Pascal
Function Fact (N:integer):longint;
Begin
If N=0
Then Fact:=1
Else Fact:=Fact
(N-1)*N;
End;
Слайд 7
Процедура на 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
Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии.
Сначала
она растет, а затем сокращается.
Слайд 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
factorial(4);
end.
Слайд 11
Задачи.
Написать рекурсивную подпрограмму возведения числа X в степень N.
Написать рекурсивную подпрограмму
нахождения НОД двух чисел.
Написать рекурсивную подпрограмму нахождения суммы цифр числа.
Написать рекурсивную подпрограмму вычисления чисел Фибоначчи.
Xn=Xn-1+Xn-2 X0=1 X1=1