• 

  1 слайд

  Задание № 11 ЕГЭ
  (базовый уровень, время – 5 мин)
  
  Рекурсивные алгоритмы.
  
  Автор – Коротун О.В.,
  учитель информатики МОУ «СОШ № 71»
  

• 

  2 слайд

  Содержание:
  Определение рекурсии
  Примеры решения задач
  Пример 1
  Пример 2
  Пример 3
  Пример 4
  Задания для тренировки
  

• 

  3 слайд

  Что нужно знать:
  Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.
  
  Герб Российской Федерации является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия.
   
  Рекурсивный герб России
  

• 

  4 слайд

• 

  5 слайд

  В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
  пример рекурсии: Если у вас жирное пятно на платье,не переживайте. Пятна от масла убираются бензином.Пятно от бензина раствором щёлочи.Щелочь убирается эссенцией.След от эссенции потрите маслом.Hу,а как убрать пятна от масла,вы уже знаете!
  

• 

  6 слайд

  Пример задания:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n + 1);
  F(n + 3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  
  Решение с помощью дерева вызовов:
  в начале каждого вызова на экран выводится значение единственного параметра функции
  

• 

  7 слайд

  Пример задания:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n + 1);
  F(n + 3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  
  1
  

• 

  8 слайд

  Пример задания:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n + 1);
  F(n + 3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  
  при n<5 выполняется два рекурсивных вызова, и на экране появляются следующие значения параметра:
  1
  4
  2
  +1
  +3
  

• 

  9 слайд

  Пример задания:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n + 1);
  F(n + 3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  
  Продолжаем до тех пор, пока условие n<5 не станет ложным для узловых параметров. Получаем следующие значения:
  
  1
  2
  4
  5
  3
  4
  5
  7
  6
  5
  7
  

• 

  10 слайд

  Пример задания:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n + 1);
  F(n + 3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  
  Продолжаем до тех пор, пока условие n<5 не станет ложным для узловых параметров. Получаем следующие значения:
  
  1
  2
  4
  5
  3
  4
  5
  7
  6
  5
  7
  Складывая все эти числа, получаем 49
  

• 

  11 слайд

  15
  Пример № 2:
  Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  F(n+2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  1
  3
  3
  9
  5
  7
  15
  5
  9
  Складывая все эти числа, получаем 79
  7
  +2
  *3
  Аналогичная задача, которую можно решать с помощью дерева:
  

• 

  12 слайд

  Пример № 2:
  Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  F(n+2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  А можно обойтись и без дерева!
  Пусть S(n) – это сумма чисел, которые будут выведены при вызове F(n). Тогда
  
  
  n+S(n+2)+S(n*3), n<6
  S(n) =
  n, n≥𝟔
  
  Выполняем вычисления:
  S(1)=1+S(3)+S(3)
  S(3)=3+S(5)+S(9)=12+S(5)
  S(5)=5+S(7)+S(15)=5+7+15=27
  Делаем обратный ход:
  S(3)=12+27=39
  S(1)=1+39+39=79
  
  
  
  

• 

  13 слайд

  Пример № 3:
  Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-2);
  F(n div 2)
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
  7
  5
  3
  2
  3
  1
  1
  1
  1
  В этом примере на экран выводятся не значения параметра n, а символ *
  -2
  div 2
  1
  0
  -1
  0
  -1
  0
  -1
  -1
  -1
  0
  0
  0
  

• 

  14 слайд

  Пример № 3:
  Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-2);
  F(n div 2)
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране
  при выполнении вызова F(7)?
  *
  Подсчитав количество «звездочек», получаем 21
  В этом примере на экран выводятся не значения параметра n, а символ *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  *
  

• 

  15 слайд

  Пример № 3:
  Дан рекурсивный алгоритм:
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-2);
  F(n div 2)
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране
  при выполнении вызова F(7)?
  Решим задачу без дерева.
  Пусть S(n) – это количество «звездочек», которые будут выведены при вызове F(n). Тогда
  
  1+S(n-2)+S(n div 2), n>0
  1, n≤𝟎
  
  Нам нужно узнать S(7).
  S(7)=1+S(5)+S(3)
  S(5)=1+S(3)+S(2)
  S(3)=1+S(1)+S(1)
  S(2)=1+S(0)+S(1)=1+1+S(1)=2+S(1)
  S(1)=1+S(-1)+S(0)=1+1+1=3
  Делаем обратный ход:
  S(2)=2+3=5
  S(3)=1+3+3=7
  S(5)=1+7+5=13
  S(7)=1+13+7=21
  
  S (n)=
  

• 

  16 слайд

  Пример № 4:
  procedure F(n: integer);
  begin
  if n < 3 then
  write('*')
  else begin
  F(n-1);
  F(n-2);
  F(n-2)
  end;
  end;
  
  Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.
  6
  5
  4
  3
  4
  3
  2
  эта задача по сути такая же, как и предыдущая: для n < 3 функция выводит одну звездочку, а для бóльших n продолжаем рисовать дерево
  -1
  -2
  4
  -2
  3
  2
  

• 

  17 слайд

  Пример № 4:
  procedure F(n: integer);
  begin
  if n < 3 then
  write('*')
  else begin
  F(n-1);
  F(n-2);
  F(n-2)
  end;
  end;
  
  Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.
  6
  5
  4
  3
  4
  3
  *
  -1
  -2
  4
  -2
  3
  *
  Вторая и третья ветви абсолютно одинаковые, поэтому будем рисовать одну, а количество «звездочек» потом умножим на 2.
  
  При условии n<3 на экране появляются «звездочки».
  
  

• 

  18 слайд

  Пример № 4:
  procedure F(n: integer);
  begin
  if n < 3 then
  write('*')
  else begin
  F(n-1);
  F(n-2);
  F(n-2)
  end;
  end;
  
  Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.
  6
  5
  4
  3
  4
  3
  -1
  -2
  4
  -2
  3
  **
  3
  **
  ***
  ***
  ***
  ***
  Получаем по первой ветви 11 «звездочек», по третьей, а значит и по второй – по 5.
  Всего – 21
  При условии n<3 на экране появляются «звездочки».
  
  

• 

  19 слайд

  Пример № 4:
  procedure F(n: integer);
  begin
  if n < 3 then
  write('*')
  else begin
  F(n-1);
  F(n-2);
  F(n-2)
  end;
  end;
  
  Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.
  Решим задачу без дерева.
  Пусть S(n) – это количество «звездочек», которые будут выведены при вызове F(n). Тогда
  
  S(n-1)+S(n-2)+S(n-2), n≥𝟑
  1, n<𝟑
  
  ИЛИ
  S(n-1)+2*S(n-2) , n≥𝟑
  1, n<𝟑
  
  
  
  S (n)=
  S (n)=
  

• 

  20 слайд

  Пример № 4:
  procedure F(n: integer);
  begin
  if n < 3 then
  write('*')
  else begin
  F(n-1);
  F(n-2);
  F(n-2)
  end;
  end;
  
  Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.
  S(n-1)+2*S(n-2) , n≥𝟑
  1, n<𝟑
  
  
  
  S (n)=
  Нам нужно узнать S(6).
  S(6)=S(5)+2*S(4)
  S(5)=S(4)+2*S(3)
  S(4)=S(3)+2*S(2)
  S(3)=S(2)+2*S(0)=S(2)+2*1=S(2)+2
  S(2)=1
  
  Делаем обратный ход:
  S(3)=1+2=3
  S(4)=3+2*1=5
  S(5)=5+2*3=11
  S(6)=11+2*5=21
  

• 

  21 слайд

  Задания для тренировки
  

• 

  22 слайд

  Задача 1:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-2);
  F(n div 2);
  F(n div 2);
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?
  
  Ответ: 34
  

• 

  23 слайд

  Задача 2:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-2);
  F(n-2);
  F(n div 2);
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
  Ответ: 58
  

• 

  24 слайд

  Задача 3:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-3);
  F(n div 2);
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
  Ответ: 15
  

• 

  25 слайд

  Задача 4:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-3);
  F(n-2);
  F(n div 2);
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
  Ответ: 55
  

• 

  26 слайд

  Задача 5:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  F(n-3);
  F(n-2);
  F(n div 2);
  F(n div 2);
  end
  end;
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
  Ответ: 97
  

• 

  27 слайд

  Задача 6:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  writeln('*');
  F(n-2);
  F(n div 2);
  end
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
  Ответ: 31
  

• 

  28 слайд

  Задача 7:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  writeln('*');
  F(n-2);
  F(n div 2);
  F(n div 2);
  end
  end;
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
  Ответ: 81
  

• 

  29 слайд

  Задача 8:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln('*');
  if n > 0 then begin
  writeln('*');
  F(n-2);
  F(n-2);
  F(n div 2);
  end
  end;
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
  Ответ: 77
  

• 

  30 слайд

  Задача 9:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  if n > 0 then begin
  F(n-2);
  F(n-1);
  F(n-1);
  end;
  writeln('*');
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?
  Ответ: 148
  

• 

  31 слайд

  Задача 10:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  if n > 0 then begin
  writeln('*');
  F(n-2);
  F(n-1);
  F(n-1);
  end;
  writeln('*');
  end;
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?
  Ответ: 197
  

• 

  32 слайд

  Задача 11:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  if n > 1 then begin
  F(n-2);
  F(n-1);
  F(n div 2);
  end;
  writeln('*');
  end;
  
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
  Ответ: 88
  

• 

  33 слайд

  Задача 12:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  if n > 2 then begin
  writeln('*');
  F(n-2);
  F(n-1);
  F(n div 2);
  end;
  writeln('*');
  end;
  Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
  Ответ: 33
  

• 

  34 слайд

  Задача 13:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  F(n+2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(2).
  Ответ: 30
  

• 

  35 слайд

  Задача 14:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n+2);
  F(n*2)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  Ответ: 53
  

• 

  36 слайд

  Задача 15:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n+3);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  Ответ: 42
  

• 

  37 слайд

  Задача 16:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 7 then begin
  F(n+3);
  F(n*2)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(2).
  Ответ: 44
  

• 

  38 слайд

  Задача 17:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 7 then begin
  F(n+2);
  F(n+3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  Ответ: 81
  

• 

  39 слайд

  Задача 18:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n+2);
  F(n+3);
  F(n*2)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  Ответ: 103
  

• 

  40 слайд

  Задача 19:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  F(n+1);
  F(n+2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(2).
  Ответ: 79
  

• 

  41 слайд

  Задача 20:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  writeln(n);
  F(n+2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(2).
  Ответ: 36
  

• 

  42 слайд

  Задача 21:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 5 then begin
  writeln(n);
  F(n+3);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  Ответ: 50
  

• 

  43 слайд

  Задача 22:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 7 then begin
  writeln(n);
  F(n+1);
  F(n+2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(2).
  Ответ: 425
  

• 

  44 слайд

  Задача 23:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  writeln(n);
  F(n+1);
  F(n+2);
  F(n*2)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
  Ответ: 530
  

• 

  45 слайд

  Задача 24:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 6 then begin
  writeln(n);
  F(n+1);
  F(n*2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(2).
  Ответ: 169
  

• 

  46 слайд

  Задача 25:
  
  Дан рекурсивный алгоритм:
  
  procedure F(n: integer);
  begin
  writeln(n);
  if n < 7 then begin
  writeln(n);
  F(n+2);
  F(n*2);
  F(n*3)
  end
  end;
  
  Найдите сумму чисел, которые будут выведены при вызове F(1).
   
   
  Ответ: 426
  

Краткое описание материала