
ЕГЭ_11_рекурсия. Рекурсивные алгоритмы
Все подпрограммы в языке Паскаль (и функции, и процедуры) являются рекурсивными. Это означает, что внутри подпрограммы можно обращаться к самой подпрограмме.
Подпрограмма – это поименованная или каким-либо образом обозначенная часть программы, которая может быть многократно вызвана из различных частей основной программы.
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие , по достижению которого дальнейшее обращение к подпрограмме не происходит.

Чему будет равна сумма чисел при F(10)?
После каждого вызова на экран выводится значение параметра функции, если выполняется условие n2 .
procedure F(n: integer); begin if n 2 then begin writeln(n); F(n - 3); F(n - 4) end end;
Запишем все вызовы в виде дерева вызовов.
F(n-3)
F(n-4)
1
102
2
9
72
62
3
13
42
10
32
6
32
22
Программа_2
5
4
11
8
7
02
-12
02
-12
02
12
12
*10 10 *7 7 *4 4 *1 *0 *3 3 *0 *-1 *6 6 *3 3 *0 *-1 *2
10 7 4 3 6 3

F(n-3)
F(n-4)
1
102
2
6
72
62
42
8
7
3
5
32
32
22
4
12
10 + 7 + 4 + 3 + 6 + 3 = 33

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): 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 - 3);
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11 )?
Программа_3
Используя Forward-описания (предописания), вы можете делать процедуры или функции известными без фактического определения ее операторной части.
F(11)
G(10): *
F(7)
G(6): *
F(3)
G(2): *
F(-1)
11 10 * 7 6 * 3 2 * -1
Ключевое слово forward переводится как опережающий, что следует понимать как опережающее объявление функции или процедуры, что подразумевает, что компилятор должен только проанализировать как вызывается эта функция и занести её имя в таблицу имен.

G(n-1) n 0
F(n-3) n 1
110
101
*
7 0
*
6 1
3 0
*
2 1
-1 0

Найти сумму чисел при вызове F(1)?
Программа_4
procedure F(n: integer);
begin
write(n,' ');
if n
F(n+1);
F(n+3);
end
end;
begin
F(1);
end.
F(n+1)
F(n+3)
F(1)
F(2)
F(4)
F(5)
F(7)
F(3)
F(5)
F(6)
F(4)
F(5)
F(7)
1 +2 +3 + 4 +5 + 7 + 6 +5 + 4 +5 +7 = 49
1 *1 2 *2 3 *3 4 *4 5 7 6 5 4 *4 5 7

Сколько символов звездочка выведется на экран при F(5)?
Программа__5
procedure F(n: integer);
begin
write('*');
if n0 then begin
F(n-2);
F(n div 2);
end
end;
begin
F(5);
end.
F(n-2)
F(n div 2)
F(5)
*
*
F(3)
*
F(2)
*
*
*
F(1)
F(1)
F(1)
F(1)
*
F(0)
F(0)
F(-1)
F(-1)
F(0)
F(-1)
*
*
*
*
*
*
procedure F(n: integer);
begin
write('*',n,' ');
if n0 then begin
F(n-2);
F(n div 2);
end
end;
begin
F(5);
end.
* 5 * 3 * 1 * -1 * 0 * 1 * -1 * 0 * 2 * 0 * 1 * -1 * 0

Что буде напечатано при выполнении F(11)?
Программа_6
procedure F(n: integer);
procedure F(n: integer);
begin
begin
write('*',n,' ');
if n1 then begin
F(n-4);
if n1 then begin
F(n-4);
write(n,' ');
write(n,' ');
F(n div 2);
end;
F(n div 2);
end;
end;
end;
begin
F(11);
begin
end.
F(11);
end.
3 7 3 11 5 2
*11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1

F(n - 4)
F(n div 2)
F(11)
111 +
F(7)
71 +
F(3)
31 +
F(-1)
-11 -
F(1)
11 -
F(3)
31 +
F(-1)
-11 -
procedure F(n: integer);
begin
if n1 then begin
F(n-4);
write(n,' ');
F(n div 2);
end;
end;
begin
F(11);
end.
F(1)
11 -
F(5)
51 +
F(1)
11 -
F(2)
21 +
F(-2)
-21 -
F(1)
11 -
*11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1

procedure F(n: integer);
begin
write('*',n,' ');
if n1 then begin
F(n-4);
write(n,' ');
F(n div 2);
end;
end;
begin
F(11);
end.
11
7
5
2
3
3
1
1
-1
-2
1
1
-1
*11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1

Что буде напечатано при выполнении F(4)?
F(n-1)
F(n-2)
procedure F(n: integer);
begin
if n0 then begin
1 F(n-1);
2 write(n,' ');
3 F(n - 2);
end;
end;
begin
F(4);
end.
4
2
3
F(4)
F(2)
F(3)
2
1
F(2)
1
F(1)
F(1)
F(0)
1
F(1)
F(0)
F(-1)
F(0)
F(-1)
F(0)
procedure F(n: integer);
begin
write('*',n,' ');
if n0 then begin
F(n-1);
write(n,' ');
F(n - 2);
end;
end;
begin
F(4);
end.
F(0)
F(-1)
*4 *3 *2 *1 *0 1 *-1 2 *0 3 *1 *0 1 *-1 4 *2 *1 *0 1 *-1 2 *0
1 2 3 1 4 1 2

Чему равна сумма чисел, выведенных на экран при вызове F(2)?
procedure F(n: integer);
procedure F(n: integer);
begin
begin
write(n,' ');
write(n,' ');
if n
if n
write( '*' ,n,' ');
write(n,' ');
F(n+1);
F(n+1);
F(n+2);
F(n+2);
F(n*2);
F(n*2);
end
end
end;
end;
begin
begin
F(2);
F(2);
end.
end.
Программа
2 *2 3 *3 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8

n*2
n+1
n+2
If n
2 *2 3 *3 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8
2+3+4+5+6 +7+8+12+7+10 +6+7+8 +12+8+5+6+7+8+12+7+10+6 +7+8 +12+4 +5 +6 +7+8+12+7+10+6 +7+8+12+8+4+5+6 +7+8+12+7+10+6+7+8+12+8=393 – сумма, первый write перед if
3+4+4+4+5+6+5+6+5+6+5+6+6+6+6+6=85 – сумма, второй write, который печатает все числа