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

Что надо знать:

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

​

Пример задания:

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 2), при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

​

​

Пример задания:

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*(n-1) + 2, при n > 2

Чему равно значение функции F(8)? В ответе запишите только натуральное число.

​

Пример задания:

Алгоритм вычисления значений функций F(w) и Q(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 1; Q(1) = 1;

F(w) = F(w-l) + 2*Q(w-1) при w > 1

Q(w) = Q(w-l) - 2*F(w-1) при w > 1.

Чему равно значение функции F(5)+Q(5)?

​

Пример задания:

Процедура F(n), где n – натуральное число, задана следующим образом (язык Паскаль):

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)? В ответе запишите только натуральное число.

​