Анализ

рекурсивных

алгоритмов с помощью

рекуррентной

формулы

Автор: Ромахина Т.А.

учитель информатики и ИКТ

МБОУСОШ № 12 г. Североморска


Рекурсивный алгоритм
это
алгоритм
, решающий задачу путем сведения ее к решению одной или нескольких таких же задач, но в сокращенном их варианте

Для определения

рекурсии необходимо
 условие остановки рекурсии (базовый случай или несколько базовых случаев)  рекуррентная формула

Рекуррентная формула
это формула, выражающая n-ый член последовательности через предыдущие члены

Примеры задач,

решаемых с

использованием

рекуррентных формул


Задача 1:
дан рекурсивный алгоритм. Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(n)? n – конкретное числовое значение function F(n: integer): integer; begin if <условие> then F:= <рекуррентная формула> else F:= <выражение, зависящее от n>; end;

Задача 2:
дан рекурсивный алгоритм. Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(n)? n – конкретное числовое значение function F(n: integer): integer; begin if <условие> then F:= <выражение, зависящее от n> else F:= <рекуррентная формула> end;
procedure F(n: integer); begin
writeln(n);
if <условие> then begin F(m); F(k); - - - - end end;
Задача 3:
найдите сумму чисел, которые будут выведены при вызове функции F(n). n – конкретное числовое значение ( ниже представлены типы рекурсивных алгоритмов (в общем виде), решаемые одним способом) procedure F(n: integer); begin if <условие> then begin F(m); F(k); - - - - end;
writeln(n);
end; m,k – зависят от n
: Сумму чисел, полученных при вызове F(n) , обозначим через S(n). Тогда соответствующая рекуррентная формула будет иметь вид

Задача 4:
найдите сумму чисел, которые будут выведены при вызове функции F(n). n – конкретное числовое значение m,k – зависят от n procedure F(n: integer); begin if <условие> then begin F(m); F(k); - - - - end else
writeln(n)
end;
: Соответствующая рекуррентная формула будет иметь вид
procedure F(n: integer); begin
writeln(n);
if <условие> then begin
writeln(n);
F(m); F(k); - - - - end end;
Задача 5:
найдите сумму чисел, которые будут выведены при вызове функции F(n). n – конкретное числовое значение ( ниже представлены типы рекурсивных алгоритмов (в общем виде), решаемые одним способом) procedure F(n: integer); begin if <условие> then begin
writeln(n);
F(m); F(k); - - - - end;
writeln(n);
end; m,k – зависят от n
: Соответствующая рекуррентная формула будет иметь вид

Задача 6:
найдите сумму чисел, которые будут выведены при вызове функции F(n). n – конкретное числовое значение m,k – зависят от n procedure F(n: integer); begin if <условие> then begin
writeln(n)
F(m); F(k); - - - - end else
writeln(n)
end;
: Соответствующая рекуррентная формула будет иметь вид
procedure F(n: integer); begin
writeln(‘*’);
if <условие> then begin F(m); F(k); - - - - end end;
Задача 7:
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(n)? n – конкретное числовое значение ( ниже представлены типы рекурсивных алгоритмов (в общем виде), решаемые одним способом) procedure F(n: integer); begin if <условие> then begin F(m); F(k); - - - - end;
writeln(‘*’);
end; m,k – зависят от n
: Количество звездочек, которые выводятся при вызове F(n) , обозначим через G(n). Соответствующая рекуррентная формула будет иметь вид

Задача 8:
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(n)? n – конкретное числовое значение m,k – зависят от n procedure F(n: integer); begin if <условие> then begin F(m); F(k); - - - - end else
writeln(‘*’)
end;
: Соответствующая рекуррентная формула будет иметь вид
procedure F(n: integer); begin
writeln(‘*’);
if <условие> then begin
writeln(‘*’);
F(m); F(k); - - - - end end;
Задача 9:
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(n)? n – конкретное числовое значение ( ниже представлены типы рекурсивных алгоритмов (в общем виде), решаемые одним способом) procedure F(n: integer); begin if <условие> then begin
writeln(‘*’);
F(m); F(k); - - - - end;
writeln(‘*’);
end; m,k – зависят от n
: Соответствующая рекуррентная формула будет иметь вид

Задача 10:
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(n)? n – конкретное числовое значение m,k – зависят от n procedure F(n: integer); begin if <условие> then begin
writeln(‘*’)
F(m); F(k); - - - - end else
writeln(‘*’)
end;
: Соответствующая рекуррентная формула будет иметь вид
procedure F(n: integer); begin if <условие> then
writeln(‘*’)
else begin F(m); F(k); - - - - end end;
Задача 11:
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(n)? n – конкретное числовое значение m,k – зависят от n
: Соответствующая рекуррентная формула будет иметь вид

Задача 12:
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(n)? n – конкретное числовое значение m,k – зависят от n procedure F(n: integer); begin if <условие> then
writeln(‘*’)
else begin
writeln(‘*’)
F(m); F(k); - - - - end end;
: Соответствующая рекуррентная формула будет иметь вид

Пример 1
Дан рекурсивный алгоритм:
function F(n: integer): integer;

begin

if n >= 3 then

F:= F(n-3) + F(n-2)*F(n-1)

else

F:= n;

end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(7)?

Решение
 запишем формулы F(n), для n от 7 (т.к. осуществляется вызов F(7)) до 3 (т.к. условие остановки рекурсии n≥3): F(7) = F(4) + F(5)*F(6) F(6) = F(3) + F(4)*F(5) F(5) = F(2) + F(3)*F(4) F(4) = F(1) + F(2)*F(3) F(3) = F(0) + F(1)*F(2)
 вычисляем ответ обратным ходом: F(3) = F(0) + F(1)*F(2) = 0 + 1*2 = 2 F(4) = F(1) + F(2)*F(3) = 1 + 2*2 = 5 F(5) = F(2) + F(3)*F(4) = 2 + 2*5 = 12 F(6) = F(3) + F(4)*F(5) = 2 + 5*12 = 62 F(7) = F(4) + F(5)*F(6) = 5 + 12*62 =
749
Ответ: значение, вычисленное алгоритмом при выполнении вызова F(7) равно 749

Пример 2
Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

writeln(n);

if n < 6 then begin

F(n+2);

F(n*3)

end

end;
Найдите сумму чисел, которые будут выведены при вызове F(2).

Решение
 определим рекуррентную формулу:  запишем формулы S(n), для n от 2 (т.к. осуществляется вызов F(2)) до 5 (т.к. условие остановки рекурсии n<6): S(2) = 2 + S(4) + S(6) S(3) = 3 + S(5) + S(9) S(4) = 4 + S(6) + S(12) S(5) = 5 + S(7) + S(15) •
 вычисляем ответ обратным ходом: S(5) = 5 + S(7) + S(15) = 5 + 7 + 15 = 27 S(4) = 4 + S(6) + S(12) = 4 + 6 + 12 = 22 S(3) = 3 + S(5) + S(9) = 3 + 27 + 9 = 39 S(2) = 2 + S(4) + S(6) = 2 + 22 + 6 =
30
Ответ: сумма чисел, которые будут выведены при вызове F(2) равна 30 Обратите внимание, для нахождения S(2) достаточно найти S(4)

Пример 3
Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

writeln(n);

if n > 0 then begin

writeln(n);

F(n-2);

F(n-2);

F(n div 2);

end

end;
Найдите сумму чисел, которые будут выведены при вызове F(6)

Решение
 определим рекуррентную формулу:  запишем формулы S(n), для n от 6 (т.к. осуществляется вызов F(6)) до 1 (т.к. условие остановки рекурсии n>0): S(6) = 12 + 2S(4) + S(3) S(5) = 10 + 2S(3) + S(2) S(4) = 8 + 2S(2) + S(2) S(3) = 6 + 2S(1) + S(1) S(2) = 4 + 2S(0) + S(1) S(1) = 2 + 2S(-1) + S(0) •
 вычисляем ответ обратным ходом: S(1) = 2 + 2S(-1) + S(0) = 2 – 2 + 0 = 0 S(2) = 4 + 2S(0) + S(1) = 4 + 0 + 0 = 4 S(3) = 6 + 2S(1) + S(1) = 6 + 0 + 0 = 6 S(4) = 8 + 2S(2) + S(2) = 8 + 8 + 4 = 20 S(5) = 10 + 2S(3) + S(2) = 10 + 12 + 4 = 26 S(6) = 12 + 2S(4) + S(3) = 12 + 40 + 6 =
58
Ответ: сумма чисел, которые будут выведены при вызове F(6) равна 58

Пример 4
Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

if n > 1 then begin

F(n-2);

F(n-1);

F(n-1);

end;

writeln('*');

end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

Решение
 определим рекуррентную формулу:  запишем формулы G(n), для n от 5 (т.к. осуществляется вызов F(5)) до 2 (т.к. условие остановки рекурсии n>1): G(5) = 1 + 2G(4) + G(3) G(4) = 1 + 2G(3) + G(2) G(3) = 1 + 2G(2) + G(1) G(2) = 1 + 2G(1) + G(0) •
 вычисляем ответ обратным ходом: G(2) = 1 + 2G(1) + G(0) = 1 + 2 + 1 = 4 G(3) = 1 + 2G(2) + G(1) = 1 + 8 + 1 = 10 G(4) = 1 + 2G(3) + G(2) = 1 + 20 + 4 = 25 G(5) = 1 + 2G(4) + G(3) = 1 + 50 + 10 =
61
Ответ: количество звездочек, которые будут напечатаны при вызове F(5) равна 61

Пример 5
Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

writeln(‘*’);

if n < 5 then begin

writeln(‘*’);

F(n+2);

F(n+3)

end

end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(2)?

Решение
 определим рекуррентную формулу:  запишем формулы G(n), для n от 2 (т.к. осуществляется вызов F(2)) до 4 (т.к. условие остановки рекурсии n<5): G(2) = 2 + G(4) + G(5) G(3) = 2 + G(5) + G(6) G(4) = 2 + G(6) + G(7) •
 вычисляем ответ обратным ходом: G(4) = 2 + G(6) + G(7) = 2 + 1 + 1 = 4 G(3) = 2 + G(5) + G(6) = 2 + 1 + 1 = 4 G(2) = 2 + G(4) + G(5) = 2 + 4 + 1 =
7
Ответ: количество звездочек, которые будут напечатаны при вызове F(2) равна 7 Обратите внимание, для нахождения G(2) достаточно найти G(4)

Пример 6
Дан рекурсивный алгоритм:
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)?

Решение
 определим рекуррентную формулу:  запишем формулы G(n), для n от 6 (т.к. осуществляется вызов F(6)) до 3 (т.к. условие остановки рекурсии n<3): G(6) = G(5) + 2G(4) G(5) = G(4) + 2G(3) G(4) = G(3) + 2G(2) G(3) = G(2) + 2G(1) •
 вычисляем ответ обратным ходом: G(3) = G(2) + 2G(1) = 1 + 2*1 = 3 G(4) = G(3) + 2G(2) = 3 + 2*1 = 5 G(5) = G(4) + 2G(3) = 5 + 2*3 = 11 G(6) = G(5) + 2G(4) = 11 + 2*5 =
21
Ответ: количество звездочек, которые будут напечатаны при вызове F(6) равна 21

Пример 7
Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

if n >= 6 then

write('*')

else begin

write('*')

F(n+1);

F(2*n)

end;

end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(2)?

Решение
 определим рекуррентную формулу:  запишем формулы G(n), для n от 2 (т.к. осуществляется вызов F(2)) до 5 (т.к. условие остановки рекурсии n≥6): G(2) = 1 + G(3) + G(4) G(3) = 1 + G(4) + G(6) G(4) = 1 + G(5) + G(8) G(5) = 1 + G(6) + G(10) •
 вычисляем ответ обратным ходом: G(5) = 1 + G(6) + G(10) = 1 + 1 + 1 = 3 G(4) = 1 + G(5) + G(8) = 1 + 3 + 1 = 5 G(3) = 1 + G(4) + G(6) = 1 + 5 + 1 = 7 G(2) = 1 + G(3) + G(4) = 1 + 7 + 5 =
13
Ответ: количество звездочек, которые будут напечатаны при вызове F(2) равна 13

Задачи для тренировки
1. Дан рекурсивный алгоритм:
function F(n: integer):

integer;

begin

if n > 3 then

F:= F(n - 1) * F(n - 2)

else

F:= n;

end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)? 2. Дан рекурсивный алгоритм:
function F(n: integer):

integer;

begin

if n > 5 then

F:= n;

else

F:= F(n+2) + F(n+3) +

F(n+1)

end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(2)?
4. Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

if n > 0 then begin

F(n-1);

F(n-3)

end;

writeln(n);

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

begin

writeln(n);

if n < 6 then begin

F(n+2);

F(n*3)

end

end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
6. Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

if n < 7 then begin

writeln(n);

F(n+2);

F(n*2);

F(n*3)

end;

writeln(n);

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

begin

writeln(n);

if n < 6 then begin

writeln(n);

F(n+2);

F(n*3)

end

end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
8. Дан рекурсивный алгоритм:
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)? 7. Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

writeln('*');

if n > 0 then begin

F(n-3);

F(n div 2);

end

end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
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)? 9. Дан рекурсивный алгоритм:
procedure F(n: integer);

begin

writeln('*');

if n > 0 then begin

writeln('*');

F(n-2);

F(n div 2);

end

end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Ответы
1. 108 2. 102 3. 30 4. 11 5. 36 6. 426 7. 15 8. 88 9. 31 10. 197

Заключение
1. Представленные разработки основаны на примерах анализа рекурсивных алгоритмов, рассмотренных на сайте К.Ю.Полякова. 2. Еще большее количество заданий для тренировки так же можно найти на сайте К.Ю.Полякова.

Спасибо за

внимание!