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

Слайд 1

Слайд 2

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

Слайд 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. Рекурсивное определение: Граничным условием в данном случае является n=0.

Слайд 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

Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии. Сначала она растет, а затем сокращается . Fact(4) Fact(3) Fact(2) Fact(1) 6 =3*2 2 =2*1 1 =1*1 24 =4*6 Fact( 0 ) 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 factorial(4); end.

Слайд 11

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

Слайд 12

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