Презентация на тему "Рекурсивные подпрограммы в Паскале" 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

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

  varglubina: 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

• 
  Слайд 12

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