Begin
<операторы>
End;
Для вызова процедуры достаточно указать ее имя со списком фактических параметров.
Функция — подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.
function <имя_функции>(<описание входных данных>)<тип функции>;
Begin
<операторы>
<имя_функции>:=<результат>
End;
Для вызова функции, ее имя со списком параметров можно использовать в любом выражении, в условиях, в некоторых операторах главной программы.
Рекурсивная функция -это такая функция, в которой реализован способ вычисления очередного значения функции через вычисление ее предшествующих значений. Это прямая рекурсия.(смотри задача1, задача3 и задача4)
Косвенной называется рекурсия, когда две или более процедуры или функции вызывают друг друга. Пример косвенного вызова процедуры или функции: процедура A вызывает процедуру B, а процедура B вызывает процедуру A.(задача 2).
Понятие рекурсивной функции тесно связано с понятием стек. Это «разновидность списка, в котором любой доступ производится только на одном из его концов, который называется вершиной стека. Иногда стек называют списком LIFO(Last In – First Out - последний вошел, первым вышел).
Механизм стека напоминает железнодорожный тупик, из которого первым может выехать только поезд, въехавший в него последним.»[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<2 не выполняется | Тело цикла не выполняться | |
| F(0) | N<2 не выполняется | Тело цикла не выполняться
 Конец выполнения F(3). Возврат к F(4)
| |
| F(2) | N=2 не выполняется | Тело цикла не выполняться | |
| F(1) | N=1 не выполняется | Тело цикла не выполняться Конец выполнения 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;
Решение:
Решение будем представлять в виде таблицы и в виде схемы.
| 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)
| * |
Программа завершилась.
Считаем количество «*».
Ответ: 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
Разбор заданий № 21.
Для решения задач данного задания необходимо владение основами анализа функций в пределах курса математики средней школы. Рассмотрим некоторые стандартные варианты.
Задача №1 (ЕГЭ 2017, вар.12)
Найти наименьшее значение k, при котором программа выдает тот же ответ, что при k=20.
Var k,i: longint;
function f (n: longint): longint;
begin
f:=n*n*n;
end;
function g (n: longint): longint;
begin
g:=3*n-2;
end;
begin
readln(k);
I:=1;
while f(i)<g(k) do
i:=i+1;
writeln(i);
end.
Решение:
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, видим, что число к, которое удовлетворяет условию найдем из неравенства:
27<g(k)<=64.
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;
begin
F:=-3*(x+2)*x;
end;
begin
a:=-10; b:=10;
R:=F(a);
for t:=a to b do
begin
if (F(t)<R) then begin
R:= F(t);
end;
writeln(R);
end.
Какое число будет напечатано в результате выполнения алгоритма?
Решение:
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 <F(x) до достижения максимума функции F(x).
- При 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.
Ответ: -360
Задача №3 (ЕГЭ 2017, вар.10)
Найти наибольшее значение входной переменной k, при котором программа выдает тот же ответ, что при k=9.
Var k,i: longint;
function f (n: longint): longint;
begin
f:=-n*(n+1);
end;
function g (n: longint): longint;
begin
g:=-2*n+2;
end;
begin
readln(k);
i:=1;
while f(i)>g(k) do
i:=i+1;
writeln(i);
end.
Решение:
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<-16.
6. Следовательно, f(i) станет меньше или равно -16 при i =4 (f(i)=64).
При i = 5 ответ не будет соответствовать условию задачи.
7. По результатам анализа программы, проведенному в п.1, видим, что число к, которое удовлетворяет условию найдем из неравенства:
-30<g(k)<=-20. Наибольшее значение, которое удовлетворяет этому условию g(k)=-20. Откуда находим,
-2*k+2=-20
-2*k=-22
k=11.
Ответ: 11
Список литературы
1. «ОГЭ. Информатика: универсальный справочник»/Дьячкова О.В. - Москва:Эксмо, 2016.