Для вызова процедуры достаточно указать ее имя со списком фактических параметров.
Функция — подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.
Для вызова функции, ее имя со списком параметров можно использовать в любом выражении, в условиях, в некоторых операторах главной программы.
Рекурсивная функция -это такая функция, в которой реализован способ вычисления очередного значения функции через вычисление ее предшествующих значений. Это прямая рекурсия.(смотри задача1, задача3 и задача4)
Косвенной называется рекурсия, когда две или более процедуры или функции вызывают друг друга. Пример косвенного вызова процедуры или функции: процедура A вызывает процедуру B, а процедура B вызывает процедуру A.(задача 2).
Понятие рекурсивной функции тесно связано с понятием стек. Это «разновидность списка, в котором любой доступ производится только на одном из его концов, который называется вершиной стека. Иногда стек называют списком LIFO(Last In – First Out — последний вошел, первым вышел).
Информатика ЕГЭ № 11. Рекурсия: Разбор задачи
Механизм стека напоминает железнодорожный тупик, из которого первым может выехать только поезд, въехавший в него последним.»[1] или его можно сравнить с пачкой документов, в которой в любой момент доступен только верхний документ. Можно положить поверх пачки еще один документ, который сделает недоступным документ, лежащий под ним, или снять верхний документ с пачки, открыв доступ к нижележащему.
Рекурсивые функции работают по принципу стека: пока не закончится процесс последней вызванной программы, предыдущие выполняться не могут и находяться в состоянии ожидания. Рассмотрим задачи №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)?
Решение будем представлять в виде таблицы и в виде схемы.
| F(n) | Что печатает? | Проверка условия | Возврат к каким функциям будет возврат по порядку? |
  F(4) |
n>2, выполняется |    F(3); F(2); F(1); |
|
| F(3) | N>2 выполняется |    F(2); F(1); F(0); |
|
| F(2) | N=2 не выполняется | Тело цикла не выполняться | |
| F(1) | n | Тело цикла не выполняться | |
| F(0) | N | Тело цикла не выполняться  Конец выполнения F(3). Возврат к F(4) |
|
| F(2) | N=2 не выполняется | Тело цикла не выполняться | |
| F(1) | N=1 не выполняется | Тело цикла не выполняться Конец выполнения F(4) |
11 Задание ЕГЭ Информатика Рекурсия
Больше процедура выполняться не будет. Программа завершится.
Задача №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 | Тело цикла не выполняться Процесс возвращается к функции G(2) |
Больше процедура выполняться не будет. Программа завершится.
Задача №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;
Решение будем представлять в виде таблицы и в виде схемы.
| F(n) | Проверка условия | Возврат к каким функциям будет возврат по порядку? | Что печатает? |
  F(5) |
n>1, выполняется |  F(2); F(4); |
*. Алгоритм закончился |
  F(2) |
n>1 выполняется |    F(1); F(1); |
* |
| F(1) | n=1 не выполняется |  Тело цикла не выполняться. Возврат к F(2) |
* |
| F(1) | n=1 не выполняется |  Тело цикла не выполняться. Возврат к F(2) |
* |
| F(4) | n>1 выполняется |   F(2); F(3); |
*.возврат в F(5) |
| F(2) | n>1 выполняется |     F(1); F(1) |
* |
| F(1) | n=1 не выполняется | Тело цикла не выполняться. Возврат к F(2) |
* |
| F(1) | n=1 не выполняется | Тело цикла не выполняться. Возврат к F(2) |
* |
| F(3) | n>1 выполняется |  F(1); F(2) |
* возврат в F(4) |
| F(1) | n=1 не выполняется | Тело цикла не выполняться. Возврат к F(3) |
* |
| F(2) | n>1 выполняется | F(1); F(1) |
* |
| F(1) | n=1 не выполняется | Тело цикла не выполняться. Возврат к F(2) |
* |
| F(1) | n=1 не выполняется | Тело цикла не выполняться. Возврат к F(2) |
* |
Задача №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
Разбор заданий № 21.
Для решения задач данного задания необходимо владение основами анализа функций в пределах курса математики средней школы. Рассмотрим некоторые стандартные варианты.
Задача №1 (ЕГЭ 2017, вар.12)
Найти наименьшее значение k, при котором программа выдает тот же ответ, что при k=20.
function f (n: longint): longint;
f:=n*n*n;
function g (n: longint): longint;
g:=3*n-2;
1. Найдем значение I, которое напечатает программа при вводе k=20.
Цикл повторится до тех пор, пока f(i) не станет больше или равным g(20), а это равно g(20)= 3*20-2=58. Следовательно, f(i) станет большим или равным 58 при i = 4, так как f(i)= i*i*i =64 при i =4. При i = 3 (f(i)=27) ответ не будет соответствовать условию задачи.
2. По результатам анализа программы, проведенному в п.1, видим, что число к, которое удовлетворяет условию найдем из неравенства:
3. Наименьшее значение, которое удовлетворяет этому условию g(k)=28. Откуда находим, 3*k-2=28
3*k=30
k=10.
Ответ: 10
Задача №2 (ЕГЭ 2017, вар.18)
Var a,b,t,R: integer;
function F (x: integer): integer;
F:=-3*(x+2)*x;
Какое число будет напечатано в результате выполнения алгоритма?
1. Проанализируем функцию F(х). F(х):=-3*(x+2)*x квадратичная и имеет два корня х=-2 и х=0. F'(х):=-6*x-6, из которого хmax =-1, при этом значение Fmax(-1):= 3. График функции — парабола, ветви которой направлены вниз.
2. Рассмотрим значения F(х).и R вблизи критических точек:
— При t=-10, начало цикла. F(x)=R и условие выполняться не будет. И
3. R =F(-10)=-240. Затем функция возрастает и условие R — При t=-1, функция F(x) будет иметь максимальное значение равное и начинает уменьшаться до значения F(x)=-240, при x=8. В этом случае значения сравняются, F(x)=R,
4. При х=9, F(x)=-3*(9+2)*9= -297. Это значение уже меньше, чем -240, поэтому условие выполняется и значение R станет равным -297.
5. При х=10, F(x)=-3*(10+2)*10= -360. Это значение так же меньше, чем -297, поэтому условие выполняется и R примет значение равное -360.
6. При х=11 цикл уже не выполняется, а значит будет напечатано значение R=-360.
Задача №3 (ЕГЭ 2017, вар.10)
Найти наибольшее значение входной переменной k, при котором программа выдает тот же ответ, что при k=9.
function f (n: longint): longint;
f:=-n*(n+1);
function g (n: longint): longint;
g:=-2*n+2;
1. Найдем значение I, которое будет напечатает программа при вводе k=9.
Цикл повторится до тех пор, пока f(i) не станет больше или равным g(9).
Рассчитаем g(9)= -2*9+2=-16.
2. При i=1, F(1)=-2. Условие выполняется и цикл работает.
3. При i=2, F(2)=-6.Условие также должно выполняться. -6>-16.
4. При i=3, F(3)=-12.Условие также должно выполняться. -12>-16.
5. При i=4, F(4)=-20.Условие не выполняется, так как -20 6. Следовательно, f(i) станет меньше или равно -16 при i =4 (f(i)=64).
При i = 5 ответ не будет соответствовать условию задачи.
7. По результатам анализа программы, проведенному в п.1, видим, что число к, которое удовлетворяет условию найдем из неравенства:
1. «ОГЭ. Информатика: универсальный справочник»/Дьячкова О.В. — Москва:Эксмо, 2016.
Источник: poisk-ru.ru
11(Базовый уровень, время – 5 мин)
Р-05.Дан рекурсивный алгоритм:procedure F(n: integer);beginwriteln(n);if n < 5 then beginF(n + 1);F(n + 3)endend;Найдите сумму чисел, которые будут выведены при вызове F(1).Решение (вариант 1, построение дерева вызовов):
- поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров
- поскольку при
выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):
- складывая все эти числа, получаем 49
- ответ: 49.
Решение (вариант 2, подстановка):
- можно обойтись и без дерева, учитывая, что при каждом вызове с n< 5 происходит два рекурсивных вызова; сумму чисел, полученных при вызове
, обозначим через
:
- выполняем вычисления:
- теперь остаётся вычислить ответ «обратным ходом»:
- Ответ: 49.
Ещё пример задания:
Источник: studfile.net
Задание 16. Системы счисления. Кодирование чисел. ЕГЭ 2023 по информатике
За это задание ты можешь получить 1 балл. На решение дается около 2 минут. Уровень сложности: повышенный.
Средний процент выполнения: 54.9%
Ответом к заданию 16 по информатике может быть цифра (число) или слово.
Разбор сложных заданий в тг-канале
Задачи для практики
Задача 1
Функция F(n), где n — натуральное число, вычисляется по следующему правилу:
F(n) = n, при n 3 кратном трём;
F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;
F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.
Чему равно значение функции F(28)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
if n 3 кратном трём;
F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;
F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.
Чему равно значение функции F(25)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
F(n) = F(n-1)+2*F(n-3), при n > 1 нечётном
Чему равно значение функции F(199)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
F(n) = F(n-2)*n, при n > 1 нечётном
Чему равно значение функции F(10)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
Чему равно значение функции F(8)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
Чему равно значение функции F(19)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
if n 3 кратном трём;
F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;
F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.
Чему равно значение функции F(22)?
Для выполнения задания рекомендуется написать программу.
Решение
Перепишем правило вычисления функции в рекуррентную функцию на языке Python:
Для доступа к решениям необходимо включить уведомления от группы Турбо в вк — это займет буквально 10 секунд. Никакого спама, только самое важное и полезное для тебя. Ты всегда можешь запретить уведомления.
Подпишись на полезные материалы ЕГЭ по информатике: разбор реальных вариантов ЕГЭ и сложных заданий + авторские конспекты
Источник: egeturbo.ru