Рекурсия
презентация к уроку (7, 8, 9, 10 класс) на тему

11 (базовый уровень, время – 5 мин)

Тема:  рекурсивные алгоритмы.

Что нужно знать:

• рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
• чтобы определить рекурсию, нужно задать

• условие остановки рекурсии (базовый случай или несколько базовых случаев)
• рекуррентную формулу

• любую рекурсивную процедуру можно запрограммировать с помощью цикла
• рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
• существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)

Пример задания:

Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

  writeln(n);

  if n < 5 then begin

    F(n + 1);

    F(n + 3)

  end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

Решение (вариант 1, построение дерева вызовов):

1. поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров
2. поскольку при  выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):

3. складывая все эти числа, получаем 49
4. ответ: 49.

Решение (вариант 2, подстановка):

1. можно обойтись и без дерева, учитывая, что при каждом вызове с n < 5 происходит два рекурсивных вызова; сумму чисел, полученных при вызове , обозначим через :

2. выполняем вычисления:

3. теперь остаётся вычислить ответ «обратным ходом»:
4. 
5. Ответ: 49.

Ещё пример задания:

Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   F(n+2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

Решение (вариант 1, метод подстановки):

6. сначала определим рекуррентную формулу; обозначим через G(n) сумму чисел, которая выводится при вызове F(n)
7. при n >= 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов:

G(n) = n при n >= 6

8. при n < 6 процедура выводит число n и дважды вызывает сама себя:

G(n) = n + G(n+2) + G(3n) при n < 6

9. в результате вызова F(1) получаем

G(1) = 1 + G(3) + G(3)

G(3) = 3 + G(5) + G(9) = 3 + G(5) + 9

G(5) = 5 + G(7) + G(15) = 5 + 7 + 15 = 27

10. используем обратную подстановку:

G(3) = 3 + G(5) + 9  = 3 + 27 + 9 = 39

G(1) = 1 + 2*G(3) = 79

11. Ответ: 79.

Решение (вариант 2, динамическое программирование):

1. п. 1-3 такие же, как в первом варианте решения
2. заполняем таблицу G(n) при n >= 6 (где G(n) = n)

3. остальные ячейки заполняем, начиная с n = 5 справа налево, используя формулу :

G(n) = n + G(n+2) + G(3n)

4. ответ читаем в самой левой ячейке
5. Ответ: 79.

Пример задания:

Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln('*');

 if n > 0 then begin

   F(n-2);

   F(n div 2)

 end

end;

 Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Решение (вариант 1, составление полной таблицы):

6. сначала определим рекуррентную формулу; обозначим через G(n) количество звездочек, которые выводит программа при вызове F(n)
7. из программы видим, что

G(n) = 1 при всех n <= 0

G(n) = 1 + G(n-2) + G(n div 2) при n > 0

8. вспомним, что n div 2 – это частное от деления n на 2
9. по этим формулам заполняем таблицу, начиная с нуля:

G(0) = 1

G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3

G(2) = 1 + G(0) + G(1) = 1 + 1 + 3 = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(4) = 1 + G(2) + G(2) = 1 + 5 + 5 = 11

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(6) = 1 + G(4) + G(3) = 1 + 11 + 7 = 19

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

10. Ответ: 21.

Решение (вариант 2, «с конца»):

1. пп. 1-3 – как в варианте 1
2. по формулам G(7) = 1+ G(5) + G(3), поэтому нужно найти G(5) и G(3)
3. G(5) = 1 + G(3) + G(2), нужны G(3) и G(2)
4. G(3) = 1 + G(1) + G(1), нужно G(1)
5. G(2) = 1 + G(0) + G(1) = 2 + G(1), нужно G(1)
6. G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3
7. теперь идем «обратным ходом»:

G(2) = 2 + G(1) = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

8. Ответ: 21.

Пример задания:

Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = F(n – 1) – G(n – 1),

G(n) = F(n–1) + G(n – 1), при n >=2

Чему равно значение величины F(5)/G(5)?

В ответе запишите только целое число.

Решение:

9. фактически рекуррентная формула задана для пары (F(n); G(n))
10. замечаем, что F(n) – это разность предыдущей пары, а G(n) – сумма тех же значений
11. заполняем таблицу, начиная с известной первой пары

12. искомое значение F(5)/G(5) равно 1
13. ответ: 1.

Ещё пример задания:

Алгоритм вычисления значения функции F(n), где n – натуральное число,

задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * n, при n > 1

Чему равно значение функции F(5)?

В ответе запишите только целое число.

Решение:

14. используя заданную рекуррентную формулу, находим, что

F(5) = F(4) * 5

15. применив формулу еще несколько раз, получаем

F(5) = F(3) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5

16. мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1
17. окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120
18. ответ: 120.

Ещё пример задания:

Процедура F(n), где n – натуральное число, задана следующим образом (язык Паскаль):

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)? В ответе запишите только целое число.

Решение:

1. эта задача по сути такая же, как и предыдущая, но «завёрнута» в другой фантик: для n < 3 (то есть, для 1 и 2) функция выводит одну звездочку

F(1) = F(2) = 1

а для бóльших n имеем рекуррентную формулу

 F(n) = F(n-1) + F(n-2) + F(n-2)

         = F(n-1) + 2*F(n-2)

2. запишем в таблицу базовые случаи

3. заполняем таблицу, используя рекуррентную формулу:

F(3) = F(2) + 2*F(1) = 3

F(4) = F(3) + 2*F(2) = 5

F(5) = F(4) + 2*F(3) = 11

F(6) = F(5) + 2*F(4) = 21

4. ответ: 21.

Задачи для тренировки^[1]:

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 1), при n > 1

Чему равно значение функции F(5)? В ответе запишите только целое число.

2. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 2), при n > 1

Чему равно значение функции F(5)? В ответе запишите только целое число.

3. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (2*n + 1), при n > 1

Чему равно значение функции F(4)? В ответе запишите только целое число.

4. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (2*n - 1), при n > 1

Чему равно значение функции F(5)? В ответе запишите только целое число.

5. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (3*n - 2), при n > 1

Чему равно значение функции F(4)? В ответе запишите только целое число.

6. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1) + F(n-2), при n > 1

Чему равно значение функции F(7)? В ответе запишите только целое число.

7. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = 2*F(n–1) + F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только целое число.

8. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1) + 2*F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только целое число.

9. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = 3*F(n–1) - F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только целое число.

10. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1)*F(n-2)+1, при n > 1

Чему равно значение функции F(6)? В ответе запишите только целое число.

11. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1)*F(n-2)+2, при n > 1

Чему равно значение функции F(5)? В ответе запишите только целое число.

12. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*n, при n > 2

Чему равно значение функции F(7)? В ответе запишите только целое число.

13. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*n + 2, при n > 2

Чему равно значение функции F(8)? В ответе запишите только целое число.

14. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*(n-1), при n > 2

Чему равно значение функции F(7)? В ответе запишите только целое число.

15. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*(n-1) + 2, при n > 2

Чему равно значение функции F(8)? В ответе запишите только целое число.

16. Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 3; F(2) = 3;

F(w) = 5*F(w-l)- 4*F(w-2) при w > 2.

Чему равно значение функции F(15)?

17. Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 4; F(2) = 5;

F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.

Чему равно значение функции F(8)?

18. (http://ege.yandex.ru) Алгоритм вычисления значений функций F(w) и Q(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 1; Q(1) = 1;

F(w) = F(w-l) + 2*Q(w-1) при w > 1

Q(w) = Q(w-l) - 2*F(w-1) при w > 1.

Чему равно значение функции F(5)+Q(5)?

19. Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 1; F(2) = 2;

F(w) = 3*F(w-l)- 2*F(w-2) при w > 2.

Чему равно значение функции F(7)?

20. Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 2; F(2) = 4;

F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.

Чему равно значение функции F(7)?

21. (http://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:

F(1) = 1; F(2) = 2;

F(n) = 5*F(n-l)- 6*F(n-2) при n > 2.

Чему равно значение функции F(7)?

22. (http://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:

F(1) = 1; F(2) = 2; F(3) = 3

F(n) = F(n-3)*(n-1)/3 при n > 3.

Чему равно значение функции F(16)?

23. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 2; G(1) = 1;

F(n) = F(n–1) – G(n–1),

G(n) = F(n–1) + G(n–1), при n >=2

Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.

24. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = F(n–1) – G(n–1),

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.

25. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = F(n–1) – 2*G(n–1),

G(n) = F(n–1) + G(n–1), при n >=2

Чему равно значение величины G(5)/F(5)? В ответе запишите только целое число.

26. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = 2*F(n–1) – G(n–1),

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины G(5)+F(5)? В ответе запишите только целое число.

27. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = 2*F(n–1) – G(n–1),

G(n) = 2*F(n–1) + G(n–1), при n >=2

Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.

28. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = F(n–1) – 2*G(n–1),

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины G(5)-F(5)? В ответе запишите только целое число.

29. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = 3*F(n–1) – 2*G(n–1),

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины G(5)-F(5)? В ответе запишите только целое число.

30. Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1; G(1) = 1;

F(n) = 3*F(n–1) – 3*G(n–1),

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.

31. Дан рекурсивный алгоритм:

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)?

32. Дан рекурсивный алгоритм:

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)?

33. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln('*');

 if n > 0 then begin

   F(n-3);

   F(n div 2);

 end

end;

 Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

34. Дан рекурсивный алгоритм:

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)?

35. Дан рекурсивный алгоритм:

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)?

36. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln('*');

 if n > 0 then begin

   writeln('*');

   F(n-2);

   F(n div 2);

 end

end;

 Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

37. Дан рекурсивный алгоритм:

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)?

38. Дан рекурсивный алгоритм:

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)?

39. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 if n > 0 then begin

    F(n-2);

    F(n-1);

    F(n-1);

 end;

 writeln('*');

end;

 Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

40. Дан рекурсивный алгоритм:

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)?

41. Дан рекурсивный алгоритм:

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)?

42. Дан рекурсивный алгоритм:

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)?

43. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1,

F(n) = F(n–1) + 2n-1, при n > 1

Чему равно значение функции F(12)? В ответе запишите только целое число.

44. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   F(n+2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2).

45. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 5 then begin

   F(n+2);

   F(n*2)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

46. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 5 then begin

   F(n+3);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

47. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 7 then begin

   F(n+3);

   F(n*2)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2).

48. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 7 then begin

   F(n+2);

   F(n+3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

49. Дан рекурсивный алгоритм:

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).

50. Дан рекурсивный алгоритм:

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).

51. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2).

52. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 5 then begin

   writeln(n);

   F(n+3);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

53. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+2);

   F(n+3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

54. Дан рекурсивный алгоритм:

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).

55. Дан рекурсивный алгоритм:

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).

56. Дан рекурсивный алгоритм:

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).

57. Дан рекурсивный алгоритм:

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).

58. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при n ≤ 2;

F(n) = F(n-2)*(n+2) при n > 2.

Чему равно значение функции F(8)?

59. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при n ≤ 2;

F(n) = F(n-2)*(n+1) при n > 2.

Чему равно значение функции F(7)?