Рекурсивные алгоритмы. Подготовка к ЕГЭ, задание 11

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

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

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

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

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

Пример задания:
Дан рекурсивный алгоритм:
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
+3

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

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

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

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

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

Пример № 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, а символ *
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

Пример № 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)=

Пример № 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)? В ответе запишите только целое число.
эта задача по сути такая же, как и предыдущая: для n < 3 функция выводит одну звездочку, а для бóльших n продолжаем рисовать дерево
-1
-2
4
-2
3
2

Пример № 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)? В ответе запишите только целое число.
-1
-2
4
-2
3
*
Вторая и третья ветви абсолютно одинаковые, поэтому будем рисовать одну, а количество «звездочек» потом умножим на 2.
При условии n<3 на экране появляются «звездочки».

Пример № 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)? В ответе запишите только целое число.
-1
-2
4
-2
3
**
3
**
***
***
***
***
Получаем по первой ветви 11 «звездочек», по третьей, а значит и по второй – по 5.
Всего – 21
При условии n<3 на экране появляются «звездочки».

Пример № 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)=
S (n)=

Пример № 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)=
Нам нужно узнать 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

ЗАДАНИЯ ДЛЯ ТРЕНИРОВКИ

Задача 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

Задача 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

Задача 3:
ДАН РЕКУРСИВНЫЙ АЛГОРИТМ:
PROCEDURE F(N: INTEGER);
BEGIN
WRITELN('*');
IF N > 0 THEN BEGIN
F(N-3);
F(N DIV 2);
END
END;
СКОЛЬКО СИМВОЛОВ "ЗВЕЗДОЧКА" БУДЕТ НАПЕЧАТАНО НА ЭКРАНЕ ПРИ ВЫПОЛНЕНИИ ВЫЗОВА F(7)?
Ответ: 15

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 13:
ДАН РЕКУРСИВНЫЙ АЛГОРИТМ:
PROCEDURE F(N: INTEGER);
BEGIN
WRITELN(N);
IF N < 6 THEN BEGIN
F(N+2);
F(N*3)
END
END;
НАЙДИТЕ СУММУ ЧИСЕЛ, КОТОРЫЕ БУДУТ ВЫВЕДЕНЫ ПРИ ВЫЗОВЕ F(2).
Ответ: 30

Задача 14:
ДАН РЕКУРСИВНЫЙ АЛГОРИТМ:
PROCEDURE F(N: INTEGER);
BEGIN
WRITELN(N);
IF N < 5 THEN BEGIN
F(N+2);
F(N*2)
END
END;
НАЙДИТЕ СУММУ ЧИСЕЛ, КОТОРЫЕ БУДУТ ВЫВЕДЕНЫ ПРИ ВЫЗОВЕ F(1).
Ответ: 53

Задача 15:
ДАН РЕКУРСИВНЫЙ АЛГОРИТМ:
PROCEDURE F(N: INTEGER);
BEGIN
WRITELN(N);
IF N < 5 THEN BEGIN
F(N+3);
F(N*3)
END
END;
НАЙДИТЕ СУММУ ЧИСЕЛ, КОТОРЫЕ БУДУТ ВЫВЕДЕНЫ ПРИ ВЫЗОВЕ F(1).
Ответ: 42

Задача 16:
ДАН РЕКУРСИВНЫЙ АЛГОРИТМ:
PROCEDURE F(N: INTEGER);
BEGIN
WRITELN(N);
IF N < 7 THEN BEGIN
F(N+3);
F(N*2)
END
END;
НАЙДИТЕ СУММУ ЧИСЕЛ, КОТОРЫЕ БУДУТ ВЫВЕДЕНЫ ПРИ ВЫЗОВЕ F(2).
Ответ: 44

Задача 17:
ДАН РЕКУРСИВНЫЙ АЛГОРИТМ:
PROCEDURE F(N: INTEGER);
BEGIN
WRITELN(N);
IF N < 7 THEN BEGIN
F(N+2);
F(N+3)
END
END;
НАЙДИТЕ СУММУ ЧИСЕЛ, КОТОРЫЕ БУДУТ ВЫВЕДЕНЫ ПРИ ВЫЗОВЕ F(1).
Ответ: 81

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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

Задача 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