19.Рекурсивные алгоритмы

Рекурсивные алгоритмы.

Что нужно знать:

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

• чтобы определить рекурсию, нужно задать

  • условие остановки рекурсии (базовый случай или несколько базовых случаев)

  • рекуррентную формулу

• любую рекурсивную процедуру можно запрограммировать с помощью цикла

• рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным

• существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)

Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln('*');

if n 0 then begin

F(n-2);

F(n div 2)

end

end;

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

Решение (вариант 1, составление полной таблицы):

1. сначала определим рекуррентную формулу; обозначим через G(n) количество звездочек, которые выводит программа при вызове F(n)

2. из программы видим, что

G(n) = 1 при всех n

G(n) = 1 + G(n-2) + G(n div 2) при n 0

1. вспомним, что n div 2 – это частное от деления n на 2

2. по этим формулам заполняем таблицу, начиная с нуля:

G(0) = 1

G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3

G(2) = 1 + G(0) + G(1) = 1 + 1 + 3 = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(4) = 1 + G(2) + G(2) = 1 + 5 + 5 = 11

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(6) = 1 + G(4) + G(3) = 1 + 11 + 7 = 19

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

1. Ответ: 21.

Решение (вариант 2, «с конца»):

1. пп. 1-3 – как в варианте 1

2. по формулам G(7) = 1+ G(5) + G(3), поэтому нужно найти G(5) и G(3)

3. G(5) = 1 + G(3) + G(2), нужны G(3) и G(2)

4. G(3) = 1 + G(1) + G(1), нужно G(1)

5. G(2) = 1 + G(0) + G(1) = 2 + G(1), нужно G(1)

6. G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3

7. теперь идем «обратным ходом»:

G(2) = 2 + G(1) = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

1. Ответ: 21.