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

1.

РЕКУРСИВНЫЕ
АЛГОРИТМЫ

2.

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

3.

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

4.

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

5.

Член последовательности в
рекурсивном алгоритме объявляется
с помощью процедуры:
PROCEDURE F(n:integer);

6.

Пример рекурсивнго алгоритма:
procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n + 1);
F(n + 3);
end;
end.

7.

№1
Алгоритм вычисления значения функции F(n),
где n – натуральное число, задан следующими
соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 1), при n > 1
Чему равно значение функции F(5)?

8.

№2
Алгоритм вычисления значения функции
F(n), где n – натуральное число, задан
следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(7)?

9.

№3
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
F(n-2);
F(n-2);
F(n div 2);
end;
еnd.
Сколько символов "звездочка" будет напечатано на экране
при выполнении вызова F(6)?

10.

№4
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
writeln('*');
if n > 0 then begin
F(n-2);
F(n div 2);
F(n div 2);
end;
еnd.
Сколько символов "звездочка" будет напечатано на экране при
выполнении вызова F(7)?

11.

№5
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 6 then begin
F(n+2);
F(n*3)
end;
еnd.
Найдите сумму чисел, которые будут выведены при вызове F(2).

12.

№6
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 7 then begin
F(n+2);
F(n+3)
end;
еnd.
Найдите сумму чисел, которые будут выведены при вызове F(1).

13.

№7
• № 5Определите, что выведет на экран программа при вызове
F(9).
procedure F(n: integer);
begin
if n > 0 then begin
F(n – 4);
F(n div 3);
write(n)
end;
еnd.

14.

№8
Определите, что выведет на экран программа при вызове F(9)?
procedure F(n: integer);
begin
if n > 0 then begin
F(n – 4);
write(n);
F(n div 2);
end;
еnd.