Готовимся к ЕГЭ2018

Разбор 11 задания
Рекурсия. Рекурсивные функции

Задача №1(ЕГЭ 2017, вар.12)

Записана рекурсивная функция(процедура) F.

Procedure  F (n:integer );

Begin

write(n);

If  n>2  then      begin

                   F(n-1);

                   F(n-2);

                   F(n-3)

                   End

End;

Что выведет программа при вызове F(4)?

             Решение:

Решение будем представлять в виде таблицы и в виде схемы.

Больше процедура выполняться не будет. Программа завершится.

Ответ: 432021

Задача №2 (Демо 2016)

Записаны две рекурсивные функции F и G.

Procedure G(n:integer);forward;

Procedure F(n:integer);forward;

Procedure F(n:integer);

Begin

If n>0 then    G(n-1);

End;

Procedure G(n:integer);

 begin

              writeln(‘*’);

    if n>1 then  F(n-3);

                   End

End;

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

             Решение:

Решение будем представлять в виде таблицы и в виде схемы.

F(n)	Что печатает?	Проверка условия	Возврат к каким функциям будет возврат по порядку?
F(11)		11>0,  выполняется	G(10)
G(10)	*	10>1выполняется	F(7)
F(7)		7>0,выполняется	G(6)
G(6)	*	6>1,выполняется	F(3)
F(3)	-	3>0,выполняется	G(2)
G(2)	*	2>1выполняется	F(-1)
F(-1)	-	-1<0  не выполняется	Тело цикла не выполняться Процесс возвращается к функции G(2)

Больше процедура выполняться не будет. Программа завершится.

Ответ: 3

Задача №3 (ЕГЭ 2016 (Ушаков), вар.11)

Определите, сколько звездочек будет напечатано в результате вызова F(5) приведенной подпрограммы:

Procedure  F (n:integer );

Begin

If  n>1  then      begin

                   F(n div 2);

                   F(n-1);

                   End;

write('*');

End; 

Решение:

Решение будем представлять в виде таблицы и в виде схемы.

Программа завершилась.

Считаем количество «*».

Ответ: 13

Задача №4 (ЕГЭ 2017, вар.20)

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

                                F(1)=1

                                F(2)=1

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

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

             Решение:

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

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

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

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

F(5) = 2*7 + 3

= 17

Ответ: 17