Процедуры и функции, виды рекурсий 10-11 класс

• 1 слайд

  РЕКУРСИЯ
  

• 2 слайд

  Процедуры и функции
  Процедура( функция) представляет собой последовательность операторов, которая имеет имя, список параметров и может быть вызвана из различных частей программы.
  Имя процедуры в тексте программы называется вызовом.
  Вызов активирует процедуру (функцию) - начинают выполняться её операторы.
  После выполнения процедуры программа продолжается с оператора стоящего за вызовом.
  Отличие процедур от функций в том, что функции возвращают значение.
  

• 3 слайд

  Описание процедур и функций
  Все процедуры или функции должны быть описаны в разделе описаний основной программы.
  Описание процедуры имеет вид:
  
  procedure имя (список формальных параметров);
  раздел описаний локальных параметров
  begin
    операторы тела процедуры
  end;
  Описание функции имеет вид:
  function имя (список формальных параметров): тип значения функции;
  раздел описаний локальных параметров
  begin
    операторы тела функции
  end;
  

• 4 слайд

  Параметры процедур и функций
  Список формальных параметров состоит из одной или нескольких секций, разделенных символом " ; ".
  
  Секция состоит из списка переменных, перечисляемых через запятую, знака “:” и типа.
  
  Секция может предваряться служебным словом var - тогда параметры передаются по ссылке,
  (экономия памяти и времени).
  
  Если var отсутствует параметры передаются значениями.
  
  Список формальных параметров вместе с окружающими скобками может отсутствовать.
  

• 5 слайд

  Что такое рекурсия?
  Рекурсия – это функция (процедура) вызывающая саму себя
  
  Может ли рекурсия заменить цикл?
  Да.
  

• 6 слайд

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

• 7 слайд

  Program n1;
  uses crt;
  
  procedure Rec(i: integer);
  begin
  if i>1 then Rec(i-1);
  writeln(i);
  end;
  
  begin
  clrscr;
  Rec(5);
  end.
  рекурсивный подъём
  Процедура закрывается и выводится i
  Пока i больше 1 вызываем следующую процедуру
  рекурсивный подъём
  

• 8 слайд

  Вызов Rec(5)
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Вызов Rec(4)
  
  
  
  
  
  
  
  
  
  
  
  Вызов Rec(3)
  
  
  
  
  
  
  
  
  Вызов Rec(2)
  
  
  
  
  Вызов Rec(1)
  Вывод (1)
  Вывод (2)
  Вывод (3)
  Вывод (4)
  Вывод (5)
  i>1
  i
  Rec(i-1)
  5
  4
  3
  2
  1
  5>1 Да
  4>1 Да
  3>1 Да
  2>1 Да
  1>1 Нет
  Rec(4)
  Rec(3)
  Rec(2)
  Rec(1)
  Вывод(1)
  рекурсивный подъём
  

• 9 слайд

  Процедура 5
  Процедура 4
  Процедура 3
  Процедура 2
  Процедура 1
  Вывод 5
  Вывод 4
  Вывод 3
  Вывод 2
  Вывод 1
  Пока i>1 то вызываем очередную
  процедуру
  Рекурсивный подъем
  рекурсивный подъём
  

• 10 слайд

  Program n2;
  uses crt;
  
  procedure Rec(i: integer);
  begin
  writeln(i);
  if i>1 then Rec(i-1);
  end;
  
  begin
  clrscr;
  Rec(5);
  end.
  рекурсивный спуск
  Вывод
  Переход к следующей процедуре
  рекурсивный спуск
  

• 11 слайд

  i>1
  Вывод i
  Rec(i-1)
  5
  4
  3
  2
  1
  5>1 Да
  4>1 Да
  3>1 Да
  2>1 Да
  1>1 Нет
  Rec(4)
  Rec(3)
  Rec(2)
  Rec(1)
  Rec(i)
  Rec(5)
  Rec(4)
  Rec(3)
  Rec(2)
  Rec(1)
  рекурсивный спуск
  

• 12 слайд

  Процедура 4
  Процедура 3
  Процедура 2
  Процедура 1
  Процедура 5
  Вывод 5
  Вывод 4
  Вывод 3
  Вывод 2
  Вывод 1
  Пока i>1 то вызываем очередную
  процедуру
  Рекурсивный спуск
  рекурсивный спуск
  

• 13 слайд

  Program n3;
  Uses crt;
  Procedure Print(n:integer);
  Begin
  Writeln ('У попа была собака,');
  Writeln ('Он ее любил.');
  Writeln ('Она съела кусок мяса —');
  Writeln ('Он ее убил.');
  Writeln ('Убил и закопал');
  Writeln ('И на могиле написал:');
  if n>1 then Print(n-1);
  End;
  BEGIN
  Print(4);
  END.
  рекурсивный спуск
  Вывод
  Переход к следующей процедуре
  рекурсивный спуск
  

• 14 слайд

  Program n4;
  uses crt;
  
  procedure Rec(i: integer);
  begin
  writeln(i);
  if i>1 then Rec(i-1);
  writeln(i);
  end;
  
  begin
  clrscr;
  Rec(5);
  end.
  рекурсивный спуск,
  и рекурсивный подъем
  
  Спуск
  Подъем
  рекурсивный спуск и подъем
  

• 15 слайд

  Задачи ЕГЭ (рекурсии)
  задание №11
  Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F.
  
  
  
  Чему равна сумма всех чисел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(1)?
  

• 16 слайд

  Решение
  Пер­вым дей­стви­ем про­це­ду­ра F(1) вы­ве­дет число 1. Далее про­це­ду­ра F(1) вы­зо­вет про­це­ду­ру F(n + 1), в ре­зуль­та­те вы­пол­не­ния ко­то­рой на экра­не по­явит­ся число n + 1 = 2. Про­це­ду­ра F(2) вы­зо­вет про­це­ду­ру F(3), ко­то­рая вы­ве­дет на экран число 3 и вы­зо­вет про­це­ду­ру F(4), ко­то­рая вы­ве­дет на экран число 4 и вы­зо­вет F(5), ко­то­рая вы­ве­дет на экран число 5.
  После этого управ­ле­ние вернётся к про­це­ду­ре F(4), ко­то­рая начнёт вы­пол­нять сле­ду­ю­щий шаг сво­е­го ал­го­рит­ма, т. е. об­ра­тить­ся к про­це­ду­ре F(n + 3) = F(7). Про­це­ду­ра F(7) вы­ве­дет на экран число 7. Далее управ­ле­ние вернётся к про­це­ду­ре F(3). Рас­суж­дая ана­ло­гич­но при­хо­дим к вы­во­ду, что про­це­ду­ра F(3) до­пол­ни­тель­но вы­ве­дет на экран число 6, про­це­ду­ра F(2) — 5.
  По­след­ним дей­стви­ем про­це­ду­ры F(1) будет вызов про­це­ду­ры F(n + 3) = F(4), ко­то­рая вы­ве­дет на экран числа 4, 5, 7.
  Таким об­ра­зом, на экра­не будут числа 1, 2, 3, 4, 5, 7, 6, 5, 4, 5, 7. Их сумма равна 49.
   Ответ: 49.
  
  

• 17 слайд

  Паскаль
  program vopr_11;
  uses crt;
  var k:integer;
  procedure Rec(n:integer);
  begin
  k:=k+n;
  write(n,' ');
  if n < 5 then begin
  Rec(n + 1);
  Rec(n + 3);
  end
  end;
  //тело программы
  begin
  Rec(1);
  writeln('Ответ:':15,k);
  end.
  

• 18 слайд

  7
  5
  1
  4
  2
  6
  4
  7
  5
  3
  5
  1+2+3+4+5+7+6+5+4+5+7 =
  10 +
  18 +
  21
  49
  

• 19 слайд

  Самостоятельно
  Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан
  ре­кур­сив­ный ал­го­ритм F.
  
  
  
  Чему равна сумма всех чисел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(6)?
  

• 20 слайд

  Пояснение
  На пер­вом шаге про­це­ду­ра F(6) вы­ве­дет число 6 и вы­зо­вет про­це­ду­ры F(5) и F(3).
  На вто­ром шаге про­це­ду­ры F(5) и F(3) вы­ве­дут числа 5 и 3 и вы­зо­вут про­це­ду­ры F(4), F(2), F(2) и F(0).
  На тре­тьем шаге будут вы­ве­де­ны числа 4, 2, 2 и 0; вы­зва­ны про­це­ду­ры F(3), F(1), F(1), F(−1), F(1), F(−1).
  На четвёртом шаге будут вы­ве­де­ны числа 3, 1, 1, −1, 1, −1; вы­зва­ны про­це­ду­ры F(2) и F(0).
  На пятом шаге будут вы­ве­де­ны числа 2, 0 и вы­зва­ны про­це­ду­ры F(1), F(−1).
  На ше­стом шаге будут вы­ве­де­ны числа 1 и −1.
  
  Найдём сумму вы­ве­ден­ных чисел:
   
  6 + 5 + 3 + 4 + 2 + 2+ 0 + 3 + 1 + 1 + (−1) + 1 + (−1) + 2 + 0 + 1 + (−1) = 28.
  
  Ответ: 28.
  

• 21 слайд

  решение
  program vopr_11;
  uses crt;
  var k:integer;
  procedure F(n: integer);
  begin
  writeln(n);
  k:=k+n;
  if n > 1 then
  begin
  F(n - 1);
  F(n - 3);
  end
  end;
  //тело программы
  begin
  F(6);
  writeln('Ответ:':14,k);
  end.
  

• 22 слайд

  0
  2
  -1
  1
  6
  3
  5
  1
  3
  0
  2
  -1
  1
  4
  2
  -1
  1
  6+5+4+3+2+1+(-1)+0+1+2+1+(-1)+3+2+1+(-1)+0 =
  10
  11 +
  + 7
  28
  

• 23 слайд

  Алгоритмы, опи­ра­ю­щи­е­ся на не­сколь­ко предыдущих значений
  Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:
  F(1) = 1
  F(2) = 3
  F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n >2
  Чему равно зна­че­ние функ­ции F(5)?
  В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.
  
  

• 24 слайд

  Решение
  Выпишем уже известные нам F(1) и F(2)
  F(1)=1
  F(2)=3
  F(3)=11
  F(4)=53
  F(5)=309
  
  По­сле­до­ва­тель­но на­хо­дим:
  F(3) = F(2) * 3 + F(1) * 2 = 11,
  F(4) = F(3) * 4 + F(2) * 3 = 53,
  F(5) = F(4) * 5 + F(3) * 4 = 309.
  Ответ: 309
  

• 25 слайд

  Самостоятельно
  Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:
  F(1) = 1
  F(2) = 3
  F(n) = F(n−1) * F(n−2) + (n−2), при n > 2
  Чему равно зна­че­ние функ­ции F(5)?
  В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.
  
  

• 26 слайд

  Решение
  F(1) = 1
  F(2) = 3
  F(3) = 4
  F(4) = 14
  F(5) = 59
  
  По­сле­до­ва­тель­но на­хо­дим:
  F(3) = F(2) * F(1) + 1 = 4,
  F(4) = F(3) * F(2) + 2 = 14,
  F(5) = F(4) * F(3) + 3 = 59.
  Ответ: 59
  

• 27 слайд

  Алгоритмы, опи­ра­ю­щи­е­ся на одно преды­ду­щее значение
  Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:
  F(1) = 1
  F(n) = F(n–1) * n, при n >1
  Чему равно зна­че­ние функ­ции F(5)? В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.
  

• 28 слайд

  Решение
  По­сле­до­ва­тель­но на­хо­дим:
  F(2) = F(1) * 2 = 2,
  F(3) = F(2) * 3 = 6,
  F(4) = F(3) * 4 = 24,
  F(5) = F(4) * 5 = 120.
   
  При­ме­ча­ние
  Ис­поль­зо­ва­ние функ­ции поз­во­ля­ет вы­чис­лить так на­зы­ва­е­мый фак­то­ри­ал числа n — про­из­ве­де­ние на­ту­раль­ных чисел от 1 до n. Тем самым, F(5) = 1 * 2 * 3 * 4 * 5 = 120.
  
  Ответ: 120
  

• 29 слайд

  Самостоятельно
  Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:F(1) = 3
  F(n) = F(n–1) * (n–1), при n >1
  Чему равно зна­че­ние функ­ции F(6)?
  В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.
  
  

• 30 слайд

  Решение
  По­сле­до­ва­тель­но на­хо­дим:
  F(2) = F(1) * 1 = 3,
  F(3) = F(2) * 2 = 6,
  F(4) = F(3) * 3 = 18,
  F(5) = F(4) * 4 = 72,
  F(6) = F(5) * 5 = 360.
  Ответ: 360
  

• 31 слайд

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

Краткое описание документа:

Что такое процедуры и функции и их описание.

Параметры процедур и функций.

Определение рекурсии и рекурсивного объекта.

Что такое рекурсивный подъем и его использование.

Что такое рекурсивный спуск и его использование.

Подробное решение задач на рекурсии.

Разбор ЕГЭ задач на рекурсии с примерами кода на PASCAL