ЕГЭ информатика

№11 Тема: рекурсивные алгоритмы.
Что нужно знать:
· рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
· чтобы определить рекурсию, нужно задать
o условие остановки рекурсии (базовый случай или несколько базовых случаев)
o рекуррентную формулу
· любую рекурсивную процедуру можно запрограммировать с помощью цикла
· рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
· существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)
Пример задания:
Р-05. Ниже записаны две рекурсивные процедуры: F и G:
procedure F(n: integer); forward; procedure G(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 - 2);
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении
вызова F(11)?
Решение:
1) заметим, что каждая функция вызывает другую (это называется косвенная рекурсия), причём только один раз
2) вот цепочка вызовов:
F(11) ® G(10) ® F(8) ® G(7) ® F(5) ® G(4) ® F(2) ® G(1)
3) за один вызов функции G выводится одна звёздочка, внутри функции F звездочки не выводятся, поэтому за 4 вызова G будет выведено 4 звездочки
4) Ответ: 4.
Пример задания:
 Дан рекурсивный алгоритм:
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) поскольку при n<5 выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):



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